БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
Большинство задач поиска в пространстве состояний, проанализированных в этой главе, имеют длинную историю, отраженную в литературе, и являются менее тривиальными, чем может показаться на первый взгляд. Задача с миссионерами и каннибалами, используемая в упр. 3.9, была подробно проанализирована Амарелем [24]. До него эту задачу ввели в проблематику искусственного интеллекта Саймон и Ньюэлл [1420], и в проблематику исследования операций — Беллман и Дрейфус [96]. Работы наподобие проведенных Ньюэллом и Саймоном над программами Logic Theorist [1127] и GPS [1129] привели к тому, что алгоритмы поиска считались основным оружием в арсенале исследователей искусственного интеллекта 1960-х годов, а сами процессы решения задач стали рассматриваться в качестве канонической проблемы искусственного интеллекта. К сожалению, в то время в области автоматизации этапа формулировки задачи было предпринято слишком мало усилий. Более современная трактовка подхода к представлению и абстрагированию задач, включая применение программ искусственного интеллекта, которые (отчасти) сами выполняют эти функции, изложена в книге Кноблока [807].
Задача игры в восемь — это "младшая сестра" задачи игры в пятнадцать, которая была изобретена знаменитым американским разработчиком игр Сэмом Ллойдом [955] в 1870-х годах. Игра в пятнадцать быстро приобрела в Соединенных Штатах огромную популярность, которую можно сравнить лишь с более современной сенсацией, вызванной изобретением кубика Рубика. Она также быстро привлекла внимание математиков [739], [1486]. Редакторы American Journal of Mathematics заявили: "Игра в пятнадцать в последние несколько недель занимает все внимание американской публики, и можно с уверенностью сказать, что ею интересуются девять из десяти людей всех полов и возрастов и всех общественных положений. Но не это побудило нас, редакторов, включить статьи, посвященные этой теме, в наш журнал American Journal of Mathematics, а тот факт, что..." (далее следует краткое описание аспектов игры в пятнадцать, представляющих интерес с точки зрения математики). Исчерпывающий анализ игры в восемь был проведен с помощью компьютера Шо-филдом [1363]. Ратнер и Уормут [1268] показали, что общая версия игры (не в пятнадцать, а в пхп-1) принадлежит к классу NP-полных задач.
Задача с восемью ферзями была впервые опубликована анонимно в немецком шахматном журнале Schach в 1848 году; позднее ее создание приписали некоему
Максу Беззелю. Она была повторно опубликована в 1850 году и на этот раз привлекала внимание выдающегося математика Карла Фридриха Гаусса, который попытался перечислить все возможные решения, но нашел только 72. Наук (Nauck) опубликовал все 92 решения позднее, в том же 1850 году. Нетто [1121] обобщил эту задачу до п ферзей, а Абрамсон и Янг [2] нашли алгоритм с оценкой О (п).
Каждая из реальных задач поиска, перечисленных в данной главе, была предметом значительных усилий исследователей. Методы выбора оптимальных расписаний авиаперелетов по большей части остаются недоступными для общего пользования (закрытыми), но Карл де Маркен (Carl de Marcken) сообщил авторам (в личной беседе), что структуры формирования цен на авиабилеты и связанные с ними ограничения стали настолько сложными, что задача выбора оптимального авиарейса является формально неразрешимой. Задача коммивояжера (Traveling Salesperson Problem — TSP) — это стандартная комбинаторная проблема в теоретических компьютерных науках [898], [899]. Карп [772] доказал, что задача TSP является NP-трудной, но для нее были разработаны эффективные методы эвристической аппроксимации [933]. Арора [41] разработал полностью полиномиальную схему аппроксимации для евклидовых вариантов задачи TSP. Обзор методов компоновки СБИС был сделан Шахукаром и Мазум-дером [1390], а в журналах по сверхбольшим интегральным микросхемам (СБИС) появилось много статей, посвященных оптимизации компоновки. Задачи робототехниче-ской навигации и сборки обсуждаются в главе 25.
Алгоритмы неинформированного поиска для решения задач являются центральной темой классических компьютерных наук [680] и исследования операций [417]; более современные результаты исследований приведены в книгах Део и Панга [390], а также Галло и Паллоттино [516]. Метод поиска в ширину применительно к решению задач с лабиринтами был сформулирован Муром [1078]. Метод динамического программирования [96], в котором предусматривается систематическая регистрация решений для всех подзадач с возрастающей длиной, может рассматриваться как форма поиска в ширину в графах. Алгоритм определения кратчайшего пути между двумя точками, предложенный Дейкстрой [399], является предшественником алгоритма поиска по критерию стоимости.
Одна из версий алгоритма поиска с итеративным углублением, предназначенная для эффективного ведения игры в шахматы с контролем времени, была впервые применена Слейтом и Аткином [1429] в программе ведения шахматной игры Chess 4.5, но ее применению для поиска кратчайшего пути в графе мы обязаны Корфу [835]. В некоторых случаях может также оказаться очень эффективным двунаправленный поиск, который был предложен Полом [1219], [1221].
Частично наблюдаемые и недетерминированные варианты среды не были достаточно глубоко исследованы в этом подходе к решению задач. Некоторые проблемы эффективности при поиске в пространстве доверительных состояний рассматривались Генезеретом и Нурбакшем [538]. Кёниг и Симмонс [819] изучали навигацию робота из неизвестной начальной позиции, а Эрдман и Мэйсон [439] исследовали проблему робототехнического манипулирования без датчиков, используя непрерывную форму поиска в пространстве доверительных состояний. Поиск в условиях непредвиденных ситуаций изучался в этой подобласти планирования (см. главу 12). По большей части в подходе к изучению планирования и осуществления действий с неопределенной информацией используются инструментальные средства теории вероятностей и теории решений (см. главу 17).
Книги Нильссона [1141], [1142] являются хорошим общим источником информации о классических алгоритмах поиска. Исчерпывающий и более современный обзор можно найти в [838]. Статьи о новых алгоритмах поиска (которые, как это ни удивительно, продолжают изобретаться) публикуются в таких журналах, как Artificial Intelligence.