6

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

我正在为所有打开的节点使用优先队列 [使用数组]。由于我将有重复的距离，即不止一个具有相同距离/优先级的节点，因此在 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) 和在那之后直接去。

为什么在距离的前半部分使用这种曲折路径，当我的目的地是 (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;
  }
}
4

1 回答 1

3

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

疑问：第一种和第二种计算方式有何不同？

第一个将较低的优先级放在转弯的移动上。第二个将较低优先级放在转弯较多的路径上。在某些情况下（例如，第一个转弯），该值将是相同的，但总的来说，第二个将选择具有尽可能少转弯的路径，而第一个可能没有。

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?

Yes

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

Yes, exactly. You want to not look at choices that have a turn in them first. This will make them lower priority and your algorithm will investigate other options with a higher priority -- exactly what you want.

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 –</p>

No, I don't understand this question -- I don't think it makes sense in this context -- all moves have to abut the previous cell, diagonal moves are not allowed.

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. :) 

Not so easy without seeing the details of your algorithm but the following might work:

enter image description here

The red are blocks. The green is what I would expect the first one to do, it locally tries to find the least turn. The blue is the least turn solution. Note, how far the red areas are from each other and the details of how your algorithm influence if this will work. As I have it above -- having an extra turn only costs 1 in the heuristic. SO, if you want to be sure this will work change the heuristic like this:

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

Where 25 is bigger than the distance to get past the 2nd turn in the green path. (Thus after the 2nd turn the blue path will be searched.)

于 2013-03-30T23:37:31.900 回答