遍历图的两种最常见的方法是 breadth-first search 和 depth-first search 。这两种搜索算法都遵循一个通用模板:
- 创建一个工作列表 W，以起始节点 s 为种子。
- 虽然工作列表不为空:
- 删除工作列表的第一个元素；称它为v。
- 如果 v 未被访问:
- 将 v 标记为已访问。
- 对于每个直接连接到 v 的节点 u，将 u 添加到 W。
在广度优先搜索中，工作列表 W 被实现为 FIFO queue ，而在深度优先搜索中它是 LIFO stack 。如果 W 是 priority queue ，你得到 uniform-cost search 。
不久前我问过 a question about a data structure for choosing random elements out of a bag 。如果您使用这个随机包实现上述工作列表 W，那么您将获得一个“随机优先搜索”算法，该算法从初始节点开始随机探索图中的节点。
我的问题是:是否有任何已知算法使用这种类型的搜索？也就是说，是否有通过以这种方式生成图的随机生成树来工作的算法？ p>
最佳答案
自动拼图生成是一种应用，其中随机优先搜索是一种有用的策略。
假设您希望生成类似 Sudoku 的组合谜题实例.一种方法是生成一个随机的、完全求解的实例，然后在仍然存在唯一解的情况下删除数字。你如何首先生成那个随机解决的实例？您从一个空网格开始，然后应用随机优先 求解算法。事实上，事实证明，通过在随机优先和最佳优先策略之间切换来选择下一个数字，使用相同的代码生成和解决方案是相当容易的去尝试。
这正是我们在编写 Nintendo DS 游戏 Zendoku 时所做的，我写了 a detailed article about our approach .
另见 this answer讨论使用随机生成迷宫 Prim's algorithm .
关于algorithm - 随机优先搜索？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8885920/