4

我注意到我遇到的一些“硬”组合问题可以用某种类型的树搜索（如 alpha-beta 剪枝、束搜索或类似算法）进行转换。 然而，对它们进行编程似乎是重复编码相同的东西，而且很容易出错。在我看来应该有一个实现这些算法的库，而我应该被要求写的是

  1. 解决方案的编码，即如何从不完整的解决方案中获得更具体的解决方案。这将给出树/图结构。
  2. 给定一个部分解决方案，如何获得最大/最小成本，以及可能的成本估算。
  3. 初始解决方案/部分解决方案。
  4. 也许某种验证解决方案。

很抱歉我没有给出任何具体的代码，但我想我已经解释了这个问题。如果我可以为上述功能编写代码，我是否应该能够轻松地运行许多树/图搜索算法？是否有任何用户友好的库/框架可以轻松支持这一点？我希望它使用 Python 或 C/C++，但很想听听任何建议。

编辑：更准确地说，我说的是知情树搜索算法。

4

5 回答 5

2

快速图

对于任何愿意使用 .Net 的人，请查看用于所有基于图形/树的处理的开源 QuickGraph 库。它巧妙地将与图形表示、算法、变异和表示相关的所有概念分开。它有很多扩展点，因此它应该能够支持大多数图形可转换问题。

[编辑] QuickGraph 提供的算法集目前不包括 alpha-beta 修剪或束搜索，尽管它的“搜索”算法部分包括 11 种其他方法，这些方法为实现您最喜欢的遍历算法提供了充足的指导，并且及时我可以想象它会支持 alpha-beta 和光束。

广告。1 它确实满足您的第一个标准，因为可以插入一个委托函数，该函数基于不完整的解决方案（即当前节点）返回几个更具体的解决方案（即相邻节点）。这是由DelegateImplicitGraph（和变体）处理的，并且应该是内存效率的，因为它可以防止一次将整个搜索空间放在内存中。 广告。2此外，算法可以采用自定义委托，例如最大/最小/预期成本启发式（请参阅 参考资料AStarShortestPathAlgorithm）。这满足您的第二个标准。

总之，QuickGraph 可以帮助您构建问题，为各种类型的问题提供插入式算法，并允许您通过提供新算法来改进它。

于 2011-04-09T21:33:06.323 回答
1

在不指定具体步骤的情况下表达问题是一种声明式编程。

您谈论“部分解决方案”。这是否意味着您正在考虑的问题具有重叠的子问题？如果是这样，那么听起来您正在寻求一种方法来进行一般动态编程。真正的意思是通过连续的步骤构建一个函数，解决问题的更简单版本，然后迭代。这篇Mathematica 期刊文章中有一些很好的例子。

你考虑过Prolog吗？它不是一个框架，但如果您愿意，搜索算法是内置在语言中的。可以使用像 Prolog 这样的东西作为基础来编写非常通用的约束编程解决方案。在 Python 中有python-constraint 库，它非常好——我过去使用过它。

于 2011-04-08T17:10:58.043 回答
1

Fuego 是一个开源的蒙特卡罗树搜索（相对于 alpha-beta 树搜索）平台，可以针对 2 人全信息游戏（最初是针对围棋创建的）。它甚至可能比这更普遍。

http://fuego.sourceforge.net/

编辑：我刚刚了解到它还具有一个 alpha-beta 搜索器。这是最近的一篇论文： http ://webdocs.cs.ualberta.ca/~mmueller/ps/fuego-TCIAIG.pdf

于 2011-04-09T22:50:22.060 回答
1

Boost 有Boost Graph Libary (BGL)。Boost Graph Library User's Guide 有一个关于使用隐式图的 Knight's tour 问题的示例。

于 2011-04-04T13:07:04.113 回答
0

我在网上找到了 Peter Norvig 的 Python 代码，用于知情和不知情的搜索。它支持 A-star 搜索，并且可以用于针对我所看到的一般问题进行编程。我想知道它是否足够快或者可以扩展到波束搜索、分支和绑定等。

于 2011-04-09T19:30:40.493 回答