1

我有一个 A* 算法的结构，它定义为：

typedef struct matriz{
    int g,h,f;
    bool isBarrier, isStart, isEnd;
}matrix;

我用这个结构制作了一个矩阵，并将所有初始值设为 0。

matrix n[8][8];

然后我做了一个算法来计算起始位置到当前位置之间的距离。

为此，我使用了递归方法，因为步骤将是到达该位置所需的步数，每次计算另一个位置时都会增加：

bool checkbounds(int x, int y){
    if(x>=0 && x<=totalsize-1){
        if(y>=0 && y<=totalsize-1) return true;
    }
    return false;
}

bool isGNull(int x, int y){
    if(n[x][y].g==0)return true;
    return false;
}

void countg(int x, int y, int steps){
    if(checkbounds(x-1,y)){
        if(isGNull(x-1,y)){
            n[x-1][y].g=steps;
            countg(x-1,y,steps+1);
        }
    }
    if(checkbounds(x,y-1)){
        if(isGNull(x,y-1)){
            n[x][y-1].g=steps;
            countg(x,y-1,steps+1);
        }
    }
    if(checkbounds(x+1,y)){
        if(isGNull(x+1,y)){
            n[x+1][y].g=steps;
            countg(x+1,y,steps+1);
        }
    }
    if(checkbounds(x,y+1)){
        if(isGNull(x,y+1)){
            n[x][y+1].g=steps;
            countg(x,y+1,steps+1);
        }
    }
}

问题是它应该在返回递归时返回到初始步骤值。

预期的结果应该是这样的：

| 5  4  3  2  3  4  5  6 |
| 4  3  2  1  2  3  4  5 |
| 3  2  1  S  1  2  E  6 |
| 4  3  2  1  2  3  4  5 |
| 5  4  3  2  3  4  5  6 |
| 6  5  4  3  4  5  6  7 |
| 7  6  5  4  5  6  7  8 |
| 8  7  6  5  6  7  8  9 |

其中 S 是起始位置，E 是结束位置。

但我得到的是：

| 5  4  3  2 35 36 53 54 |
| 6 19 20  1 34 37 52 55 |
| 7 18 21  S 33 38  E 56 |
| 8 17 22 31 40 39 50 57 |
| 9 16 23 30 41 48 49 58 |
|10 15 24 29 42 47 60 59 |
|11 14 25 28 43 46 61 64 |
|12 13 26 27 44 45 62 63 |

可能是一些逻辑错误，但我很难找到它，有人可以帮助我吗？

--EDIT-- 用户 Elazar 对算法的大小进行了一定的改进，但仍然给出与以前相同的结果。

bool checkbounds(int x, int y) {
    return 0 <= x && x < totalsize
        && 0 <= y && y < totalsize;
}

void countg(int _x, int _y, int steps) {
    static int d[] = {-1, 0, 1, 0};
    for (int i = 0; i < 4; i++) {
        int x = _x+d[i], y = _y+d[3-i];
        if (checkbounds(x,y) && n[x][y].g==0) {
            n[x][y].g=steps;
            countg(x,y,steps+1);
        }
    }
}

提前致谢。

4

3 回答 3

6

您的递归算法将向上游荡，然后向左，然后向下，然后向右，标记到目前为止它已经行进的距离。再次查看数字，您可以看到它所走的路线。

| 5 <4 <3 <2 35 36 53 54 |
  v        ^
| 6 19>20  1 34 37 52 55 |
  v  ^  v  ^
| 7 18 21  S 33 38  E 56 |
  v  ^  v
| 8 17 22 31 40 39 50 57 |
  v  ^  v
| 9 16 23 30 41 48 49 58 |
  v  ^  v
|10 15 24 29 42 47 60 59 |
  v  ^  v
|11 14 25 28 43 46 61 64 |
  v  ^  v
|12>13 26>27 44 45 62 63 |

然后，当它最终到达右下角时，它会展开堆栈并且不会继续前进，因为一切都有一个数字。这称为深度优先搜索。

最简单的更改是更改您的算法以使其实际工作是检查当前steps是否比上一个短steps，而不是前一个是否steps为“null”。但用patashu的话来说，“这将是非常低效的”。

这个算法甚至远不接近 A*，而且很难看出它是如何变成一个的。A* 是广度优先搜索，需要您以交错的方式执行多个路径。我非常建议从头开始。

于 2013-05-08T01:25:40.180 回答
2

不是答案，但它刺痛了我的眼睛：

bool checkbounds(int x, int y) {
    return 0 <= x && x < totalsize
        && 0 <= y && y < totalsize;
}

void countg(int _x, int _y, int steps) {
    static int d[] = {-1, 0, 1, 0};
    for (int i = 0; i < 4; i++) {
        int x = _x+d[i], y = _y+d[3-i];
        if (checkbounds(x,y) && n[x][y].g==0) {
            n[x][y].g=steps;
            countg(x,y,steps+1);
        }
    }
}
于 2013-05-08T01:24:15.437 回答
1

您正在执行深度优先而不是广度优先搜索（请注意，它需要从 1 到 64 的一条长路径，然后从不尝试其他任何东西）递归搜索。意思是你一直沿着第一条路径行进，尝试每一个单元格，然后在完成之后你尝试下一个方向，从单元格一个向上，然后一个单元格向上，一个单元格向上......起始单元格，而且每次你​​都找不到别的地方去。

这不太适合递归编码，IMO。相反，您应该保留尚未检查邻居的所有单元格的数据结构（在 A* 术语中称为开放集）并不断

1）检查开放集中是否有任何东西（否则你就完成了）

2）否则选择最佳路径的最佳候选者（迄今为止的最低成本+如果使用一个，则最低允许启发式）并检查其所有邻居 - 您从中创建或改进的每条路径，添加到开放集

于 2013-05-08T01:26:36.047 回答