python - 有没有办法在python中以特定索引顺序遍历列表
问题描述
好的,自从我在 python 中工作以来已经有很长时间了。但基本上我正在做经典的 8 拼图问题,所以给定一个字符串,例如“12-453786”,我的程序将它解决为所需的“12345678-”。我目前正在使用广度优先搜索来解决它,并在下面的示例中存储访问过的节点和来自的节点。但是,要跟踪路径或完成难题所需的实际移动量,我需要能够从已解决的元组开始,并通过我的元组列表追溯到开始状态
我正在考虑做某种 whilesolved != startstate 循环,但这不会完全奏效。
def breadth_first_search(puz):
qu = queue.Queue()
laststate=""
qu.put((puz, laststate))
startstate=puz
visited=[]
#visited[puz] = puz
while queue:
puz = qu.get()
visited.append(puz)
pos = puz[0].index('-')
nebs = neighborcells(pos)
#print(*visited)
if puz[0] == "12345678-":
break
else:
for i in nebs:
swapped=swap(puz,i,pos)
if swapped in visited:
pass #?
else:
qu.put((swapped, puz[0]))
#some sort of linked list like function to get the path of result to start
#here
访问节点示例(元组列表)
[('12-453786', ''),
('1-2453786', '12-453786'),
('12345-786', '12-453786'),
('-12453786', '1-2453786'),
('12-453786', '1-2453786'),
('1524-3786', '1-2453786'),
('1234-5786', '12345-786'),
('12345678-', '12345-786')]
这个特定谜题的预期结果应该是 2 步
解决方案
使用您当前的数据结构((nextState, prevState) 元组数组),您绝对可以回到开始状态,但这不会非常有效,因为您每次都必须扫描整个列表才能找到您的状态'重新寻找。相反,您可以使用简单的数据结构来存储 BFS 图。这样,当您到达最终状态时,您只需按照反向链接返回初始状态即可。
同样在您当前的代码中,您没有防范您之前访问过的状态,因此您可能会陷入无限循环的情况,而您的 while 循环将永远不会中断。
推荐阅读
- c - 静态内存可以延迟分配吗?
- r - 无法将变量转换为 ggplot 的因子
- apache-flink - flink 背压监控
- ignite - 处理选择器键失败后,点燃缓存失败...java.io.IOException: Broken pipe exception
- javascript - IONIC3 推送通知在 IOS DEVICE 中不起作用
- time-complexity - 循环调整的时间复杂度
- azure-devops - 如何将 apitoken 添加为自定义 VSTS 服务端点数据源的一部分?
- java - 将表示为货币的字符串值转换为普通浮点数或整数
- laravel-5.5 - 在 laravel 5.5 中注册一个新类型的用户
- angular - 如何提取 x.509 证书并以角度 2 显示其字段