如何使用算法解决绳桥问题？

Question

我在想这个吊桥问题是否可以用图形算法搜索来解决：

我的直觉告诉我应该使用深度优先搜索，但是如何定义状态呢？（也就是说，如果DFS是正确的方法。）

吊桥问题

- NickPoussin

Answer 1

这个任务需要手动完成，不使用计算机。

然而，如果将情况进行概括，我想可以通过图搜索来解决，但是应该考虑到图的大小。如果每个顶点代表“状态”，那么状态数估计为2^N⋅L，其中N是人数，L是手电筒的长度。每个状态都包含信息，每个人在哪一侧以及手电筒剩余时间。如果有从初始状态到所有人都在营地一侧的路径，那么这条路径就是解决方案。

这是创建状态的最明显的方式，但也许你可以用更有效的方法来做到这一点（当前状态数量和运行时间与输入大小呈指数关系）。

但是，对于像您提供的示例中那样小的规模，指数运行时间（使用图）是可以接受的。如果你建议编程解决方案而不是手动解决问题，面试官甚至可能会喜欢它。

- P Shved

---

手电筒的长度？？？我猜你指的是桥的长度或手电筒的运行时间。 - sharptooth

他的意思是手电筒剩余时间的长度（或者就像你所说的手电筒运行时间）。 - NickPoussin

谢谢 Pavel。你对状态的解释“每个状态包含信息，每个人在哪一侧以及手电筒剩余时间”对我帮助很大。我想明天我会尝试编程这个游戏来玩玩。 - NickPoussin

Answer 2

你可能想看一下EWD 1255。

- Pratik Deoghare

---

TheMachineCharmer，感谢提供链接，我觉得这是一篇有趣的阅读。如果我理解Dijkstra教授的意思正确的话，那么在吊桥问题中就没有“alpha”了。也许有，只是我没看到？ - NickPoussin

我刚刚发布了一些相关和有用的内容。将其制作成了c-wiki。 :D - Pratik Deoghare