Каждая из реальных задач поиска, перечисленных в данной главе, была предметом значительных усилий исследователей. Методы выбора оптимальных расписаний авиаперелетов по большей части остаются недоступными для общего пользования (закрытыми), но Карл де Маркен (Carl de Marcken) сообщил авторам (в личной беседе), что структуры формирования цен на авиабилеты и связанные с ними ограничения стали настолько сложными, что задача выбора оптимального авиарейса является формально неразрешимой. Задача коммивояжера (Traveling Salesperson Problem — TSP) — это стандартная комбинаторная проблема в теоретических компьютерных науках [898], [899]. Карп [772] доказал, что задача TSP является NP-трудной, но для нее были разработаны эффективные методы эвристической аппроксимации [933]. Арора [41] разработал полностью полиномиальную схему аппроксимации для евклидовых вариантов задачи TSP. Обзор методов компоновки СБИС был сделан Шахукаром и Мазум-дером [1390], а в журналах по сверхбольшим интегральным микросхемам (СБИС) появилось много статей, посвященных оптимизации компоновки. Задачи робототехниче-ской навигации и сборки обсуждаются в главе 25.

Алгоритмы неинформированного поиска для решения задач являются центральной темой классических компьютерных наук [680] и исследования операций [417]; более современные результаты исследований приведены в книгах Део и Панга [390], а также Галло и Паллоттино [516]. Метод поиска в ширину применительно к решению задач с лабиринтами был сформулирован Муром [1078]. Метод динамического программирования [96], в котором предусматривается систематическая регистрация решений для всех подзадач с возрастающей длиной, может рассматриваться как форма поиска в ширину в графах. Алгоритм определения кратчайшего пути между двумя точками, предложенный Дейкстрой [399], является предшественником алгоритма поиска по критерию стоимости.