algorithm - 随机优先搜索？

Question

遍历图的两种最常见的方法是 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>

Answer 1

自动拼图生成是一种应用，其中随机优先搜索是一种有用的策略。

假设您希望生成类似 Sudoku 的组合谜题实例.一种方法是生成一个随机的、完全求解的实例，然后在仍然存在唯一解的情况下删除数字。你如何首先生成那个随机解决的实例？您从一个空网格开始，然后应用随机优先 求解算法。事实上，事实证明，通过在随机优先和最佳优先策略之间切换来选择下一个数字，使用相同的代码生成和解决方案是相当容易的去尝试。

这正是我们在编写 Nintendo DS 游戏 Zendoku 时所做的，我写了 a detailed article about our approach .

另见 this answer讨论使用随机生成迷宫 Prim's algorithm .