Алгоритм поиска A*
A* - это набор шагов (алгоритм), который компьютер может использовать, чтобы определить, как быстро добраться между двумя местами. Если у вас есть список мест и информация о том, как трудно добраться из одного места прямо в другое, использование A* может быстро подсказать вам самый быстрый путь. Он связан с алгоритмом Дейкстры, но делает умные предположения, чтобы не тратить много времени на медленные способы. Это хорошая серия шагов, если вам нужен только путь между двумя местами. Если вы хотите найти много путей по одной карте, то есть более быстрые способы, которые находят все ответы сразу, например, алгоритм Флойда-Уоршалла. A* не будет работать, если вы хотите посетить несколько мест за одну поездку (задача "Путешествие коммивояжера").
Шаги
A* сначала нужен список всех мест, куда вы можете поехать, а затем - список расстояний между каждым из них. Затем он скажет вам, как быстрее всего добраться из места A в место Z.
Для примера скажем, что A соединен с местами B и C, а B и C соединены с D и E. D и E соединены с Z. Существует 4 возможных пути из A в Z. Вы можете пойти A-B-D-Z, A-C-D-Z, A-B-E-Z или A-C-E-Z. Компьютер, использующий A*, сначала смотрит, насколько трудно добраться из A в B и из A в C. Это и есть "стоимость" для этих мест. Стоимость места означает, насколько трудно добраться от А до этого места. Записав обе стоимости, компьютер смотрит, насколько трудно добраться из B в D, и прибавляет их к стоимости B. Он записывает это как стоимость D. Затем компьютер смотрит, насколько трудно добраться из C в D, и добавляет это к стоимости C. Это уже другая стоимость для D, и если она меньше, чем та, которая уже есть, он заменит старую. Компьютер хочет знать только лучший путь, поэтому он игнорирует путь с большей стоимостью. Он запомнит только один из A-B-D и A-C-D, в зависимости от того, какой из них быстрее.
Компьютер продолжает и находит самый быстрый способ добраться до E. Наконец, он переходит от D к Z и находит стоимость, и от E к Z и находит стоимость. Он получает окончательную стоимость для Z, и это самая маленькая стоимость, которую он может получить. Теперь компьютер знает, какой путь самый быстрый, и у него есть ответ. Компьютер может проделать аналогичную серию шагов, но с гораздо большим количеством мест. Каждый раз он будет рассматривать место, ближайшее к A, и суммировать затраты для соседей этого места.
Люди называют вышеупомянутую серию шагов алгоритмом Дейкстры. Алгоритм Дейкстры может быть медленным, потому что он просматривает множество мест, которые могут идти не в ту сторону от Z. Если вы спросите компьютер, как добраться из одного города в соседний, алгоритм Дейкстры может оказаться в другом штате.
A* устраняет эту проблему. A* позволяет вам сообщить компьютеру предположение о том, как далеко будет от каждого места до конца. Компьютер может использовать это предположение, чтобы приблизительно определить, сколько времени потребуется, чтобы добраться от определенного места до Z. Вместо того, чтобы просто выбрать место, ближайшее к A, он будет смотреть на то, которое, вероятно, будет иметь наименьшую общую стоимость. Он найдет этот итог, добавив стоимость к ожидаемому расстоянию. Таким образом, он может смотреть только в том направлении, где, вероятно, будет лучше. Нет ничего страшного в том, что предположение не идеально, но даже простое неверное предположение может заставить программу работать намного быстрее. Если вы пытаетесь найти путь между двумя местами в реальном мире, хорошей догадкой будет расстояние между ними по прямой. Реальный путь по дорогам будет длиннее, но это позволяет программе угадать его, и она не пойдет в неправильном направлении.
В литературе по математике или информатике эта догадка часто является функцией места и называется эвристикой. Каждое место - это вершина, а каждый путь между двумя местами - ребро. Это слова из теории графов.
