0

我已经实现了 AIMA 中定义的 RBFS，并希望将其与 A* 的实现进行比较。当我在 TSPlib（ulyssis16 - 16 个城市）的实例上试用它时，两者都提出了正确的解决方案，内存使用也是正确的（A* 为指数，RBFS 为线性）。唯一奇怪的是，RBFS 算法在不应该的情况下比 A* 快得多。A* 大约在 3.5 分钟内完成，RBFS 只需几秒钟。当我计算每个节点的访问次数时，A* 访问的节点比 RBFS 多得多。这似乎也违反直觉。

这是因为微不足道的例子吗？我不能在更大的实例上尝试它，因为我的计算机没有足够的内存。

有没有人有任何建议？根据它们的规范、结果和内存使用情况，这两种算法似乎都是正确的。只有执行时间似乎关闭了......

我已经到处找了，但找不到任何关于他们的搜索策略有什么不同的地方。除了 RBFS 可以重新访问节点这一事实。

谢谢

碧玉

编辑 1：AIMA 对应于 Russel 和 Norvig 的《Artificial Intelligence a Modern Approach》一书。编辑 2：TSPlib 是 TSP 问题的一组实例（http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/) 编辑 4：A* 算法的代码如下。这应该是正确的。def graph_search(problem, fringe): """搜索一个问题的后继者以找到一个目标。参数边缘应该是一个空队列。如果两条路径达到一个状态，只使用最好的一个。[图 3.18] """ closed = {} fringe.append(Node(problem.initial)) while fringe: node = fringe.pop() if problem.goal_test(node.state): 如果 node.state 不在关闭状态，则返回节点：已关闭 [ node.state] = True fringe.extend(node.expand(problem)) return None

def best_first_graph_search(problem, f):
    return graph_search(problem, PriorityQueue(f,min))

def astar_graph_search(problem, h):
    def f(n):
        return n.path_cost + h(n)
    return best_first_graph_search(problem, f)

其中问题是一个变量，包含有关要解决的问题的详细信息（达到目标时，如何生成后继者，初始状态......）。一个节点包含如何通过存储父节点和一些其他效用函数来达到该状态的路径。这是此代码的旧版本http://aima-python.googlecode.com/svn/trunk/search.py​​ ）对于 TSP 问题，旅游是增量创建的。使用的启发式是尚未访问的节点上的最小生成树。

RBFS的代码如下： def rbfs(problem, h): def f(n): return n.path_cost + h(n)

    def rbfs_helper(node, bound):
        #print("Current bound: ", bound)

        problem.visit(node)

        if (problem.goal_test(node.state)):
            return [node, f(node)]

        backup = {}
        backup[node.state.id] = f(node)

        succ = list(node.expand(problem))

        if (not succ):
            return [None, float("inf")]

        for v in succ:
            backup[v.state.id] = max(f(v), backup[node.state.id])

        while(True):
            sortedSucc = sorted(succ, key=lambda node: backup[node.state.id])

            best = sortedSucc[0]

            if (backup[best.state.id] > bound):
                return [None, backup[best.state.id]]

            if (len(sortedSucc) == 1):
                [resultNode, backup[best.state.id]] = rbfs_helper(best, bound)
            else:
                alternative = sortedSucc[1]
                [resultNode, backup[best.state.id]] = rbfs_helper(best, min(bound, backup[alternative.state.id]))

            if (resultNode != None):
                return [resultNode, backup[best.state.id]]

    [node, v] = rbfs_helper(Node(problem.initial), float("inf"))

    return node

它还使用上面定义的问题和节点。这些是专门设计用作通用元素的。

4

0 回答 0