Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 31
Текст из файла (страница 31)
Задача ~ компоновки СВИС требует позиционирования миллионов компонентов и соединений на микросхеме для минимизации плошади, схемных задержек, паразитных емкостей и максимизации выхода готовой продукции. Задача компоновки следует за этапом логического проектирования и обычно подразделяется на две части: компоновка ячеек и маршрутизация каналов.
При компоновке ячеек простейшие компоненты схемы группируются по ячейкам, каждая из которых выполняет некоторую известную функцию. Каждая ячейка имеет постоянную форму (размеры и площадь) и требует создания определенного количества соединений с каждой из остальных ячеек. Требуется разместить ячейки на микросхеме таким образом, чтобы они не перекрывались и оставалось место для прокладки соединительных проводов между ячейками. При маршрутизации каналов происходит поиск конкретного маршрута для каждого проводника через зазоры между ячейками. Эти задачи поиска являются чрезвычайно сложными, но затраты на их решение, безусловно, оправдываются. В главе 4 приведены некоторые алгоритмы, позволяющие решать эти задачи.
ох Задача управления навигацией робота представляет собой обобщение описанной выше задачи поиска маршрута. В этой задаче вместо дискретного множества маршрутов рассматривается ситуация, в которой робот может перемешаться в непрерывном пространстве с бесконечным (в принципе) множеством возможных действий и состояний. Если требуется обеспечить циклическое перемещение робота по плоской поверхности, то пространство фактически может рассматриваться как двухмерное, а если робот оборудован верхними и нижними конечностями или колесами, которыми также необходимо управлять, то пространство поиска становится многомерным. Даже для того чтобы сделать это пространство поиска конечным, требуются весьма развитые методы.
Некоторые из этих методов рассматриваются в ~лаве 25. Изначальная сложность задачи усугубляется тем, что при управлении реальными роботами необходимо учитывать ошибки в показаниях датчиков, а также отклонения в работе двигательных средств управления. Решение задачи Ъ. автоматического упорядочения сборки сложных объектов роботом было впервые продемонстрировано на примере робота Ргеббу (1044!. С тех пор прогресс в этой области происходил медленно, но уверенно, и в настоящее время достигнуто такое положение, что стала экономически выгодной сборка таких неординарных объектов, как электродвигатели. В задачах сборки цель состоит в определении последовательности, в которой должны быть собраны детали некоторого объекта.
Если выбрана неправильная последовательность, то в дальнейшем нельзя будет найти способ добавления некоторой детали к этой последовательности без отменены определенной части уже выполненной работы. Проверка возможности выполнения некоторого этапа в последовательности представляет собой сложную геометрическую задачу поиска, тесно связанную с задачей навигации робота.
Поэтому одним из дорогостоящих этапов решения задачи упорядочения сборки является Часть П. Решение проблем 122 формирование допустимых преемников. Любой практически применимый алгоритм должен предотвращать необходимость поиска во всем пространстве состояний, за исключением крошечной его части. Еше одной важной задачей сборки является Ъ. проектирование молекулы белка, цель которой состоит в определении последовательности аминокислот, способных сложиться в трехмерный белок с нужными свойствами, предназначенный для лечения некоторых заболеваний. В последние годы выросла потребность в создании программных роботов, которые осушествляют 'в. поиск в!в1егпег, находя ответы на вопросы, отыскивая требуемую информацию или совершая торговые сделки. Это — хорошее приложение для методов поиска, поскольку 1пгегпег легко представить концептуально в виде графа, состоящего из узлов (страниц), соединенных с помощью ссылок.
Полное описание задачи поиска в 1пгегпег отложим до главы 1О. 3.3. ПОИСК РЕШЕНИЙ Сформулировав определенные задачи, необходимо найти их решение. Такая цель достигается посредством поиска в пространстве состояний. В настояшей главе рассматриваются методы поиска, в которых используются явно заданное Ъ. дерево поиска, создаваемое с помощью начального состояния и функции определения преемника, которые совместно задают пространство состояний.
Вообще говоря, вместо дерева поиска может применяться граф поиска, если одно и то же состояние может быть достигнуто с помощью многих путей. Это важное дополнение рассматривается в разделе 3.5. На рис. 3.5 показаны некоторые расширения дерева поиска, предназначенного для определения маршрута от Арада до Бухареста. Корнем этого дерева поиска является Ъ. поисковый узел, соответствуюший начальному состоянию, 7п)лгас)) . Первый этап состоит в проверке того, является ли это состояние целевым. Безусловно, что оно не является таковым, но необходимо предусмотреть соответствуюшую проверку, чтобы можно бьшо решать задачи, содержащие в себе готовое решение, такие как "начав путешествие с города Арад, прибыть в город Арад". А в данном случае текущее состояние не является целевым, поэтому необходимо рассмотреть некоторые другие состояния.
Такой этап осуШествляется путем ~в. развертывания текущего состояния, т.е применения функции опрелеления преемника к текугцему состоянию для Ж формирования в результате этого нового множества состояний. В данном случае будут получены три новых состояния: 1п (ЯЗЬац), тп)зйоз воаха) и 2п)лезйпд) . Теперь необходимо определить, какой из этих трех вариантов следует рассматривать дальше. В этом н состоит суть поиска — пока что проверить один вариант и отложить другие в сторону, на тот случай, что первый вариант не приведет к решению.
Предположим, что вначале выбран город Сибиу. Проведем проверкудля определения того, соответствует ли он целевому состоянию (не соответствует), а затем развернем узел ЯЗ.Ыи для получения состояний Тп)лгаЯ, 1п)Гасгагав), 1а)Огас)еа) и 1п)ддтпдсцр31оеа). После этого можно выбрать любое из этих четырех состояний либо вернуться и выбрать узел тдгвдяоаха или лехдпс).
Необходимо снова и снова выбирать, проверять и развертывать узлы до тех пор, пока не будет найдено решение или не останется больше состояний, которые можно было бы развернуть. Порядок, в котором происходит развертывание состояний, определяется 'ъ стратегией поиска. Общий алгоритм поиска в дереве неформально представлен с истннге 3.2. 124 Часть 1! р и д ""и'б Р~~ Глава 3.
Решение проблем посредством поиска [25 периферии представляет собой 'в. листовой узел, т.е. узел, не имеющий преемников в дереве. На рис. 3.5 периферия каждого дерева состоит из узлов с полужирными контурами. Простейшим представлением периферии может служить множество узлов.
Тогда стратегия поиска должна быть выражена в виде функции, которая выбирает определенным образом из этого множества следующий узел, подлежагций развертыванию. Хотя данный подход концептуально является несложным, он может оказаться дорогостояшим с вычислительной точки зрения, поскольку функцию, предусмотренную в этой стратегии, возможно, придется применить к каждому элементу в указанном множестве для выбора наилучшего из них. Поэтому предполагается, что коллекция узлов реализована в виде ск очереди.
Операции, применимые к любой очереди, состоят в следующем. ° Ма)се-С1иеие ( е1етепс, ... ) . Создает очередь с заданным элементом (элементами). ° Етрпуз(сгиеие). Возврашает истинное значение, только если в очереди больше нет элементов. ° Р1ГЗС ( диене) . Возврашает первый элемент в очереди.
° нетоуе-РЕгяс ( с)иеие) . Возврагцает элемент Рзгяс (с)иене) и удаляет его из очереди. ° 1пяегС (е1етепг, диене) . Вставляет элемент в очередь и возвращает результируюшую очередь. (Ниже будет показано, что в очередях различных типов вставка элементов осуществляется в различном порядке.) ° 1пзегс-А11 [ е1етепся, с1иеие) . Вставляет множество элементов в очередь и возврашает результирующую очередь. С помощью этих определений мы можем записать более формальную версию общего алгоритма поиска в дереве, показанную в листинге 3.3. Листинг 3.3. Общий алгоритм поиска в дереве.
Следует учитывать, что фактический параметр егепдв (пернферня) должен представлять собой пустую очередь, а порядок поиска зависит от типа очереди. Функция Яо1исаоп возвращает последовательность действий, полученную путем прохождения пе указателям на родительские узлы в обратном направлении, к корню ЕипсеЕоп тгее-яеагсЬ(ргоЫет, Егйпде) гесигпв решение яо1и одоп или индикатор неудачи Еа11иге Егдпде + — 1пяегг(Маке-мосе(1пьгьа1-ЯСаге[ргоЫеш]), Егдлде) 1оор ([о ЕЕ Ешрсут(Егдпде) сиво гесигп индикатор неудачи Еа11иге попе ь- Непюуе-Рагзг(гг1пде) ЕЕ Поа1-тезг[ргоЫет] применительно к влаге[попе] завершается успешно пьеп гесигп яо1исьоп(попе) Егдлде <†1пяегн-я11(вхрапс(пос[е, ргоЬ1еш), Ег1пде) Еипсеаоп Ехрапд(поде, ргоЬ1еш) гесигпв множество узлов яиссеяяогя яиссеяяогя ь- пустое множество Еог вась <асс1оп, геяи1с> Ап яиссезяог-Рп [ргоЫеш] (этапе[поде]) бо я ь- новый узел Часть П. Решение проблем 126 Ясаке[я! ь- геяц1е Ракепб-Небе[я) +- поде лссьоп[я! ь- ассзоп Радо-Сове[я! ( — Радо-Сове[песе! + Ядер-сове[поде, ассзоп, я) перса[я! +- персе[ооие! + 1 добавить узел я к множеству яиссеяяогя кееити яиссеяяояя Измерение производительности решения задачи Результатом применения любого алгоритма решения задачи является либо неудачное завершение, либо получение решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
