Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Благодарности. Многие читатели прислали мне исключительно полезные отзывы о предыдущих изданиях этой книги
|
|
Многие читатели прислали мне исключительно полезные отзывы о предыдущих изданиях этой книги. В частности, в течение ряда лет предварительные наброски книги апробировались на сотнях студентов в Принстоне и Брауне. Особую благодарность хотелось бы выразить Трине Авери и Тому Фримену за оказанную помощь в выпуске первого издания; Джанет Инсерпи за проявленные ею творческий подход и изобретательность, чтобы заставить аппаратные и программные средства нашей примитивной и давно устаревшей компьютеризированной издательской системы напечатать первое издание книги; Марку Брауну за его участие в исследованиях по визуализации алгоритмов, которые во многом способствовали появлению в книге многочисленных рисунков, а также Дэйву Хенсону и Эндрю Эппелю за их готовность ответить на мои вопросы, связанные с языками программирования. Я хотел бы также поблагодарить многочисленных читателей, приславших отзывы на различные издания этой книги, в том числе Гая Олмсу, Джона Бентли, Марка Брауна, Джея Гришера, Аллана Хейдона, Кеннеди Лемке, Юди Манбер, Дану Ричарде, Джона Рейфа, М. Роенфельда, Стивена Сейдмана, Майка Квина и Вильяма Варда.
При подготовке нового издания я имел удовольствие работать с Питером Гордоном, Дебби Лафферти и Хелен Гольштейн из издательства Addison-Wesley, которые терпеливо опекали этот проект с момента его зарождения. Большое удовольствие доставила мне совместная работа с другими штатными сотрудниками этого издательства. Характер проекта сделал подготовку издания данной книги несколько непривычной задачей для многих из них, и я высоко ценю проявленную ими снисходительность. В частности, Мэри-лин Рашш затратила немало усилий, чтобы втиснуть работу по изданию книги в жесткие временные рамки.
Предисловие
В процессе написания этой книги я приобрел трех новых наставников и хочу особо выразить им свою признательность. Во-первых, Стиву Саммиту, который внимательно проверил на техническом уровне первые варианты рукописи и предоставил буквально тысячи подробных комментариев, особенно в отношении программ. Стив хорошо понимал мое стремление снабдить книгу изящными и эффективные реализациями, и его комментарии помогли мне не только обеспечить определенное единообразие реализаций, но и существенно улучшить многие из них. Во-вторых, я хочу поблагодарить Лин Дюпре за тысячи подробных комментариев в отношении рукописи, которые помогли автору не только избежать и исправить грамматические ошибки, но и (что значительно важнее) выработать последовательный и связный стиль написания, что позволило собрать воедино устрашающую массу технического материала. Я исключительно благодарен полученной возможности поучиться у Стива и Лин — их вклад в разработку этой книги оказался решающим. В третьих, Крис Ван Вик реализовал и отладил все разработанные мною алгоритмы на C++, ответил на многочисленные вопросы, касающиеся C++, помог разработать соответствующий стиль на C++ и дважды внимательно прочел рукопись. Крис терпеливо сносил все мои придирки к разработанным им программам на C++, не возмущался, когда я отвергал многие из них, но по мере того, как мои знания языка C++ росли, мне приходилось возвращать эти программы практически в том виде, в каком они были написаны Крисом. Я бесконечно благодарен возможности многому научиться у Стива, Лин и Криса — они внесли решающий вклад в издание этой книги.
Многое из написанного здесь я узнал из лекций и трудов Дона Кнута - моего наставника в Стэнфорде. Хотя непосредственно Дон и не участвовал в написании этой книги, его влияние можно почувствовать на всем ее протяжении, ибо именно он поставил изучение алгоритмов на научную основу, благодаря чему вообще стало возможным появление подобного рода книг. Мой друг и коллега Филлип Флажоле, благодаря которому анализ алгоритмов стал вполне сформировавшейся областью исследований, оказал не меньшее влияние на этот труд.
Я глубоко признателен за оказанную мне поддержку Принстонскому университету, Брауновскому университету и Национальному институту исследований в области информатики и автоматики, где была проделана большая часть работы над книгой, а также Институту исследований защиты и Исследовательскому центру компании Xerox в Пало-Аль-то, где была завершена немалая часть работы. В основу многих глав этой книги положены исследования, которые щедро финансировались Национальным научным фондом и Отделом военно-морских исследований. И в заключение, я благодарю Билла Боуэна, Аарона Лемоника и Нейла Руденштайна за то, что они способствовали созданию в Принсто-не академической обстановки, в которой я получил возможность подготовить эту книгу, несмотря на множество других возложенных на меня обязанностей.
Роберт Седжвик
Марли-де-Руа, Франция, февраль 1983 г.
Принстон, Нью-Джерси, январь 1990 г.
Джеймстаун, Род-Айленд, август 1997 г.
Часть 5. Алгоритмы на графах
Предисловие консультанта по C++
Боб Сэджвик и я написали множество вариантов большей части программ, стремясь реализовать алгоритмы на графах в виде прозрачных и естественных программ. Поскольку существует великое разнообразие графов, порождающих множество касающихся их вопросов, мы согласились, что рано или поздно, но нам придется искать такую схему класса, которая будет работать на протяжении всей книги. Как ни странно, но эти поиски закончились использованием только двух схем: простой схемы, применяемой в главах 17-19, в которых ребра графа либо присутствуют, либо нет, и подхода, подобного контейнерам библиотеки STL (Standard Template Library — стандартная библиотека шаблонов) в главах 20-22, в которых с ребрами связана более обширная информация.
Классы C++ обладают существенными преимуществами для представления алгоритмов на графах. Мы используем классы для накопления полезных родовых функций на графах (наподобие ввода/вывода). В главе 18 мы используем классы для выделения операций, общих для нескольких различных методов поиска на графах. На протяжении всей книги мы применяем класс итератора к ребрам, исходящим из некоторой вершины, так что программы работают независимо от того, как хранится граф. Очень важно то, что мы упаковываем алгоритмы на графах в классы, конструктор которого осуществляют обработку графа и функции-элементы которого предоставляют нам доступ к информации об обнаруженных свойствах. Такая организация позволяет алгоритмам на графах без труда применять другие алгоритмы на графах в виде подпрограмм, например, программу 19.13 (транзитивное замыкание на основе сильных компонент), программу 20.8 (алгоритм Крускала построения минимального остовного дерева), программу 21.4 (построение всех кратчайших путей с использованием алгоритма Дейкстры), программу 21.6 (самый длинный путь в ориентированном ациклическом графе). Эта тенденция достигает наивысшей точки в главе 22, большая часть программ которой построена на более высоком уровне абстракции с использованием классов, которые были определены в предыдущих частях данной книги.
Дабы не входить в противоречие с материалом, изложенным в настоящей книге, наши программы используют разработанные в ней классы стеков и очередей, и мы применяем операции с явными указателями на односвязных списках в двухуровневых реализациях. Мы также принимаем два стилистических изменения из частей 1-4: конструкторы используют инициализацию вместо присваивания, и мы используем векторы STL вместо массивов. Ниже мы приводим перечень всех функций на векторах STL, которые были задействованы в наших программах:
■ Конструктор по умолчанию создает пустой вектор.
■ Конструктор vec(n) строит вектор из n элементов.
■ Конструктор vec(n, x) строит вектор из n элементов, каждый из которых инициа
лизируется значением х.
■ Функция-элемент vec.assign(n, x) преобразует vec в вектор из n элементов, каждый
из которых инициализируется значением х.
■ Функция-элемент vec.resize(n) возрастает или убывает, получая пропускную способ
ность n.
Предисловие
■ Функция-элемент vec.resize(n, x) увеличивает или уменьшает vec, получающий пропускную способность n, и инициализирует любые новые элементы значением x.
STL также определяет оператор присваивания, конструктор копирования и деструктор, которые необходимы, чтобы сделать векторы объектами первого рода.
Прежде чем я приступил к работе над этими программами, я ознакомился с формальными описаниями и псевдокодами множества этих алгоритмов, однако реализовал только некоторые из них. Разработка деталей, необходимая для преобразования алгоритмов в работающие программы, оказалась для меня весьма поучительной, и было очень интересно наблюдать за тем, как они работают. Я надеюсь, что ознакомление с программами, опубликованными в этой книге, и их выполнение поможет вам достичь большего понимания собственно алгоритмов.
Мои искренние благодарности я направляю Джону Бентли, Брайану Кернингану и Тому Шимански, от которых я узнал многое из того, что я сейчас знаю о программировании; Дебби Лафферти, которая предложила мне принять участие этом проекте. Я также приношу свою благодарность университету города Дрю и Принстонскому университету за безвозмездную поддержку.
Кристофер Ван Вик Чатем, Нью Джерси, 2001 г.