Как получить технику отступления, чтобы решить большие лабиринты? ⇐ C++

[Anonymous]

Я разрабатываю функцию отступления, чтобы решить лабиринт, данный матрицей 0 и 1. Проблема в том, что для небольших матриц он правильно находит самый короткий путь, но для матриц 15x15 или больше, он замораживает и ничего не делает. Я пробовал обрезку по -разному, но ничто не решило более крупные лабиринты. Я хочу сделать это с помощью техники отступления, хотя я знаю, что другие методы более эффективны. Есть 8 возможных направлений. < /P>
Когда он работает (для небольших лабиринтов, а не та, которые в примере). Статистика для количества посещаемых узлов, многообещающих и т. Д. Я также не думаю, что это правильно расчет времени выполнения. for (map::const_iterator it = steps_inc.begin(); it != steps_inc.end(); ++it) {
int nx = x + get(it->second); second);
maze_solve(data, nx, ny, visitado, caminoActual, mejorCamino, stats, profundidadActual + 1);
}
< /code>
Я также пробовал итеративное решение, без рекурсивного вызова, вот как я должен это сделать? Примером ввода, который не работает, будет: < /p>
15 15
1 0 0 1 1 1 1 0 0 0 0 0 1 1 0
1 0 0 1 0 1 0 0 1 1 1 0 0 0 1
0 1 0 1 0 1 0 0 1 1 0 1 0 0 0
1 0 0 1 0 1 0 0 0 1 0 1 0 0 1
1 0 0 1 0 1 0 0 1 1 0 1 0 0 0
1 1 1 1 0 1 0 0 1 1 0 1 0 0 1
1 0 0 0 0 1 0 0 0 1 0 1 0 0 0
1 0 1 1 1 1 0 0 1 1 0 1 0 0 1
0 0 1 1 0 0 0 0 1 1 0 1 0 0 1
1 1 1 0 0 1 1 1 1 0 0 1 0 0 0
1 0 0 0 1 0 0 0 0 0 0 1 0 0 0
1 0 0 0 0 1 0 0 1 1 1 1 1 1 1
1 1 1 1 1 0 0 0 1 1 0 0 0 0 0
1 0 0 1 1 0 0 1 0 1 0 1 1 1 1
0 1 1 0 0 0 1 0 1 1 1 1 1 1 1
< /code>
#include
#include
#include
#include
#include
#include
#include

using namespace std;

enum Step { N, NE, E, SE, S, SW, W, NW };

const map steps_inc = {
{N, {-1, 0}}, {NE, {-1, 1}}, {E, {0, 1}}, {SE, {1, 1}},
{S, {1, 0}}, {SW, {1, -1}}, {W, {0, -1}}, {NW, {-1, -1}}
};

const map stepCode = {
{N, 1}, {NE, 2}, {E, 3}, {SE, 4},
{S, 5}, {SW, 6}, {W, 7}, {NW, 8}
};

struct Data {
vector lab;
int filas, columnas;
};

//Statistics
struct Estadisticas {
int visitados = 0;
int explorados = 0;
int hojas = 0;
int noFactibles = 0;
int noPrometedores = 0;
};

//If a node is feasible
bool esFactible(int x, int y, const Data &data, const vector &visitado) {
return x >= 0 && x < data.filas && y >= 0 && y < data.columnas &&
data.lab[x][y] == '1' && !visitado[x][y];
}

//Solve maze using the backtracking technique
void maze_solve(const Data &data, int x, int y, vector &visitado,
vector
> &caminoActual, vector &mejorCamino,
Estadisticas &stats, int profundidadActual) {

stats.visitados++;

if (!esFactible(x, y, data, visitado)) {
stats.noFactibles++;
return;
}

visitado[x][y] = true;
caminoActual.emplace_back(x, y);
stats.explorados++;

if (x == data.filas - 1 && y == data.columnas - 1) {
stats.hojas++;
if (mejorCamino.empty() || caminoActual.size() < mejorCamino.size())
mejorCamino = caminoActual;
}
else if (!mejorCamino.empty() && caminoActual.size() >= mejorCamino.size()) {
stats.noPrometedores++;
}
else {
for (map::const_iterator it = steps_inc.begin(); it != steps_inc.end(); ++it) {
int nx = x + get(it->second);
int ny = y + get(it->second);
maze_solve(data, nx, ny, visitado, caminoActual, mejorCamino, stats, profundidadActual + 1);
}
}

caminoActual.pop_back();
visitado[x][y] = false;
}

int main(int argc, char *argv[]){
Data d;
d.filas=15;
d.columnas=15;
d.lab= { {'1', '0', '0', '1', '1', '1', '1', '0', '0', '0', '0', '0', '1', '1', '0'},
{'1', '0', '0', '1', '0', '1', '0', '0', '1', '1', '1', '0', '0', '0', '1'},
{'0', '1', '0', '1', '0', '1', '0', '0', '1', '1', '0', '1', '0', '0', '0'},
{'1', '0', '0', '1', '0', '1', '0', '0', '0', '1', '0', '1', '0', '0', '1'},
{'1', '0', '0', '1', '0', '1', '0', '0', '1', '1', '0', '1', '0', '0', '0'},
{'1', '1', '1', '1', '0', '1', '0', '0', '1', '1', '0', '1', '0', '0', '1'},
{'1', '0', '0', '0', '0', '1', '0', '0', '0', '1', '0', '1', '0', '0', '0'},
{'1', '0', '1', '1', '1', '1', '0', '0', '1', '1', '0', '1', '0', '0', '1'},
{'0', '0', '1', '1', '0', '0', '0', '0', '1', '1', '0', '1', '0', '0', '1'},
{'1', '1', '1', '0', '0', '1', '1', '1', '1', '0', '0', '1', '0', '0', '0'},
{'1', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0'},
{'1', '0', '0', '0', '0', '1', '0', '0', '1', '1', '1', '1', '1', '1', '1'},
{'1', '1', '1', '1', '1', '0', '0', '0', '1', '1', '0', '0', '0', '0', '0'},
{'1', '0', '0', '1', '1', '0', '0', '1', '0', '1', '0', '1', '1', '1', '1'},
{'0', '1', '1', '0', '0', '0', '1', '0', '1', '1', '1', '1', '1', '1', '1'} };
for(int i=0;i

Подробнее здесь: https://stackoverflow.com/questions/796 ... -mazes-too