小编Bab*_*bak的帖子

我正在用曼哈顿距离实现一个星型算法来解决8-puzzle(在C中).它似乎工作得非常好并且通过了大量的单元测试,但是在一个案例中找不到最短路径(它找到了27个步骤而不是25个步骤).

当我将启发式函数更改为汉明距离时,它会找到25个步骤.当我使曼哈顿距离函数返回实际成本的一半时,还可以找到25个步骤.

这就是为什么我认为这个问题存在于曼哈顿距离函数的某个地方,并且它过度估算成本(因此不可接受).我想在C程序中可能还有别的东西出错了,所以我写了一个小的Python脚本来测试和验证曼哈顿距离函数的输出,它们都产生完全相同的结果.

我真的很困惑,因为启发式函数似乎是唯一的失败点,它似乎同时是正确的.

你可以试试这个求解器,然后像"2,6,1,0,7,8,3,5,4"这样选择格式顺序.选择算法曼哈顿距离,它可以找到25步.现在将其更改为曼哈顿距离+线性冲突,它会找到27个步骤.

但我的曼哈顿距离(没有线性冲突)分为27步.

这是我的一般算法:

manhattan_distance = 0
iterate over all tiles
if the tile is not the blank tile:
find the coordinates of this tile on the goal board
manhattan_distance += abs(x - goal_x) + abs(y - goal_y)

我认为如果某些重要部分出现了严重错误,那么它将无法通过所有25个以上的测试,因此这可能是某种边缘情况.

这里评论C中的曼哈顿距离函数:

int ManhattanDistance(Puzzle p, State b){
   State goal = getFinalState(p);
   int size = getSize(b);
   int distance = 0;
   if (getSize(goal) == size){ // both …

假设我们有一个DIRECTED,WEIGHTED和CYCLIC图表.

假设我们只对总重量小于MAX_WEIGHT的路径感兴趣

找到总重量小于MAX_WEIGHT的两个节点A和B之间的不同路径数量的最合适(或任何)算法是什么？

PS:这不是我的功课.只是个人的非商业项目.

for a in map:
    for b in map[a]:
        for c in map[b]:
            for d in map[c]:
                for e in map[d]:
                    print a+b+c+d+e

上面的代码用于在图形中创建一定长度的所有路径.map [a]表示从a点可以到达的点.

如何更改它以模拟具有任意数量的循环？

这就像笛卡尔积(itertools.product),在每次迭代中,您对下一个元素的选择仅限于map [current_point]中的选择.

我正在做一项任务,我必须使用一颗星来解决一个15谜题(在C中).

启发函数是曼哈顿距离(又名出租车距离).

我们给出了一个示例输入/输出,其中电路板在22次移动中和扩展395个节点(电路板状态)后解决(即我们必须查看395个节点的子节点)

通过'正确'启发式,我的意思是我的功能与用于产生样本输出的功能相同并产生正确的距离.

问题是我的解决方案扩展了超过400个节点以找到解决方案(它是最佳的22个移动而不是另一个).

我注意到数字的变化取决于我生成子节点的顺序(向上,向左,向下,向右或其他方向移动空间区域).

有24种方法可以向上,向下,向左和向右移动空间磁贴以生成子项,我尝试了所有这些,但它们都没有扩展395个节点.

为什么会这样？

术语:

• node:每个节点都是15-puzzle board的配置
• children:通过从当前节点向上,向下,向左或向右移动空间磁贴可以实现的配置

PS:如果重要的话,我正在使用二进制堆作为开放列表

谢谢