A * pathfinding slow

Question

В настоящее время я работаю над алгоритмом поиска A *. Алгоритм просто решал бы лабиринты текстовых файлов. Я знаю, что алгоритм A * должен быть очень быстрым в поиске финиша. Кажется, что у меня осталось 6 секунд, чтобы найти путь в лабиринте 20x20 без стен. Он находит финиш с правильным путем, который просто требуется навсегда, чтобы сделать это.

Если бы я знал, какая часть кода была проблемой, я бы просто опубликовал ее, но я действительно не знаю, что происходит не так. Так вот алгоритм, который я использую ...

while(!openList.empty()) { 
    visitedList.push_back(openList[index]); 
    openList.erase(openList.begin() + index); 

    if(currentCell->x_coor == goalCell->x_coor && currentCell->y_coor == goalCell->y_coor)   
    } 
     FindBestPath(currentCell); 
     break; 
    } 

    if(map[currentCell->x_coor+1][currentCell->y_coor] != wall) 
    { 
    openList.push_back(new SearchCell(currentCell->x_coor+1,currentCell->y_coor,currentCell)); 
    } 
    if(map[currentCell->x_coor-1][currentCell->y_coor] != wall) 
    { 
     openList.push_back(new SearchCell(currentCell->x_coor-1,currentCell->y_coor,currentCell)); 
    } 
    if(map[currentCell->x_coor][currentCell->y_coor+1] != wall) 
    { 
     openList.push_back(new SearchCell(currentCell->x_coor,currentCell->y_coor+1,currentCell)); 
    } 
    if(map[currentCell->x_coor][currentCell->y_coor-1] != wall) 
    { 
     openList.push_back(new SearchCell(currentCell->x_coor,currentCell->y_coor-1,currentCell)); 
    } 

    for(int i=0;i<openList.size();i++) { 
     openList[i]->G = openList[i]->parent->G + 1; 
     openList[i]->H = openList[i]->ManHattenDistance(goalCell); 
    } 

    float bestF = 999999; 
    index = -1; 

    for(int i=0;i<openList.size();i++) { 
     if(openList[i]->GetF() < bestF) { 
      for(int n=0;n<visitedList.size();n++) { 
       if(CheckVisited(openList[i])) { 
        bestF = openList[i]->GetF(); 
        index = i; 
       } 
      } 
     } 
    } 
    if(index >= 0) { 
     currentCell = openList[index]; 
    } 
} 

Я знаю, что этот код является грязным и не самым эффективным способом сделать вещи, но я думаю, что это все еще должно быть быстрее, чем это. Любая помощь будет принята с благодарностью.

Спасибо.

Answer 1

Ваш лабиринт 20x20 не имеет стен и, следовательно, много и много маршрутов, которые имеют одинаковую длину. На самом деле я бы оценил триллионы эквивалентных маршрутов. Это не так уж плохо, когда вы принимаете это во внимание.

Конечно, поскольку ваш эвристический дизайн выглядит идеально, вы должны получить большую выгоду от исключения маршрутов, которые, как предполагается, будут эвристически предсказаны как точно до тех пор, пока лучший маршрут известен до сих пор. (Это безопасно, если ваша эвристика правильная, т. Е. Никогда не переоценивает оставшееся расстояние).

Answer 2

Вы не всегда возвращаетесь назад?

Алгоритм A * отступает, когда текущее лучшее решение становится хуже, чем другой ранее посещаемый маршрут. В вашем случае, поскольку нет стен, все маршруты хороши и никогда не умирают (и, как правильно указали MSalters, их несколько). Когда вы делаете шаг, ваш маршрут становится хуже, чем все остальные, что на один шаг короче.

Если это так, это может занять время, затраченное на ваш алгоритм.

Answer 3

openList.erase О (п), а для цикла, начиная с for(int i=0;i<openList.size();i++) О (п^2) в связи с вызовом CheckVisited - их называют каждую итерацию, что делает ваш общий алгоритм O (N^3). A * должен быть O (n log n).

---

Попробуйте изменить openList к приоритетному очереди, как это должно быть, и visitedList в хэш-таблице. Целый цикл for можно заменить на dequeue - убедитесь, что вы проверяете, visitedList.Contains(node)до enqueuing!

Кроме того, нет необходимости пересчитывать ManHattenDistance для каждого узла на каждой итерации, так как он никогда не изменяется.

Answer 4

Вот большой совет.

Если вы когда-либо находите два пути в одну и ту же ячейку, вы всегда можете выбросить более длинную. Если есть галстук, вы можете выбросить второй, чтобы добраться туда.

Если вы реализуете это без каких-либо других оптимизаций, поиск станет более чем приемлемо быстрым.

Во-вторых, алгоритм A * должен только возвращать назад, если длина текущей ячейки плюс эвристика превышает длину текущей ячейки плюс эвристику для любого другого узла. Если вы реализуете это, тогда он должен непосредственно найти путь и остановиться. Чтобы облегчить вам сохранение путей в очереди приоритетов (как правило, с кучей), а не вектора.