遍历图形的两种最常用方法是breadth-first search和depth-first search . 这两种搜索算法都遵循一个通用模板：
-
创建一个工作清单W，用起始节点s播种 .
-
虽然工作清单不是空的：
-
删除工作清单的第一个元素;叫它v .
-
如果未访问v：
-
Mark v as visited .
-
对于直接连接到v的每个节点，将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，那么您将获得一个"random-first search"算法，该算法从初始节点开始随机探索图中的节点 .
我的问题是这样的： are there any known algorithms that use this type of search? 也就是说，是否存在以这种方式生成图形的随机生成树的算法？
5 回答
Automatic puzzle generation 是随机优先搜索是一种有用策略的应用程序 .
假设您希望生成像Sudoku这样的组合拼图的实例 . 一种方法是生成随机的，完全求解的实例，然后删除数字，只要还有唯一的解决方案 . 你如何首先生成随机求解的实例？您从空网格开始并应用随机优先求解算法 . 实际上，通过在随机优先和最佳优先策略之间切换来选择要尝试的下一个数字，证明在生成和解决方案中使用相同的代码相当容易 .
这正是我们在编写任天堂DS游戏Zendoku时所做的，我写了a detailed article about our approach .
另见this answer使用随机化Prim's algorithm讨论迷宫生成 .
这恰好是给定随机启发式的最佳优先搜索的实现 .
我没有't know if there'是您描述的特定算法的名称 . 听起来有点像simulated annealing . 在优化理论中，还有random search的概念，但它确实依赖于评估函数，而你所描述的也不是Bachelor's Thesis by Brodeur and Childs，它对图搜索的随机算法有一个很好的总结，包括讨论何时可能使用它们 .
听起来你正试图在BFS和DFS之间取得 balancer . 这出现在游戏编程中，其中使用修剪来缩小宽度，以便可以在深度上花费更多周期 . 一些示例是迭代加深深度优先搜索和最佳第一搜索 . 起点可以在这里找到：http://en.wikipedia.org/wiki/Alpha-beta_pruning#Other_algorithms
查看A* . 您可以将启发式函数调整为最适合您数据的任何内容 - 有点像moooeeeep的答案，但有更多细节和维基百科链接 . 如果你想要一个具有随机性的启发式，那么你可以写一个 .
通常图形具有某种结构，并且以结构化方式搜索它们是有意义的（如果您正在寻找路径，那么搜索连接到已搜索的另一个节点的节点是有意义的，而不是一个可能断开连接的随机节点 . ）大多数时候我在有向无环图/ DAG或树上运行这些算法（连接DAG） . 如果我的数据中没有任何逻辑结构，我通常不会尝试从中制作图形，然后将图论应用于它 . 我想这取决于你想要事物的随机性 .
祝好运！