实现A*算法
所以我在C中实现A*算法.这是程序.
我正在为所有开放节点使用Priority Queue [using array].由于我将有重复的距离,这是多个具有相同距离/优先级的节点,因此在PQ中插入节点时,如果插入节点的父节点具有相同的优先级,我仍然将它们交换,以便我最新输入的成员保持在顶部(或尽可能高),以便我继续遵循特定的方向.另外,在删除时,当我将最顶层的元素与最后一个元素交换时,再次,如果交换的最后一个元素与其中一个子元素相同,那么它将被交换到底部.(我不确定这是否会影响以任何方式).
现在的问题是我有一个100*100矩阵,我有2D阵列的(0,20)到(15,20)的障碍,我正在移动.现在对于一个起始位置(2,2)和结束位置(16,20),我得到一条直线路径,即首先一直向右走,然后向下走到15,然后向右移动一个,我就完成了.
但是,如果我以(2,2)开始并且最后以(12,78)开始,即点被障碍物分开并且路径必须绕过它,我仍然经过(16,20)和我的路径之后(16,20)仍然是直的,但是我的路径(16,20)是曲折的,即我向下走了一段距离,然后向右走了一段距离,然后向下向右走,依此类推,最终达到(16,20)在那之后直奔.
为什么这个zig zag路径为距离的前半部分,我可以做些什么来确保我的路径是直的,因为它是,当我的目的地是(16,20)而不是(12,78).
谢谢.
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;
}
}
你应该改变你的评分部分。现在您计算绝对距离。相反，计算最小移动距离。如果您将每次移动算作一次，那么如果您位于 (x,y) 并前往 (dX,dY) 那将是
\n\ndistance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY))\n较低的值被认为是较高的分数。
\n\n这种启发法是猜测如果没有任何障碍，需要进行多少次移动。
\n\n\n\n
启发式的好处是您可以更改它以获得您想要的结果，例如，如果您更喜欢按照您的建议沿直线移动，那么您可以进行以下更改：
\n\n= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) \n + (1 if this is a turn from the last move)\n这将使您“找到”趋于相同方向的解决方案。
\n\n如果你想强制尽可能少的转弯：
\n\n= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) \n + (1 times the number of turns made)\n这就是 A* 的优点——启发式方法会通知搜索——你仍然总会找到解决方案，但如果有多个解决方案，你可以影响你首先看的地方——这使得它有利于模拟人工智能行为。
\n\n\n\n
\n\n\n疑问：第一种和第二种计算方式有何不同？
\n
第一个对回合移动的优先级较低。第二个在转弯较多的路径上设置较低的优先级。在某些情况下（例如，第一个转弯），该值将是相同的，但总的来说，第二个将选择转弯尽可能少的路径，而第一个可能不会。
\n\n\n\n\n另外，1如果这是从上一步开始的一个回合，为此，\n说我的源位于左上角，目的地位于右下角，现在我的\n路径通常是，左，左，左...下，下，下....现在，1如果\n这是从上一步开始的一个回合，根据这个，当我从左到下改变\n时，我会加1吗？
\n
是的
\n\n\n\n\n是不是总价值变多了，down的优先级就会降低。
\n
对，就是这样。你不想首先考虑那些有轮流发生的选择。这将使它们的优先级降低，并且您的算法将研究具有更高优先级的其他选项 - 正是您想要的。
\n\n\n\n\n或者 1 如果这是从上一次移动开始的一个回合，那么当我移动到一个单元格时，它不与之前处理过的单元格相邻？谢谢\xe2\x80\x93
\n
不，我不明白这个问题 - 我认为在这种情况下没有意义 - 所有移动都必须紧邻前一个单元格，不允许对角线移动。
\n\n\n\n
\n\n\n不过，如果您能告诉我第一种方法和第二种方法会给出不同答案的一个实例，我将非常感激。如果你可以。多谢。:)\xc2\xa0
\n
如果不查看算法的详细信息，事情就不那么容易了，但以下方法可能有效：
\n\n
红色是块。绿色是我期望第一个做的，它在本地尝试找到最少的转弯。蓝色是最少转弯的解决方案。请注意，红色区域彼此之间的距离有多远，以及您的算法如何影响该算法是否有效的详细信息。正如我上面所说的——在启发式中，额外的回合只花费 1。所以，如果你想确保这会起作用，请像这样改变启发式：
\n\n= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) \n + (25 times the number of turns made)\n其中 25 大于通过绿色路径第二个转弯的距离。（因此在第二回合后将搜索蓝色路径。）
\n