1

我输入了这样的地图：

int map_w = 40;
int map_h = 20;
char map[20][40] = {
    {'c', 'c', 'c', 'c', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'c', 'c', 'n', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'n', 'h', 'n', 'n'},
    {'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'c', 'n', 'n', 'h', 'h', 'n'},
    {'c', 'c', 'c', 'c', 'n', 'c', 'n', 'n', 'c', 'c', 'h', 'n', 'n', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'n'},
    {'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'n', 'c', 'n', 'n', 'h', 'h', 'h', 'h', 'n', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'h', 'h', 'n'},
    {'h', 'h', 'h', 'h', 'c', 'c', 'c', 'n', 'c', 'c', 'h', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'n', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h'},
    {'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'n', 'c', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'c', 'h', 'h', 'n', 'h', 'n', 'h', 'n'},
    {'n', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'h', 'h', 'n', 'h', 'h', 'h', 'h'},
    {'c', 'c', 'n', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'h', 'h', 'h', 'p', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h'},
    {'c', 'c', 'n', 'c', 'n', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'h', 'h', 'h', 'h', 'n', 'h'},
    {'c', 'c', 'c', 'n', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'h', 'p', 'h', 'h', 'h'},
    {'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'h', 'h', 'c', 'n', 'n', 'n', 'c', 'c', 'c', 'd', 'c', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'h', 'h', 'h', 'h', 'h', 'h'},
    {'c', 'c', 'n', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'h', 'c', 'h', 'h', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'h', 'h', 'h', 'h', 'n', 'h', 'n', 'c', 'h', 'h', 'h', 'h', 'h', 'h'},
    {'c', 'c', 'n', 'n', 'c', 'n', 'c', 'n', 'c', 'n', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'h', 'n', 'c', 'h', 'h', 'n', 'h', 'n', 'h'},
    {'n', 'c', 'c', 'n', 'c', 'n', 'n', 'n', 'c', 'n', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'c', 'c', 'n', 'c', 'h', 'h', 'h'},
    {'n', 'c', 'n', 'n', 'c', 'n', 'c', 'n', 'c', 'p', 'h', 'h', 'h', 'n', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'h', 'n', 'c', 'c', 'c', 'n', 'c', 'h', 'h', 'h'},
    {'n', 'n', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'h', 'h', 'c', 'h', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'h', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'n', 'n', 'h', 'h', 'n'},
    {'n', 'n', 'n', 'c', 'c', 'n', 'n', 'n', 'c', 'h', 'h', 'c', 'h', 'n', 'c', 'h', 'n', 'n', 'c', 'n', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'n', 'n', 'c', 'c', 'n', 'h', 'h', 'n'},
    {'n', 'n', 'n', 'n', 'n', 'n', 'c', 'c', 'c', 'h', 'h', 'h', 'h', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'n', 'n', 'c'},
    {'n', 'n', 'c', 'c', 'n', 'c', 'n', 'n', 'h', 'h', 'h', 'h', 'h', 'c', 'c', 'n', 'c', 'h', 'h', 'h', 'h', 'h', 'h', 'c', 'n', 'n', 'n', 'c', 'n', 'n', 'n', 'c', 'n', 'n', 'n', 'c', 'n', 'n', 'c', 'n'},
    {'c', 'c', 'c', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'c', 'n', 'c', 'c', 'c', 'c', 'c', 'c', 'n', 'n', 'n', 'c', 'n', 'n', 'c', 'n', 'c', 'c', 'n', 'n', 'n', 'n', 'n'}
};

这是地图的外观： http://i.snag.gy/GyCOD.jpg

数组中的字符与每个正方形相对应，也就是说，灰色是 h，这是一块石头，我不能这样走。棕色是正常路径（c），长度为 1 绿色是森林（n），长度为 2

然后是d作为龙和p作为公主，我必须先找到通往龙的最短路径，然后再找到公主，然后返回确切的最短路径..

所以我的第一个问题是，有没有办法把这个输入放到一些修改过的 Dijkstra、Bellman-Ford 或一些不同的算法中？或者我必须首先为每个正方形建立一个连接，从正方形 1,2 我可以到 1,1 并且长度是 2，到 2,2 并且长度是 2，或者我可以简单地通过某种方式运行算法双数组？？

问题 2 您建议使用哪种算法？我想到了贝尔曼福特，虽然我没有负平方，但我需要返回确切的路径，这很容易感谢数组 pi，它在贝尔曼福特中维护，但我愿意接受任何建议，因为我刚刚进入图论。

4

3 回答 3

4

我建议你仔细看看A*。

这是查找路径的一种简单而有效的方法，尤其是在 2D 网格中。

于 2013-11-22T14:38:21.080 回答
2

好吧，Bellman-Ford 和 Dijkstra 算法在这里都是多余的，因为边的权重都为 1。
请注意，您可以为权重 = 2 的情况创建辅助顶点，因此使用权重为 1,2 的边 -你将有更多的顶点和边，但是所有的 wight 1，基本上这是通过将表单中的边替换(u,v,2)为：(u,u',1)和(u',v,1)- 对于每条边的权重为 2。
请注意，在最坏的情况下，它会给你4|V|顶点和4|E|边，所以它当涉及到大 O 表示法时，不会改变时间复杂度。

在这样的图中（未加权/所有边的权重相同），BFS有效地解决了问题，并且比 BF 和 Dijkstra 的算法更容易编程。

另一种选择是具有曼哈顿距离启发式函数的A* 算法，或双向搜索，这通常比大规模的普通 BFS 更快。

PS，请注意，您可以通过创建一个next:V->(2^V x R)函数“即时”创建图形，对于给定的 vertex v，其结果next(v)将是其所有连接和权重。通过这样做，您实际上可以动态创建您需要的图形部分，而不是在一些预处理期间，

假设您有以下情况，并假设 2 的成本是您搬到森林（而不是从森林）。

     a  b
     ____
1:   c  h
2:   n  c

在这里，你有边（在原始图中）：

((1,a),(2,a),2), ((2,a),(1,a),1), ((2,a),(2,b),1), ((2,b),(2,a),2)


通过应用我建议您得到的修改：6 个边缘而不是 4 个，并且想法是您得到边缘 ((1,a),(1_2,a_a),1) ((1_2,a_a),(2,a),1)而不是((1,a),(2,a),2)，并且类似地对于((2,b),(2,a),2).

现在，在这里，您的next()功能将是：

next(1,a) = [((1_2,a_a),1)]
next(1_2,a_a) = [(2,a),1)] //dummy nodes also need an output...
next(2,a) = [((1,a),1), ((2_2,a_b),1] //two nodes in here, because you can move to 2 nodes.
next(2_2,a_b) = [((2,b),1)]
next(2,b) = [((2,a),1)]

请注意，由于问题似乎规模很小，而且用您自己的话来说，您是初学者——我认为应用 BFS 将是解决您问题的最佳解决方案。完成后，您将能够改进为更有效的算法 - 但 IMO，您应该从最简单的算法开始，即 BFS。

于 2013-11-22T14:44:03.217 回答
1

如果要将地图明确表示为图形，则必须识别每个节点的子节点。因此，您可以通过编程方式填充该显式表示：每个节点 (i>0,j) 连接到 (i-1,j)，(i,j>0) 连接到 (i,j)，(i

于 2013-11-22T14:44:19.213 回答