随机优先搜索？

Question

遍历图的最常见方法是广度优先搜索和深度优先搜索。这两种搜索算法都遵循一个通用模板：

• 创建一个工作列表W，以起始节点s为种子。
• 当工作列表不为空时：
  • 删除工作列表的第一个元素；将其称为v。
  • 如果v未被访问：
    • 标记v已访问。
    • 对于每个直接连接到v的节点u，将u添加到W中。

在广度优先搜索中，工作列表W以FIFO队列的形式实现，而在深度优先搜索中，它是一个LIFO堆栈。如果W是优先队列，则可以得到一致代价搜索。

不久前，我问过有关从袋子中选择随机元素的数据结构的问题。如果使用此随机袋子实现上述工作列表W，则会得到一种“随机优先搜索”算法，该算法从初始节点开始随机探索图中的节点。

我的问题是：是否有任何已知算法使用这种类型的搜索？也就是说，是否有通过以这种方式生成图的随机生成树来工作的算法？

- templatetypedef

---

维基百科关于“迷宫生成算法”的文章提到了DFS的随机化版本。 - miku

我很好奇是什么促使你想出这个方案的。 - MAK

Answer 1

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

假设您想生成一个组合拼图实例，如Sudoku。一种方法是生成一个随机的、完全解决的实例，然后删除数字，只要仍然有唯一的解决方案。那么如何在第一次生成随机解决方案时生成它？您从一个空网格开始，应用一个随机优先求解算法。事实上，通过在选择下一个要尝试的数字时在随机优先和最佳优先策略之间切换，使用相同的代码来进行生成和解决证明是相当容易的。

这正是我们写任天堂DS游戏Zendoku时所做的，我写了一篇关于我们方法的详细文章。

另请参见这个答案，讨论使用随机化Prim算法生成迷宫。

- Gareth Rees

Answer 2

这正是在给定随机启发式的情况下最佳优先搜索的实现。

- moooeeeep

Answer 3

我不知道你所描述的具体算法是否有名称。它听起来有点像模拟退火算法。在优化理论中，还有一个随机搜索的概念，但它确实依赖于评估函数，而你所描述的似乎没有。此外，这篇Brodeur和Childs的学士论文对图搜索的随机算法进行了很好的总结，包括讨论何时可以使用它们。

- Ted Hopp

---

虽然这些搜索算法都很好，但它们都有一定的信息量，即使是你提供链接中的那个论文中的算法也是如此。我主要对随机且完全不知情的搜索感兴趣。但还是谢谢！ - templatetypedef

@templatetypedef - 也许你已经发现了一种新的搜索算法。这使得你有了命名权！我可以建议使用“Bumble Around Algorithm”吗？ :) - Ted Hopp

Answer 4

看看A*。你可以调整启发式函数，使其最适合你的数据 - 类似于moooeeeep的答案，但更详细，并带有维基百科链接。如果你想要一个具有随机性的启发式函数，那么你可以编写一个。

通常，图形具有某种结构，以结构化的方式搜索它们是有意义的（如果你正在寻找一条路径，则搜索已经搜索过的另一个节点连接的节点，而不是可能断开连接的随机节点）。大多数时候，我在有向无环图/ DAG或树上运行这些算法（连接DAG）。如果我的数据中真的没有任何逻辑结构，我通常不会尝试将其制作成图形，然后将图形理论应用于它。我想这取决于你想让事情变得多么随机。

祝你好运！

- Brian Stinar

Answer 5

听起来你正在尝试在 BFS 和 DFS 之间寻求平衡。这在游戏编程中很常见，其中修剪用于缩小广度，以便可以在深度上花费更多的周期。一些例子是迭代加深深度优先搜索和最佳优先搜索。可以在这里找到一个起点：http://en.wikipedia.org/wiki/Alpha-beta_pruning#Other_algorithms。

- Paul Jackson