Page 131 - Bkhargava_-_Grokaem_algoritmy

130 Глава 6. Поиск в ширину

Ага! На этот раз мост Золотые Ворота выделен. Следовательно, чтобы до­
браться из Твин-Пике к мосту по этому маршруту, необходимо сделать три
шага.

Есть и другие маршруты, которые приведут вас к мосту, но они длиннее
(четыре шага). Алгоритм обнаружил, что кратчайший путь к мосту состоит
из трех шагов. Задача такого типа называется задачей поиска кратчайшего
пути. Часто требуется найти некий кратчайший путь: путь к дому вашего
друга, путь к победе в шахматной партии (за наименьшее количество ходов)
и т. д. Алгоритм для решения задачи поиска кратчайшего пути называется
поиском в ширину .
Чтобы найти кратчайший путь из Твин-Пике к мосту Золотые Ворота, нам
пришлось выполнить два шага:
1. Смоделировать задачу в виде графа.

2. Решить задачу методом поиска в ширину.

В следующем разделе я расскажу, что такое графы. Затем будет рассмотрен
более подробно поиск в ширину.

www.trk.kg