Реальные задачи
Выше уже было показано, как можно определить задачу поиска маршрута в терминах заданных местонахождений и переходов по связям между ними. Алгоритмы поиска маршрута используются в самых разных приложениях, таких как системы маршрутизации в компьютерных сетях, системы планирования военных операций и авиапутешествий. Обычно процесс определения таких задач является трудоемким. Рассмотрим упрощенный пример задачи планирования авиапутешествий, который задан следующим образом.
• Состояния. Каждое состояние представлено местонахождением (например, аэропортом) и текущим временем.
• Начальное состояние. Оно задается в условии задачи.
• Функция определения преемника. Эта функция возвращает состояния, которые следуют из выполнения любого полета, указанного в расписании (возможно, с дополнительным указанием класса и места), отправления позже по сравнению с текущим временем с учетом продолжительности переезда внутри самого аэропорта, а также из одного аэропорта в другой.
• Проверка цели. Находимся ли мы в месте назначения к некоторому заранее заданному времени?
• Стоимость пути. Зависит от стоимости билета, времени ожидания, продолжительности полета, таможенных и иммиграционных процедур, комфортности места, времени суток, типа самолета, скидок для постоянных пассажиров и т.д.
В коммерческих консультационных системах планирования путешествий используется формулировка задачи такого типа со многими дополнительными усложнениями, которые требуются для учета чрезвычайно запутанных структур определения платы за проезд, применяемых в авиакомпаниях. Но любой опытный путешественник знает, что не все авиапутешествия проходят согласно плану. Действительно качественная система должна предусматривать планы действий в непредвиденных ситуациях (такие как страховочное резервирование билетов на альтернативные рейсы) в такой степени, которая соответствует стоимости и вероятности нарушения первоначального плана.
Задачи планирования обхода тесно связаны с задачами поиска маршрута, но с одним важным исключением. Рассмотрим, например, задачу: "Посетить каждый город, показанный на рис. 3.1, по меньшей мере один раз, начав и окончив путешествие в Бухаресте". Как и при поиске маршрута, действия соответствуют поездкам из одного смежного города в другой. Но пространство состояний является совершенно другим. Каждое состояние должно включать не только текущее местонахождение, но также и множество городов, которые посетил агент. Поэтому первоначальным состоянием должно быть "В Бухаресте; посещен {Бухарест}", а типичным промежуточным состоянием — "В Васлуй; посещены {Бухарест, Урзичени, Васлуй}", тогда как проверка цели должна предусматривать определение того, находится ли агент в Бухаресте и посетил ли он все 20 городов.
Одной из задач планирования обхода является задача коммивояжера (Traveling Salesperson Problem — TSP), по условию которой каждый город должен быть посещен только один раз. Назначение ее состоит в том, чтобы найти самый короткий путь обхода. Как известно, эта задача является NP-трудной, но на улучшение возможностей алгоритмов TSP были затрачены колоссальные усилия. Кроме планирования поездок коммивояжеров, эти алгоритмы использовались для решения таких задач, как планирование перемещений автоматических сверл при отработке печатных плат и организация работы средств снабжения в производственных цехах.
Задача компоновки СБИС требует позиционирования миллионов компонентов и соединений на микросхеме для минимизации площади, схемных задержек, паразитных емкостей и максимизации выхода готовой продукции. Задача компоновки следует за этапом логического проектирования и обычно подразделяется на две части: компоновка ячеек и маршрутизация каналов. При компоновке ячеек простейшие компоненты схемы группируются по ячейкам, каждая из которых выполняет некоторую известную функцию. Каждая ячейка имеет постоянную форму (размеры и площадь) и требует создания определенного количества соединений с каждой из остальных ячеек. Требуется разместить ячейки на микросхеме таким образом, чтобы они не перекрывались и оставалось место для прокладки соединительных проводов между ячейками. При маршрутизации каналов происходит поиск конкретного маршрута для каждого проводника через зазоры между ячейками. Эти задачи поиска являются чрезвычайно сложными, но затраты на их решение, безусловно, оправдываются. В главе 4 приведены некоторые алгоритмы, позволяющие решать эти задачи.
Задача управления навигацией робота представляет собой обобщение описанной выше задачи поиска маршрута. В этой задаче вместо дискретного множества маршрутов рассматривается ситуация, в которой робот может перемещаться в непрерывном пространстве с бесконечным (в принципе) множеством возможных действий и состояний. Если требуется обеспечить циклическое перемещение робота по плоской поверхности, то пространство фактически может рассматриваться как двухмерное, а если робот оборудован верхними и нижними конечностями или колесами, которыми также необходимо управлять, то пространство поиска становится многомерным. Даже для того чтобы сделать это пространство поиска конечным, требуются весьма развитые методы. Некоторые из этих методов рассматриваются в главе 25. Изначальная сложность задачи усугубляется тем, что при управлении реальными роботами необходимо учитывать ошибки в показаниях датчиков, а также отклонения в работе двигательных средств управления.
Решение задачи автоматического упорядочения сборки сложных объектов роботом было впервые продемонстрировано на примере робота Freddy [1044]. С тех пор прогресс в этой области происходил медленно, но уверенно, и в настоящее время достигнуто такое положение, что стала экономически выгодной сборка таких неординарных объектов, как электродвигатели. В задачах сборки цель состоит в определении последовательности, в которой должны быть собраны детали некоторого объекта. Если выбрана неправильная последовательность, то в дальнейшем нельзя будет найти способ добавления некоторой детали к этой последовательности без отменены определенной части уже выполненной работы. Проверка возможности выполнения некоторого этапа в последовательности представляет собой сложную геометрическую задачу поиска, тесно связанную с задачей навигации робота. Поэтому одним из дорогостоящих этапов решения задачи упорядочения сборки является формирование допустимых преемников. Любой практически применимый алгоритм должен предотвращать необходимость поиска во всем пространстве состояний, за исключением крошечной его части. Еще одной важной задачей сборки является проектирование молекулы белка, цель которой состоит в определении последовательности аминокислот, способных сложиться в трехмерный белок с нужными свойствами, предназначенный для лечения некоторых заболеваний.
В последние годы выросла потребность в создании программных роботов, которые осуществляют поиск в Internet, находя ответы на вопросы, отыскивая требуемую информацию или совершая торговые сделки. Это — хорошее приложение для методов поиска, поскольку Internet легко представить концептуально в виде графа, состоящего из узлов (страниц), соединенных с помощью ссылок. Полное описание задачи поиска в Internet отложим до главы 10.