Ошибка логики кода в рекурсивном алгоритме
У меня есть структура для алгоритма 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 |
Возможно, это какая-то логическая ошибка, но у меня возникли проблемы с ее поиском, может кто-нибудь мне помочь?
—РЕДАКТИРОВАТЬ—
Пользователь 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);
}
}
}
Заранее спасибо.
Решение
Сначала вы выполняете поиск по глубине, а не по ширине (обратите внимание, что требуется один длинный путь от 1 до 64, а затем больше ничего не пробует). Это означает, что вы путешествуете по первому пути, пробуя каждую отдельную клетку, затем, после того, как это сделано, вы пробуете следующее направление от клетки вверх, затем от клетки вверх, от клетки вверх … от начальной клетки , и каждый раз, когда вы не найдете другого места, чтобы пойти.
Это не очень хорошо подходит для рекурсивного кодирования, IMO. Вместо этого вам следует сохранять структуру данных всех ячеек, соседей которых вы еще не проверили (называйте это открытым набором, в терминологии A *), и постоянно
1) проверьте, есть ли что-нибудь в открытом наборе (иначе вы сделали)
2) иначе выберите лучшего кандидата на лучший путь (пока самая низкая стоимость + наименьшая допустимая эвристика при его использовании) и проверьте всех его соседей — каждый путь, который вы делаете из него или улучшаете, добавьте в открытый набор
Другие решения
Ваш рекурсивный алгоритм будет перемещаться вверх, затем влево, затем вниз, затем вправо, обозначая расстояние, которое он проделал до сих пор. Посмотрите снова на цифры, и вы можете увидеть маршрут, который он взял.
| 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 * — это поиск в ширину, требующий от вас выполнения нескольких путей с чередованием. Я очень рекомендую начинать все заново.
Не ответ, но это жжет мне глаза
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);
}
}
}