相关疑难解决方法(0)

我正试图找到一个叫做Twiddle的小益智游戏的最佳解决方案(这个游戏的applet可以在这里找到).游戏有一个3x3矩阵,数字从1到9.目标是使用最少的移动量使数字按正确的顺序排列.在每次移动中,您可以顺时针或逆时针旋转2x2方格.

即如果你有这种状态

6 3 9
8 7 5
1 2 4

然后顺时针旋转左上方的2x2方形

8 6 9
7 3 5
1 2 4

我正在使用A*搜索找到最佳解决方案.我的f()只是所需的旋转次数.我的启发式功能已经导致最佳解决方案(如果我修改它,请参见最后的通知),但我不认为这是你能找到的最好的解决方案.我当前的启发式获取每个角落,查看角落处的数字并计算到该数字在解决状态下将具有的位置的曼哈顿距离(这给出了将数字带到此位置所需的旋转次数)并将所有数量相加这些价值观.即你采取上面的例子:

6 3 9
8 7 5
1 2 4

这个结束状态

1 2 3
4 5 6
7 8 9 

然后启发式做了以下事情

6 is currently at index 0 and should by at index 5: 3 rotations needed
9 is currently at index 2 and should by at index 8: 2 rotations needed
1 is currently at index 6 …

我最近做了第三版Dijkstra算法,将单一来源的最短路径附加到我的项目中.

我意识到有许多不同的实现在性能上有很大差异,并且在大图中的结果质量也有所不同.使用我的数据集(> 100.000个顶点),运行时间从20分钟到几秒不等.最短路径也变化1-2%.

你知道哪个是最好的实现？

编辑: 我的数据是一个液压网络,每个节点有1到5个顶点.它可以与街道地图相媲美.我对已经加速的算法做了一些修改(使用所有剩余节点的排序列表),现在在一小部分时间内找到相同的结果.我已经搜索了这样的事情了很长一段时间.我想知道这样的实现是否已经存在.

我无法解释结果的细微差别.我知道Dijkstra不是启发式的,但所有的实现似乎都是正确的.更快的解决方案具有更短路径的结果.我只使用双精度数学.

编辑2: 我发现找到的路径的差异确实是我的错.我已经为某些顶点插入了特殊处理(仅在一个方向上有效),并在其他实现中忘记了这一点.

但是我仍然惊讶于Dijkstra可以通过以下变化大幅加速:一般来说Dijkstra算法包含一个循环,如:

MyListType toDoList; // List sorted by smallest distance 
InsertAllNodes(toDoList);
while(! toDoList.empty())
{
    MyNodeType *node = *toDoList.first();
    toDoList.erase(toDoList.first());
    ...
}

如果你稍微改变一下,它的工作方式相同,但表现更好:

MyListType toDoList; // List sorted by smallest distance 
toDoList.insert(startNode);
while(! toDoList.empty())
{
    MyNodeType *node = *toDoList.first();
    toDoList.erase(toDoList.first());
    for(MyNeigborType *x = node.Neigbors; x != NULL; x++)
    {
        ...
        toDoList.insert(x->Node);
    }
}

看起来,这种修改通过不是数量级的顺序来减少运行时间,而是指数的顺序.它将我的运行时形式从30秒减少到小于2.我在任何文献中都找不到这种修改.同样非常清楚的是,原因在于排序列表.插入/擦除在100.000元素的情况下执行得更糟糕.

回答:

经过大量的谷歌搜索后,我发现了自己.答案很清楚: boost graph lib.太棒了 - 我有一段时间没有找到这个.如果您认为Dijkstra实现之间没有性能差异,请参阅维基百科.