python - Python 按钮算法
问题描述
我目前正在尝试使用 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
- 全部递增 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
. 提前感谢您提供的任何帮助!
解决方案
我倾向于从“愚蠢”的蛮力算法开始开发这类算法,然后进一步优化它
蛮力
您可以通过一种广度优先搜索算法以“蛮力”方式实现这一点,您将在其中:
- 单击初始状态的所有按钮(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)从开始状态到结束状态并找到满足所有按钮的按钮点击组合。
推荐阅读
- php - Laravel PHP - 在选择列表中选择 db 中的 set 选项
- javascript - React - 从功能更改路线
- php - 仅针对某些用户和设备的 PHP 会话丢失
- asp.net - Azure AD 不记名令牌 - 获取用户标识符
- phpstorm - 使用代码编辑器更改文件时出现错误的意外标记:“”(第 1 列,代码点 U+0000)
- amazon-web-services - AWS Lambda 将图像写入 S3 访问被拒绝
- python - Sklearn 多个特征(多个自变量,结果 y 取决于)
- javascript - 如何在不分页的情况下抓取下一页
- excel - 使用 vlookup 参考使用 VBA 粘贴单元格颜色
- javascript - 应该使用新的数据库信息更新页面的 ajax 函数正在发挥应有的作用