пользоваться некоторой достаточно общеупотребительной терминологией.

Почти энциклопедическое изучение деревьев можно найти у Кнута [56].

Нетрудной, ориентированной на приложения книгой является [20]. Здесь можно найти хорошо изложенные основы применения сетей к теории переключателей и кодирования, анализу электрических схем и исследованию операций. Книга содержит также краткое обсуждение вопросов, связанных с применением теории сетей в химии.

При работе с сетями в теоретическом плане большую помощь может оказать книга [7], которая содержит наиболее полную мате-.матическую трактовку графов и сетей на современном уровне изложения этих вопросов. По-видимому, свое фундаментальное значение эта книга не утеряет и в ближайшем будущем.

Алгоритмы обработки сетей очень интенсивно используются в области исследования операций. Литература в этой области обширна, мы укажем лиидь на работы [34], [29] и [62].

Алгоритм CONNECT можно найти в [20]; там же рассматриваются другие матричные представления и ряд алгоритмов обработки сетей.

Хорошая эвристика для проблемы изоморфизма описана в [14]. К сожалению, некоторые из высказанных в этой статье теоретических предположений, как было показано позднее, неверны. Впрочем, рассматриваемый в статье основной алгоритм остается одной из наиболее известных общих эвристик.

Проблема изоморфизма была решена для некоторых специальных классов сетей, самым важным из них являются деревья; см. [13].

Для работы с сетями было разработано много специальных языков программирования и пакетов программ. Приводим небольшую подборку литературы по этим вопросам: [3], [ 0], [44], [55], [68]. Язык CLAMAR [68] замечателен тем, что он был полностью разработан двумя студентами. Использование большинства специальных языков ограничено и локализовано.

2.3. Некоторые структуры данных

Большой и детальный перечень различных структур данных можно найти у Киута [56]. Среди других широко используемых книг можно назвать [8], [771 и [87].

2.4. Элементарные понятия из теории вероятностей и статистики

Легко читаемым, ориентированным на практическое применение введением в теорию вероятностей является [81]. В гл. 8 этой книги содержится прекрасное введение к теме надежности систем - теме, имеющей серьезное применение в вычислительной науке.

Достаточно элементарную и легко понимаемую трактовку дискретных событий и случайных переменных можно найти в классической работе Феллера [26].

Очень элементарное, ориентированное на программистов (язык Basic) введение в дискретную вероятность содержится в [85].

Анализ ожидаемой трудоемкости алгоритмов, как правило, очень труден; анализ алгоритма SIS в этом разделе является исключением. Анализ ожидаемой трудоемкости алгоритма МАХ (см. разд. 1.2) можно найти в книге [56]. Алгоритм ETS (см. разд. 1.3) всегда выполняет одно и то же число операций для любого множества городов. Алгоритм PRIM настолько бесхитростен, что едва ли стоит заниматься анализом его ожидаемой трудоемкости. Это видно и по результатам экспериментального анализа средней трудоемкости в разд. 5.2.

Ниже приводится подборка ссылок, относящихся к приложениям, которые описаны в начале разд. 2.4.

По теме «имитационное моделирование» смотрите [28]. Дополнительные ссылки даются для разд. 3.6 и 6.3. По вычислительной статистике мы рекомендуем [30]. Генерация случайных чисел рассмотрена в [57]. По Бейесовской теории принятия решений см. [98] и [18]. Достаточно полное введение в статистические методы можно найти в [73]. Книгой на элементарном уровне является [48]. Более фундаментальная трактовка содержится в [15].

Глава 3. Методы разработки алгоритма

3.1. Методы частных целей, подъема и отрабатывания назад

В области общих методов решения задач работали психологи, математики и специалисты по вычислительной математике. Некоторые из наиболее известных источников - следующие. Психологом написана книга [96], математиком - [78, 79], специалистом по вычислительной математике - [76].

Большинство работ специалистов по вычислительной математике в области методов решения задач можно найти под рубрикой «искусственный интеллект». Исчерпывающими обзорами являются [25] и [71]. Значительная часть этой литературы связана с играми на ЭВМ.

Полное рассмотрение задачи о джипе можно найти в [35].

Ричард Беллман и другие развили метод отрабатывания назад в нечто, лежащее между искусством и наукой, известное как динамическое программирование. Хорошо написанные вводные обзоры можно найти в [45] и [52].

3.2. Эвристики

Каждый год многие студенты «заново открывают» алгоритм GTS2. Гораздо более действенный (и более сложный) эвристический метод

для задачи коммивояжера дан в [64]. Быстрые, простые (но не особенно мощные) эвристические методы для очень больших задач рассмотрены в [94].

Наглядное рассмотрение с большим количеством интересных примеров эвристических алгоритмов для составления расписаний и упаковки можно найти в [41].

Анализ ряда простых, но эффективных эвристических алгоритмов содержится в [50].

3.3. Программирование с отходом

Этот метод «заново открывался» много раз. Например, см. [39]. Хорошее общее описание процедуры отхода можно найти в [60]. В последней статье также содержится полезный полуэкспериментальный анализ средней трудоемкости, применимый к любому алгоритму с отходом.

3.4. Метод ветвей и границ

Алгоритм этого раздела основан на статье [65], которая во многом способствовала популяризации процедуры ветвей и границ.

Более содержательное рассмотрение см. в [38]. Как показывает последняя работа, процедуры ветвей и границ очень полезны для решения задач оптимизации, известных как задачи целочисленного линейного программирования. В этих задачах требуется найти множество целых чисел, которые максимизируют или минимизируют линейную форму при линейных ограничениях. Многие важные задачи, включая задачу коммивояжера, можно сформулировать как задачи целочисленного линейного программирования.

Обзор работ по задаче коммивояжера до 1968 г. можно найти в [6].

Заслуживающими внимания вкладами в литературу по задаче коммивояжера являются работы [5] и [46]. Впечатляют результаты вычислительных экспериментов с этими двумя алгоритмами. Заметим, что в работе [46] используются остовные деревья минимального веса.

Один из наиболее эффективных с точки зрения скорости и качества решения эвристических алгоритмов для задачи коммивояжера можно найти в работе [64].

3.5. Рекурсия

Прекрасное описание рекурсии дано в книге [2].

Рекуррентные соотношения часто возникают в приложениях, и для нахождения решений таких уравнений в замкнутой форме существует много методов. Хорошее вводное изложение этого материала можно найти в [66].

В книге [76] обсуждаются методы поиска в ширину и глубину.