Грокаем алгоритмы

Вам почти никогда не придется реализовать хеш-таблицу самостоятельно. Язык программирования, который вы используете, должен предоставить необходимую реализацию. Вы можете пользоваться хеш-таблицами Python, и при этом вам будет обеспечена производительность среднего случая: постоянное время.

Хеш-таблицы чрезвычайно полезны, потому что они обеспечивают высокую скорость операций и позволяют по-разному моделировать данные. Возможно, вскоре выяснится, что вы постоянно используете их в своей работе.

• Хеш-таблица создается объединением хеш-функции с массивом.

• Коллизии нежелательны. Хеш-функция должна свести количество коллизий к минимуму.

• Хеш-таблицы обеспечивают очень быстрое выполнение поиска, вставки и удаления.

• Хеш-таблицы хорошо подходят для моделирования отношений между объектами.

• Как только коэффициент заполнения превышает 0,7, пора изменять размер хеш-таблицы.

• Хеш-таблицы используются для кэширования данных (например, на веб-серверах).

• Хеш-таблицы хорошо подходят для обнаружения дубликатов.

6. Поиск в ширину

В этой главе

• Вы научитесь моделировать сети при помощи новой абстрактной структуры данных — графов.

• Вы освоите поиск в ширину — алгоритм, который применяется к графам для получения ответов на вопросы вида «Какой кратчайший путь ведет к X?»

• Вы узнаете, чем направленные графы отличаются от ненаправленных.

• Вы освоите топологическую сортировку — другой алгоритм сортировки, раскрывающий связи между узлами.

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

(BFS, Breadth-First Search).

Поиск в ширину позволяет найти кратчайшее расстояние между двумя объектами. Однако сам термин «кратчайшее расстояние» может иметь много разных значений! Например, с помощью поиска в ширину можно:

• написать программу для игры в шашки, которая вычисляет кратчайший путь к победе;

• реализовать проверку правописания (минимальное количество изменений, преобразующих ошибочно написанное слово в правильное, например АЛГОРИФМ -> АЛГОРИТМ — одно изменение);

• найти ближайшего к вам врача.

Одни из самых полезных алгоритмов, известных мне, работают с графами. Внимательно прочитайте несколько следующих глав — этот материал неоднократно пригодится вам в работе.

Знакомство с графами

Предположим, вы находитесь в Сан-Франциско и хотите добраться из Твин-Пикс к мосту Золотые Ворота. Вы намереваетесь доехать на автобусе с минимальным количеством пересадок. Возможные варианты:

Какой алгоритм вы бы использовали для поиска пути с наименьшим количеством шагов?

Можно ли сделать это за один шаг? На следующем рисунке выделены все места, в которые можно добраться за один шаг.

Мост на этой схеме не выделен; до него невозможно добраться за один шаг. А можно ли добраться до него за два шага?

И снова мост не выделен, а значит, до него невозможно добраться за два шага. Как насчет трех шагов?

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

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

Чтобы найти кратчайший путь из Твин-Пикс к мосту Золотые Ворота, нам пришлось выполнить два шага:

1. Смоделировать задачу в виде графа.

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

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

Что такое граф?

Граф моделирует набор связей. Представьте, что вы с друзьями играете в покер и хотите смоделировать, кто кому сейчас должен. Например, условие «Алекс должен Раме» можно смоделировать так:

А полный граф может выглядеть так:

Граф задолженностей при игре в покер

Алекс должен Раме, Том должен Адиту и т.д. Каждый граф состоит из узлов и ребер.

Вот и все! Графы состоят из узлов и ребер. Узел может быть напрямую соединен с несколькими другими узлами. Эти узлы называются соседями. На этом графе Рама является соседом Алекса. С другой стороны, Адит соседом Алекса не является, потому что они не соединены напрямую. При этом Адит является соседом Рамы и Тома.