Python按钮算法

Question

我目前正试图用Python编程解决一个难题，我希望自己能够解决它，但我发现很难描述这个问题，所以我可以通过在线资源寻求帮助。下面我将描述问题的性质，我们非常感谢您的帮助

因此，有一套4个彩色按钮，每个按钮都被分配一个功能，以循环方式改变一个或多个按钮的颜色。这些按钮的代码表示可能如下所示：

# 1 = green, 2 = red, 3 = blue, 4 = purple
# goes 1->4 then loops
cstate = [1,3,4,1] # current state of the numbers

按钮可以执行的四种不同功能是：

1. 自身递增1
2. 将自身和另一个增量增加1
3. 将自身和其他2个增加1
4. 全部递增1

每个功能对每个按钮都是唯一的，因此不能为两个按钮分配相同的功能

我尝试表示这些函数是为了创建一个数组，描述通过单击每个按钮而受影响的按钮的索引，例如：

incArray =[[0,3],[0,1,3],[0,1,2,3],[3]]

接下来，我创建了一个函数，将按钮函数应用于上述cstate数组：

def increment(currentState, whichClicked, whichEffects):
    
    retArr = currentState
    for click in whichClicked:
        for change in whichEffects[click]:
            if currentState[change] == 4:
                retArr[change] = 1
            else:
                retArr[change] += 1
        print(retArr)

    return retArr

现在在这个特定的例子中，我给increment函数添加了whichClicked = [2,2,2,1,0,3,3]，因为我知道这是fstate = [2,3,3,4]的正确组合（或最终状态）

我试图实现的是编写代码来生成上面描述的whichClicked数组，给定cstate和fstate。提前感谢您提供的任何帮助

Answer 1

我倾向于开发这类算法，从一个“哑”暴力算法开始，然后进一步优化它

蛮力

您可以通过一种Breadth-first search algorithm以“暴力”的方式实现这一点，您只需：

• 单击初始状态上的所有按钮（4个选项）
• 对于所有结果状态，您将再次单击所有按钮（16个选项）
• 等等，你经常检查你是否达到了目标状态

大概是这样的：

from collections import deque
from dataclasses import dataclass

start_state = [1,3,4,1] # current state of the numbers
incArray =[[0,3],[0,1,3],[0,1,2,3],[3]]

@dataclass
class Node:
    path: list
    state: list

def apply_button(state, inc_array, button):
    new_state = state.copy()
    for affected_button in inc_array[button]:
        new_state[affected_button] = new_state[affected_button] % 4 + 1
    return new_state

def brute_force(start_state, inc_array, goal_state):
    iterations=0
    leafNodes = deque([Node([], start_state)])
    while True:
        node = leafNodes.popleft()
        for button in range(4):
            iterations+=1
            new_state = apply_button(node.state, inc_array, button)
            new_path = node.path + [button]
            if new_state==goal_state:
                print(f"iterations: {iterations}")
                return new_path
            leafNodes.append(Node(new_path, new_state))

print(brute_force(start_state,incArray,[2, 3, 3, 4]))
# OUTPUT:
# iterations: 7172
# [0, 1, 2, 2, 2, 3, 3]

首次优化

您将看到结果输出与您在示例中提供的“whichClicked”数组相同，但所有项都已排序。这是因为单击按钮的顺序不会影响最终结果。 您可以使用这些知识来优化算法，因为它正在评估大量冗余选项。（例如，路径[0,1]给出的结果与路径[1,0]相同）

因此，一个新的策略可能是在解决方案中排除这些冗余选项。如果在纸上绘制整个搜索图（或取消对# print(new_path)行的注释），您会看到以下代码仅在“排序”路径上迭代：

def brute_force_opt(start_state, inc_array, goal_state):
    iterations=0
    leafNodes = deque([Node([], start_state)])
    while True:
        node = leafNodes.popleft()
        min_button = node.path[-1] if len(node.path) else 0
        for button in range(min_button, 4):
            iterations+=1
            new_state = apply_button(node.state, inc_array, button)
            new_path = node.path + [button]
            # print(new_path)
            if new_state==goal_state:
                print(f"iterations: {iterations}")
                return new_path
            leafNodes.append(Node(new_path, new_state))

print(brute_force_opt(start_state,incArray,[2, 3, 3, 4]))
# OUTPUT:
# iterations: 283
# [0, 1, 2, 2, 2, 3, 3]

正如您从输入中看到的，迭代次数已从7172减少到283

现在，首先要评估的路径是：

[0]
[1]
[2]
[3]
[0, 0]
[0, 1]
[0, 2]
[0, 3]
[1, 1]
[1, 2]
[1, 3]
[2, 2]
[2, 3]
[3, 3]
[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 0, 3]

---

已编辑

二次优化

第二个优化可以是考虑存在“循环”路径：例如，在按下第四个按钮四次（路径[3,3,3,3]）后，您将处于相同的状态。要考虑到这一点，一个简单的方法是保存一个已经遇到的状态列表。如果您再次处于这种状态，您可以忽略它，因为它不会提供更好的解决方案（通过此循环路径到达解决方案的路径总是更长）：

def brute_force_opt2(start_state, inc_array, goal_state):
    iterations=0
    encoutered_states = set()
    leafNodes = deque([Node([], start_state)])
    while True:
        node = leafNodes.popleft()
        min_button = node.path[-1] if len(node.path) else 0
        for button in range(min_button, 4):
            new_state = apply_button(node.state, inc_array, button)
            if tuple(new_state) not in encoutered_states:
                iterations+=1
                new_path = node.path + [button]
                # print(new_path)
                if new_state==goal_state:
                    print(f"iterations: {iterations}")
                    return new_path
                leafNodes.append(Node(new_path, new_state))
                encoutered_states.add(tuple(new_state))

print(brute_force_opt2(start_state,incArray,[2, 3, 3, 4]))
# OUTPUT:
# iterations: 213
# [0, 1, 2, 2, 2, 3, 3]

如您所见，迭代次数现在只有182次。正如所料，该数字低于唯一状态的最大数量（4^4=256）

分析方法

假设这个问题的复杂性会大得多（例如更多的按钮和颜色），蛮力的方法可能不可行，你可以考虑一种更具分析性的方法，例如，计算每个按钮必须增加多少次（模4）。从开始状态转到结束状态，并找到满足所有按钮要求的按钮单击组合