c - 实现A*算法

Question

所以我在 C 中实现 A* 算法。这是过程。

我正在为所有开放节点使用优先级队列 [使用数组]。由于我将有重复的距离，即不止一个节点具有相同的距离/优先级，因此在 PQ 中插入一个节点时，如果插入节点的父级具有相同的优先级，我仍然交换它们，以便我最新的输入的成员保持在顶部(或尽可能高)，以便我继续遵循特定的方向。此外，在删除时，当我将最顶部的元素与最后一个元素交换时，如果交换的最后一个元素与其子元素之一相同，则它会被交换到底部。(我不确定这是否会影响以任何方式)。

现在的问题是说我有一个 100*100 矩阵，我在二维数组的 (0,20) 到 (15,20) 之间有障碍物，我在其中移动。现在对于起始位置 (2,2) 和结束位置 (16,20)，我得到一条直线路径，即首先一直向右走，然后向下走直到 15，然后向右移动一个，我就完成了。

但是，如果我从 (2,2) 开始并以 (12,78) 结束，即这些点被障碍物隔开并且路径必须绕过它，我仍然会经过 (16,20) 和我在 (16,20) 之后的路径仍然是直的，但是我到 (16,20) 的路径是曲折的，即我直线向下走一段距离，然后向右走一段距离，然后向下再向右走，依此类推，最终到达 (16, 20) 然后直接走。

为什么前半段距离是曲折路径，当我的目的地是 (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;
  }
}

Answer 1

你应该改变你的计分部分。现在你计算绝对距离。而是计算最小移动距离。如果你把每一步都算作一个，那么如果你在 (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)

这将使您“找到”趋于相同方向的解决方案。

如果你想 FORCE 的次数越少越好:

= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) 
     + (1 times the number of turns made)

这就是 A* 的优点——启发式算法会为搜索提供信息——你仍然总能找到一个解决方案，但如果有多个解决方案，你可以影响你首先寻找的位置——这对模拟 AI 行为。

---

Doubt : How is the first one and second calculating way different from each other?

第一个将转弯的 Action 放在较低的优先级上。第二个将较低的优先级放在转弯较多的路径上。在某些情况下(例如，第一个转弯)该值将相同，但总体而言，第二个将选择转弯次数尽可能少的路径，而第一个转弯可能不会。

Also, 1 if this is a turn from the last move , for this, say i have source at top left and destination at bottom right, now my path normally would be, left,left,left...down,down,down.... Now, 1 if this is a turn from the last move, according to this, when I change from left to down, will I add 1?

是

Wont it make the total value more and the priority for down will decrease.

是的，没错。你不想先看有转机的选择。这将使它们的优先级降低，而您的算法将调查具有更高优先级的其他选项——这正是您想要的。

Or 1 if this is a turn from the last move is when I move to a cell, that is not abutting the cell previously worked upon? Thnks –

不，我不明白这个问题——我认为在这种情况下它没有意义——所有移动都必须紧靠前一个单元格，不允许对角线移动。

---

Though, I'd really appreciate if you could tell me one instance where the first and second methods will give different answers. If you could. Thanks alot. :) 

如果不了解您的算法的细节就不是那么容易，但以下可能会起作用:

红色的是方 block 。绿色是我希望第一个做的，它在本地尝试找到最少的转弯。蓝色是最少转的解决方案。请注意，红色区域彼此之间的距离以及您的算法如何影响它是否有效的详细信息。正如我在上面所说的那样——在启发式中多转一圈只需要花费 1。所以，如果您想确保这会起作用，请像这样更改启发式:

= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) 
     + (25 times the number of turns made)

其中 25 大于通过绿色路径中第 2 个转弯的距离。 (因此在第 2 轮之后将搜索蓝色路径。)