Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Вторая книга (Графовые алгоритмы и структуры данных) из серии Совершенный алгоритм Тима Рафгардена является продолжением, по сути, единого цикла лекций. Автор не только сохранил стиль первой книги, но и часто ссылается на материал, который был в ней преподнесён. Стиль обоих книг я считаю очень удачным. А именно, детальное и всестороннее изложение небольшого количества тем доступным языком.
Снова, это не каталог решений, а именно лекции. Поэтому автор далеко не сразу дает готовые алгоритмы. По сути, автор рассказывает как к этим алгоритмам можно прийти. Либо пробуя разные варианты, либо постепенно улучшая решения. Так например, поиск кратчайшего пути:
Начинается с обхода в ширину
Вводится модификация со взятием кратчайшего ребра при обходе
Показывается, почему это не работает на отрицательных длинах, и доказывается, почему работает на неотрицательных
Приводится анализ временной сложности
Ставится задача быстрого поиска рёбер с минимальной длиной
Вводится понятие кучи, необходимые на ней операции и их (желаемая) временная сложность
Разбирается зачем и почему мы можем хранить в куче вершины, а не рёбра
Приводятся детальные примеры где ещё такую структуру с такими операциями и их характеристиками можно было бы применить
Даётся идея о реализации кучи в виде двоичного дерева
Объясняется как её улучшить, перейдя к представлению в виде массива
Детально иллюстрируется нарушение инварианта при вставке и удалении и поясняется как его восстановить
Автор не разбирает как изначально собрать кучу за линейное время (можно посмотреть, например, и код, и анализ в An average case analysis of Floyd’s algorithm to construct heaps за авторством Ernst E. Doberkat от 1984 года), не приводит готовый код вставки и удаления, не приводит финальный готовый код реализации алгоритма поиска кратчайшего пути от начала до конца. Здесь это оставлено в виде задач. Но, если сравнивать с готовым решением в Грокаем алгоритмы, то, по крайней мере, в Совершенный алгоритм понятно откуда что взялось, почему и как; поиск минимумов с линейного заменён на логарифмический.
Очень скудно рассмотрено представление графов в виде матриц смежности. Недостаточно и информации чтобы с места написать балансировку деревьев или фильтр Блума. Но повторю вывод для первой части и здесь: если, чтение Кнута - это Труд, то Совершенный алгоритм - это просто интересное и увлекательное чтение.
Полное оглавление можно посмотреть на сайте издательства: тут.
