Intel_Nils (526801), страница 8
Текст из файла (страница 8)
Между каждой парой городов имеется путь, длина которого указана на этой карте. Нужно, отправляясь из города А, найти самый короткий путь, по которому коммивояжер по одному разу проходит через каждый из городов и затем возвращается в город А. Чтобы дать представление в пространстве состояний, мы должны определить следующее: Описания состояний.
Будем задавать состояния списком городов, пройденных к настоящему моменту. Так, начальным состоянием будет список (А). Мы не будем допускать, чтобы в этом списке какой-то город упоминался более одного раза, с тем лишь исключением, что после того, как в нем буду~ упомянуты все остальные .города, может быть снова упомянут А. Операторы. Операторы суть вычисления, соответствующие поступкам: (1) направиться теперь в город А, (2) направиться 88 Гл. 2.
Представление задач в пространстве состояний теперь в город В, ..., (5) направиться теперь в город Е. Оператор неприменим к некоторому описанию состояния, если он не преобразует его в некоторое допустимое описание. Так, оператор номер (!) (соответствующий «направиться теперь в город А») неприменим ни к какому описанию, не содержащему названия всех городов.
Критерий достижения цели, Любое описание, начинающееся и оканчивающееся городом А и перечисляющее все другие города, есть описание состояния, удовлетворяющего поставленной цели. На рис. 2.5 показано представление этого пространства состояний в виде графа. (Явно указаны лишь некоторые из его (А) /А В) /А Е) I 1 / / ч / 1 / / ~ / ч / 1 / / $ / ч / (АСОЕВ) (АСРЕВА) Целевая вершина Ряс. 2.8. Часть графа для эвдачн о коммнвояжете. вершин.) Числа, написанные около дуг графа, указывают стоимости этих дуг'.
Мы полагаем эти стоимости равными расстояниям между соответствующими городами (см. рис. 2А). В вершинах графа стоят описания тех состояний, которые они представляют. Достоинства представления в виде графа состоят 2.б. Некоторые примеры представлений зада» в том, что приписывание дугам стоимостей дает нам удобный способ вычисления полной длины маршрута, а следовательно, и способ поиска кратчайшего из них. Кратчайший (34 мили) для нашего случая показан на графе жирными стрелками. Задача о коммивояжере представляет собой пример задачи.
в которой информация, содержащаяся в ее формулировке, представима в графической форме (карте расстояний). Следует быть внимательным и не смешивать какие-либо графы, используемые при формулировке задачи, с графом пространства состояний, который строится при решении задачи. Задачи синтаксического анализа При работе с языками часто сталкиваются с задачей синтакси»еского анализа. В таких задачах сначала дается некоторое формальное определение через задание грамматики, которая выделяет определенный класс строк символов.
А затем возникает вопрос о том, принадлежит ли к этому классу произвольная строка. Следующий пример иллюстрирует этот тип задач. Грамматика. Предположим, что мы определяем предложение иак строку однбго из следующих видов: за символом а следует символ Ь за символом а следует некоторое предложение за некоторым предложением следует символ Ь за некоторым предложением следует другое предложение. Примеры предложений: ааЬ, айаадаЬ, аааааЬ. Некоторые строки, не являющиеся предложениями: ааа, айа, аЬаа.
Предположим, что мы захотели определить, является лн строка аЬааЬаЬ предложением. Тогда формулировка этой задачи в пространстве состояний выглядит так: Описания состояний. Один из возможных путей формулировки этой задачи состоит в том, чтобы выбрать в качестве начального состояния рассматриваемую строку аЬааЬаЬ. Тогда множеством допустимых состояний будет множество строк, получающихся из нее путем применения тех правил переписывания (они даются ниже), которыми определяются операторы. Операторы.
Мы определяем операторы через следующие правила переписывания: З,аЬЗ»- $,5$з (подстрока аЬ может быть заменена символом 5, обозначающим предложение) З,а5$з-н $,5$, $15ЬЗз 3153» $,55$, - 3,53з Мы видим, что эти правила просто выражают грамматику, определяющую понятие предложения. ло Гл. 2, Представление задач в пространстве состояний Критерий цели. Целевое состояние описывается строкой, которая состоит из одиночного символа 5. Последовательность состояний, представляющая собой решение этой задачи, имеет следующий вид: аЬааЬаЬ 5аадаЬ 5а5аЬ 55аЬ 555 55 5 Граф, изображающий пространство состояний для этой задачи, показан на рис.
2.6. В этой задаче оказалось так, что Ь Ь Ь и '"'"'я аЬааЬаЬ аьазаь аьаааа ада аьаэа целевая вершина Я Р и с. 2.6. Граф дли задачи синтаксического анализа. в силу заданной граглматикн любая строка, начинающаяся с и и оканчивающаяся на Ь, является предложением. Знание такого факта, очевидно, сильно бы упростило решение вопроса о том, будет ли некоторая произвольная строка предложением. Иногда оказывается, что заданная грамматика может бьмь представ- лХ Некоторые примеры представлений задач 4! лена в эквивалентном, но более простом виде. Обнаружение таких упрощений позволяет строить меньшие пространства для перебора.
Задачи распределения Следующая простая задача типична для класса задач, называемых иногда задачами распределения. Имеются два источника жидкости: А дает 100 галлонов в минуту, а  — 50. Источники должны снабжать два бассейна С и Р„потребность каждого из которых 75 галлонов в минуту. Жидкость может В В с Вассейи, 75 оста сник,50 Васса!и 75 л истачиик, !СО Р не. 2.7. Расположение источников жидкости и бассейнов (расстояаия измеряются в милях). подаваться от источника к бассейну с помощью труб с максимальной пропускной способностью 75 галлонов в минуту. Пусть источники и бассейны расположены так, как это показано на рис. 2.7, и соединения труб допускаются только в местах расположения источников и бассейнов.
Спрашивается, как следует подсоединять трубы, чтобы при этом полная длина труб была наименьшей., Представление этой задачи в пространстве состояний выглядит следующим образом: Описания состояний. Состояния описываются списком величин избыточного расхода жидкости, который имеется в точках А, В, С и Р. Так, начальное состояние описывается списком (А = 100, В = 50, С = О, Р = О).
Операторы. Операторы соответствуют передаче избытка «жидкости в минуту» из одной точки в другую. В задачах, по- 42 Гл. 2. Представление задач в пространстве состояний .добных этой, в качестве подходящего избытка выступает наибольший общий делитель пропускных способностей н потребностей в жидкости в различных точках. Таким образом, у нас есть операторы: 1. Передать 25 галлон/мин из А в В. 2. Передать 25 галлон/мин из А в С. 12. Передать 25 галлон/мин из В в А.
Разумеется, операторы применимы лишь тогда, когда имеется достаточный избыток жидкости в той точке, от которой жидкость отбирается для передачи в другую точку. И, конечно, для осуществления каждой такой передачи нужно иметь соответствующую трубу. Критерий цели. Целевое состояние описывается списком (А = О, В = О, С = 75, В = 75) . Напальная вершина /Я = )РОВ 50 С 00 Р) л51 1Л 75,0 =5 1Я = 75,В "50,С 0,0 лз/ /Я 0 В=ОС 75 О 75) Ф Целевая вершина р и с. 2.8. Часть графа для задача распределения. Часть графа, получающегося таким образом пространства состояния, показана на рис. 2.8.
Обозначение типа А -+В около дуг графа показывает, что соответствующий оператор передает избыток в 25 галлон/мин от А к /7. Стоимости, написанные рядом с каждой дугой, показывают, сколько миль труб нужно добавить для подачи этого избытка. Число нуль при этом озна- 2.б. Некоторые причеры предстаелепий задач 43 чает, что нет необходимости добавлять еше трубу, поскольку уже имеющаяся труба обладает достаточной дополнительной пропускной способностью. Граф на рис.
2.8 изображен не полностью — многие из его вершин не показаны. Исследовав полпый граф, можно установить, что путь, ведущий от начальной вершины к целевой и обладающий наименьшей стоимостью, требует 12 миль труб. Задачи управления В типичной задаче управления имеется процесс, представленный системой «устанавливаемых» переменных, которые должны управляться с помощью соответствующего управления, обеспечиваемого некоторым множеством управляющих переменных.
Интересным примером служит задача о перевернутом маятнике на тележке (рис. 2.9). В этой задаче масса М прикреплена к концу стержня длины 1, другой конец которого шарнирно закреплен на тележке, так что стержень может свободно вращаться в вертикальной плоскости, совпадающей с направлением движения тележки, снабженной колесами. Устанавливаемые переменные — угол наклона стержня О, координата х тележки и производная по времени О.
Требуется, чтобы значения каждой из этих переменных поддерживались в определенных, заранее укзванных границах. Управляющей переменной служит скорость тележки х, которая может принимать одно Рке. Х9. Перевернутый м ктиз двух значений +о и — о, (Мы квк ке тележке. предполагаем для простоты, что эти значения могут сменять друг друга мгновенно.) Главная задача здесь состоит в принятии в данный момент решения о том, следует ли перемешать тележку со скоростью о вправо илн со скоростью о влево.
Описание состояний. Предположив, что переменные О, О и х принимают дискретные значения с достаточно мелким шагом, можно считать состоянием вектор, составленный из этих трех переменных (пространством состояний при этом служит решетка в трехмерном пространстве 9, О и х). Операторы. Имеются ровно два оператора: 1. Применить управление + о. 2. Применить управление — о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
