标签: tree-search

有关DFS,A*人工智能搜索的图搜索和树搜索版本有什么区别？

我正在写一个分布式的Go/Gomoku机器人.

基本上,重点是将树搜索分发到许多计算机上.使用像DFS这样的基本树搜索算法,这将非常简单,因为我可以将搜索空间划分为子树.虽然我宁愿拥有更高效的东西,比如使用alpha-beta修剪的mini-max - 但是根据我的理解,没有任何共享内存它是毫无意义的.所以我有点卡住了.

任何想法我可以使用哪种算法高效且易于分发？更重要的是,我在哪里可以找到一些(伪)代码或者可能实现？

谢谢,

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

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

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

编辑：更准确地说，我正在谈论知情树搜索算法。

我试图总结所有路径,通过一个树,从根到最低的孩子,每个级别扩展1到10倍.我的函数遍历所有孩子,但我遇到的问题是,当我尝试创建节点列表并在列表中执行此列表时,我成为列表列表的List ...列表.我认为我的问题是组合步骤我尝试制作模式匹配方法,但是当它成为列表列表时应该比较列表的方法,并且应该创建新列表并比较它们,如果它只是一种方式(符合列表)使用节点而不是带列表的列表)不起作用.

我正在尝试使用不同的算法来解决问题,而Steepest Ascent Hill Climbing(SAHC)和Best First Search是我需要实现的两种算法.

根据维基百科:

"在最陡峭的登山攀登中,所有后继者都进行了比较,并选择了最接近解决方案......"

"最陡峭的登山攀爬类似于最佳优先搜索,它尝试所有可能的当前路径扩展,而不是只有一个."

SAHC:比较所有后继者,并选择最接近解决方案.
BestFS:尝试当前路径的所有可能扩展,而不是只有一个.

我真的不明白这些是如何不同的.有些人可以帮我解决这个问题,最好是用树木做一些解释吗？

任何节点都可以包含任意数量的子节点.为了搜索这棵树我写了这样的东西

function Search(key, nodes){

 for (var i = 0; i < nodes.length; i++) {


        if (nodes[i].key == key) {
            return nodes[i];
        }



        if (nodes[i].hasOwnProperty('children')) {
            return this.Search(key, nodes[i].children);
        }


    }

哪个不太有效...任何输入？