gpt4 book ai didi

c++ - 递归算法的代码逻辑错误

转载 作者:塔克拉玛干 更新时间:2023-11-03 08:27:07 25 4
gpt4 key购买 nike

我有一个 A* 算法的结构,定义如下:

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

我把这个结构做了一个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 |

可能是一些逻辑错误,但我找不到它,有人可以帮助我吗?

--编辑--用户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);
}
}
}

提前致谢。

最佳答案

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

| 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是“空”。但是用patashu的话来说,“这将是非常低效的”。

该算法甚至与 A* 相差甚远,而且很难看出如何将其变成 A*。 A* 是广度优先搜索,需要您以交错方式执行多条路径。我非常建议从头开始。

关于c++ - 递归算法的代码逻辑错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16431105/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com