实现A*算法
所以我用C语言实现了A*算法，下面是程序。
对于所有打开的节点，我使用了使用数组的优先级队列。由于我将有重复的距离，即多个节点具有相同的距离/优先级，因此在PQ中插入节点时，如果所插入节点的父节点具有相同的优先级，我仍然交换这两个节点，以便最新输入的成员保持在顶部(或尽可能高)，以便我继续沿着特定的方向前进。此外，在删除时，当我将最上面的元素与最后一个元素交换时，如果交换的最后一个元素与它的一个子元素相同，那么它将被交换到底部。(我不确定这是否会有任何影响)。
现在的问题是，假设我有一个100*100的矩阵，我有从(0,20)到(15,20)的2D阵列的障碍物，我正在其中移动。现在对于开始位置(2,2)和结束位置(16,20)，我得到了一条直线，即首先一直向右走，然后向下走到15，然后向右移动一次，我就完成了。
但是，如果我从(2,2)开始，最后作为(12,78)，即点被障碍物隔开，路径必须绕过它，我仍然通过(16,20)，并且我在(16,20)之后的路径仍然是直的，但我向上到(16,20)的路径是Z字形的，即我向下直走，然后向右，然后向下，然后向右，依此类推，最终到达(16,20)，然后直走。
当我的目的地是(16,20)而不是(12,78)时，我可以做些什么来确保我的路径是笔直的，为什么前半段的路径是Z字形的？
谢谢。
void findPath(array[ROW][COLUMN],sourceX,sourceY,destX,destY) {
PQ pq[SIZE];
int x,y;
insert(pq,sourceX,sourceY);
while(!empty(pq)) {
remove(pq);
if(removedIsDestination)
break; //Path Found
insertAdjacent(pq,x,y,destX,destY);
}
}
void insert(PQ pq[SIZE],element){
++sizeOfPQ;
PQ[sizeOfPQ]==element
int i=sizeOfPQ;
while(i>0){
if(pq[i].priority <= pq[(i-1)/2].priority){
swapWithParent
i=(i-1)/2;
}
else
break;
}
}
回答 1
Stack Overflow用户
发布于 2013-03-30 23:37:32
你应该改变你的计分部分。现在你可以计算绝对距离。而是计算最小移动距离。如果你把每一次移动都算作一次，那么如果你在(x，y)并去(dX，dY)，那就是
distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY))较低的值被视为较高的分数。
这个试探法是对如果没有任何阻碍的情况下它会采取多少步的猜测。
启发式的好处是你可以改变它来得到你想要的结果，例如，如果你更喜欢按照你的建议在直线上移动，那么你可以做这样的改变：
= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY))
+ (1 if this is a turn from the last move)这将使您“找到”倾向于同一方向的解决方案。
如果你想强迫尽可能少的转弯：
= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY))
+ (1 times the number of turns made)这就是A*的好处--启发式将通知搜索--你仍然会找到一个解决方案，但如果有不止一个解决方案，你可以影响你首先看哪里--这使得它很适合模拟AI行为。
怀疑:第一种计算方法和第二种计算方法有什么不同？
第一个将较低的优先级放在一个转弯的走法上。第二种方法在转弯较多的道路上设置较低的优先级。在某些情况下(例如，第一个转弯)，数值将是相同的，但在所有第二个转弯路径中，会选择转弯尽可能少的路径，而第一个转弯路径可能不会。
另外，如果这是上一步的转弯，假设我的源在左上角，目标在右下角，现在我的路径通常是，left，left，left...down，down，down....。现在，如果这是上一步的转弯，根据这个，当我从左转到下，我会加1吗？
是
不会使总价值更大，而向下的优先级将会降低。
是的，完全正确。你不想先看那些有转折的选择。这将使它们具有较低的优先级，并且您的算法将研究具有较高优先级的其他选项--这正是您想要的。
当我移动到一个单元格时，如果这是从上一步开始的一个转弯，那是不是与之前处理过的单元格相邻？
或1？唐克斯-
不，我不理解这个问题--我认为在这种情况下没有意义-，所有的移动都必须与前一个单元相邻，对角线移动是不允许的。
，如果你能告诉我第一个和第二个方法会给出不同的答案，我会非常感激。如果可以的话。非常感谢。：)：
如果看不到算法的细节就不是那么容易了，但以下方法可能会起作用：
红色的是积木。果岭是我希望第一个人做的，它在当地试图找到最少的转弯。蓝色是最小转数的解决方案。请注意，红色区域彼此之间有多远，以及算法如何影响这一点的细节。正如我上面所说的--在启发式中，多转一圈只需要花费1。所以，如果你想确保这个方法能正常工作，就像下面这样修改启发式：
= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY))
+ (25 times the number of turns made)其中25大于通过绿色小路第二个转弯的距离。(因此，在第二个转弯后，将搜索蓝色路径。)
https://stackoverflow.com/questions/15724563
复制
腾讯云开发者
