15 СЕНТЯБРЯ
В этой главе
✓ Вы научитесь моделировать сети при помощи новой абстрактной структуры данных — графов.
Вы освоите поиск в ширину — алгоритм, который применяется к графам для получения ответов на вопросы вида «Какой кратчайший путь ведет к X?»
Вы узнаете, чем направленные графы отличаются от ненаправленных.
Вы освоите топологическую сортировку — другой алгоритм сортировки, раскрывающий связи между узлами.
Эта глава посвящена графам. Сначала вы узнаете, что такое граф. Затем я покажу первый алгоритм, работающий с графами. Он называется поиском в ширину (BFS, Breadth-First Search).
Поиск в ширину позволяет найти кратчайшее расстояние между двумя объектами. Однако сам термин «кратчайшее расстояние» может иметь много разных значений! Ь1апример, с помощью поиска в ширину можно:
□ написать программу для игры в шашки, которая вычисляет кратчайший путь к победе;
реализовать проверку правописания (минимальное количество изменений, преобразующих ошибочно написанное слово в правильное, например АЛГОРИФМ -> АЛГОРИТМ — одно изменение);
найти ближайшего к вам врача.
Одни из самых полезных алгоритмов, известных мне, работают с графами. Внимательно прочитайте несколько следующих глав — этот материал неоднократно пригодится вам в работе.
Знакомство с графами
Предположим, вы находитесь в Сан-Франциско и хотите добраться из Твин-Пикс к мосту Золотые Ворота. Вы намереваетесь доехать на автобусе с минимальным количеством пересадок. Возможные варианты;
Какой алгоритм вы бы использовали для поиска пути с наименьшим количеством шагов?
Можно ли сделать это за один шаг? На следующем рисунке выделены все места, в которые можно добраться за один шаг.
Мост на этой схеме не выделен; до него невозможно добраться за один шаг. А можно ли добраться до него за два шага?
И снова мост не выделен, а значит, до него невозможно добраться за два шага. Как насчет трех шагов?
Ага! На этот раз мост Золотые Ворота выделен. Следовательно, чтобы добраться из Твин-Пикс к мосту по этому маршруту, необходимо сделать три шага.
Есть и другие маршруты, которые приведут вас к мосту, но они длиннее (четыре шага). Алгоритм обнаружил, что кратчайший путь к мосту состоит из трех шагов. Задача такого типа называется задачей поиска кратчайшего пути. Часто требуется найти некий кратчайший путь: путь к дому вашего друга, путь к победе в шахматной партии (за наименьшее количество ходов) и т. д. Алгоритм для решения задачи поиска кратчайшего пути называется поиском в ширину.
Чтобы найти кратчайший путь из Твин-Пикс к мосту Золотые Ворота, нам пришлось выполнить два шага:
Смоделировать задачу в виде графа.
Решить задачу методом поиска в ширину.
В следующем разделе я расскажу, что такое графы. Затем будет рассмотрен более подробно поиск в ширину.
Что такое граф?
Г раф моделирует набор связей. Представьте, что вы с друзьями играете в покер и хотите смоделировать, кто кому сейчас должен. Например, условие «Алекс должен Раме» можно смоделировать так:
А
Do'stlaringiz bilan baham: |