随机优先搜索？

Question

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

• 创建一个工作清单W,用起始节点s播种.
• 虽然工作清单不是空的:
  • 删除工作清单的第一个元素; 叫它v.
  • 如果没有访问v:
    • Mark v as visited.
    • 对于直接连接到v的每个节点,将u添加到W.

在广度优先搜索中,工作列表W实现为FIFO队列,而在深度优先搜索中,它是LIFO堆栈.如果W是优先级队列,则会获得统一成本搜索.

不久前,我问了一个关于从包中选择随机元素的数据结构的问题.如果您使用此随机包实现上述工作清单W,那么您将获得一个"随机优先搜索"算法,该算法从初始节点开始随机探索图中的节点.

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

Answer 1

自动拼图生成是一种应用,随机优先搜索是一种有用的策略.

假设您希望生成像Sudoku这样的组合拼图的实例.一种方法是生成随机的,完全求解的实例,然后只要还有唯一的解决方案就删除数字.你如何首先生成随机求解的实例？您从空网格开始并应用随机优先求解算法.实际上,通过在随机优先和最佳优先策略之间切换来选择要尝试的下一个数字,证明在生成和解决方案中使用相同的代码相当容易.

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

另见使用随机Prim算法讨论迷宫生成的答案.