3.14. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ

Алгоритмы поиска кратчайшего пути

Алгоритмы поиска кратчайшего пути (или пути наименьшей стоимости) между двумя вершинами графа представляют большой интерес для широкого круга дисциплин. Процедуру, названную нами методом равных цен, впервые описал Дийкстра (1959). Подобный метод полного перебора предлагался также

Муром (1959). Алгоритмы динамического программирования Беллмана по существу также являются методами полного перебора. Подробное изложение динамического программирования содержится в книге Беллмана и Дрейфуса (1962). Процедура перебора на заданную глубину часто называется программированием. с обратным слежением (back-track programming); она описана Голомбом и Бомертом (1965). Стюарт Дрейфус (1969) дает подробный обзор этих и других методов поиска на графах.

Эвристические приемы поиска

Вопрос использования эвристической информации для увеличения эффективности перебора рассматривался как в области искусственного интеллекта, так и в исследовании операций. Вероятно, самым известным применением эвристических оценочных функций были игровые программы, в особенности программа Сэмюэля (1959, 1967) для игры в шашки. Привлечение оценочных функций для придания направленности перебору на графе было предложено Дораном и Мичи (1966) и в дальнейшем исследовалось Дораном (1968) и Мичи и Россом (1970). Наши примеры игры в восемь основаны на примерах Дорана и Мичи. Общая теория использования оценочных функций для ведения перебора была дана в статье Харта, Нильсона и Рафаэля (1968); приведенное нами описание алгоритма упорядоченного поиска и его свойств базируется на этой статье.

В методах ветвей и границ из области исследования операций мы также находим привлечение оценочных функций для направления перебора к цели. Их описание можно найти в обзорной статье Лолера и Вуда (1966). Метод ветвей и границ, предложенный Шапиро (1966) для задачи о коммивояжере, может быть также интерпретирован как прямое применение алгоритма А.

Наш анализ, подтверждающий важность включения функции (точно так же, как и функции Н) в оценочную функцию, взят из диссертации Поля (1969). (См. также Поль, 1970.) Поль (1969) рассмотрел также проблему построения перебора как из начальной, так и из целевой вершины. В особенности здесь интересно его подробное рассмотрение более сложных критериев остановки, необходимых при двунаправленном переборе.

Прерывание хода процесса перебора этапами отсечения ветвей дерева (для очищения требуемой памяти) было исследована Дораном и Мичи (1966) и Дораном (1967).

Критерии качества работы

Доран и Мичи (1966) предложили целенаправленность как критерий эффективности данного поиска. Слейджл и Диксон (1969) предложили иную меру, которую они назвали «глубинное

отношение». Наше «эффективное ветвление» было навеяно этими двумя введенными раньше мерами эффективности.

Задачи

(см. скан)