Шпора-small (Шпоры к первому коллоквиуму), страница 12

PDF-файл Шпора-small (Шпоры к первому коллоквиуму), страница 12, который располагается в категории "контрольные работы и аттестации" в предмете "искусственный интеллект" изседьмого семестра. Шпора-small (Шпоры к первому коллоквиуму), страница 12 - СтудИзба 2019-09-18 СтудИзба

Описание файла

Файл "Шпора-small" внутри архива находится в папке "Шпоры к первому коллоквиуму". PDF-файл из архива "Шпоры к первому коллоквиуму", который расположен в категории "контрольные работы и аттестации". Всё это находится в предмете "искусственный интеллект" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 12 страницы из PDF

Для этого могутприменяться любые подходящие структуры – строки, массивы, списки, деревья и т.п. Например,для игры в пятнадцать или восемь наиболее естественной формой описания состояния будетсписок положений фишек или же двумерный массив. Заметим, что от выбора формы описаниясостояния зависит в общем случае сложность задания операторов задачи, которые должны бытьтакже определены при формализации задачи в пространстве состояний.Если для игры в пятнадцать средством формализации выступает язык программированияЛисп или Паскаль, то операторы задачи могут быть описаны в виде четырех соответствующихфункций языка.

При использовании же продукционного языка, эти операторы задаются в видеправил продукций вида: «исходное состояние → результирующее состояние».В рассмотренных выше примерах (игры в пятнадцать и восемь) искомое целевоесостояние задавалось явно, т.е. известно было местоположение каждой фишки в целевойконфигурации.

В более сложных случаях игры может быть несколько целевых состояний, либо жецелевое состояние может быть определено неявно, т.е. охарактеризовано некоторым свойством,например, как состояние, в котором сумма номеров фишек в верхнем ряду не превосходит 10. Вподобных случаях свойство, которому должно удовлетворять целевое состояние, должно бытьописано исчерпывающим образом, к примеру, путем задания булевской функции, реализующейпроверку нужного свойства состояния задачи.Итак, для представления задачи в пространстве состояний необходимо определитьследующее:• форму описания состояний задачи и описание начального состояния;• множество операторов и их воздействий на описания состояний;• множество целевых состояний или же описание их свойств.Перечисленные составляющие задают неявно граф-пространство состояний, в котором требуетсяпровести поиск решения задачи.

Заметим попутно, что в отличие от такого неявного способазадания графа, при явном способе задания все вершины и дуги графа должны быть перечислены,например, с помощью таблиц.Решение задачи в пространстве состояний подразумевает просмотр неявно заданногографа, для чего необходимо преобразование в явную форму достаточно большой его части,включающей искомую целевую вершину. Действительно, просмотр осуществляется какпоследовательный поиск, или перебор вершин, в пространстве состояний. В исходной точкепроцесса к начальному состоянию применяется тот или иной оператор и строится новая вершинасостояние, а также связывающие ее с корневой вершиной дуги.

На каждом последующем шагепоиска к одной из уже полученных вершин-состояний применяется допустимый оператор истроится еще одна вершина графа и связывающие дуги. Этот процесс поиска продолжается до техпор, пока не будет построена вершина, соответствующая целевому состоянию.Рис.21117139g52438101512614111713g3521512614111713948109352g48101117131512614111713Примеры пространств состоянийBC93529352g126141117134 15g 128 610 14154810AD935241281015g61411171393521117134 15g 128 610 149352HE4 158 12g 610 14GРазберем два характерных примера представления в пространстве состояний,показывающих, что такое представление возможно для различных типов задач. Подчеркнемзаранее, что предлагаемые ниже представления, хотя и являются достаточно естественными, неявляются единственно допустимыми в этих задачах, возможны и другие варианты.Вообще, от выбора представления, т.е.

рассмотренных выше составляющих, зависитразмер пространства состояний, а значит, и эффективность поиска в нем. Очевидно, желательныпредставления с малыми пространствами состояний, но нахождение сужающих пространствопоиска удачных представлений требует обычно некоторого дополнительного анализа решаемойзадачи.Рассмотрим формализацию в пространстве состояний известной задачи о коммивояжере(представляющей классическую переборную проблему). Коммивояжер, располагая картой дорог,соединяющей 7 городов (рис.

3), должен построить свой маршрут так, чтобы выехав из города А,посетить каждый из других шести городов B, C, D, E, H, G в точности по одному разу и затемвернуться в исходный город. В другом, более сложном варианте задачи требуется также, чтобымаршрут имел минимальную протяженность.Рис. 3Состояние решаемой задачи можно задать как список городов, которые уже проехалкоммивояжер к текущему моменту. Тогда возможным состояниям соответствуют списки изэлементов A, B, C, D, E, H, G без повторений, исключение составляет только город A, он можетвстретиться в списке дважды – в начале списка и его конце. Пример списка-состояния – (A B C H).Начальное же состояние определяется как список (A), а целевое – как любой допустимый список,начинающийся и кончающийся элементом A.

Для определенных таким образом состояний задачиоператоры задачи могут соответствовать перемещениям между городами – получаем такимобразом 13 операторов.Рассмотрим теперь широко известную задачу об обезьяне и банане, простейшуюформулировку которой мы и рассмотрим. В комнате находятся обезьяна, ящик и связка бананов,которая подвешена к потолку настолько высоко, что обезьяна может до нее дотянуться, тольковстав на ящик.

Нужно найти последовательность действий, которая позволит обезьяне достатьбананы. Предполагается, что обезьяна может ходить по комнате, двигать по полу ящик, взбиратьсяна него и хватать бананы.Ясно, что описание состояния этой задачи должно включать следующие сведения:местоположение обезьяны в комнате – в горизонтальной плоскости пола и по вертикали (т.е. наполу она или на ящике), местоположение ящика на полу и наличие у обезьяны бананов. Все этоможно представить в виде четырехэлементного списка (ПолОб, ВертОб, ПолЯщ, Цель), гдеПолОб – положение обезьяны на полу (это может быть двухэлементный вектор координат);ПолЯщ – положение обезьяны и ящика на полу;ВертОб – это константа П или Я в зависимости от того, где находится обезьяна, на полу или наящике;Цель – это константа 0 или 1 в зависимости от того, достала ли обезьяна бананы или нет.Зафиксируем также как константы три следующие точки в плоскости пола:ТО – точка первоначального местоположения обезьяны;ТЯ – точка первоначального расположения ящика;ТБ – точка пола, расположенная непосредственно под связкой бананов.Тогда начальное состояние задачи описывается списком (ТО, П, ТЯ, 0), а целевое состояниезадается как любой список, последний элемент которого – 1.Естественно определить операторы в этой задаче в соответствии с возможными действиямиобезьяны:1) Перейти (W) – переход обезьяны к точке W горизонтальной плоскости пола;2) Передвинуть (V) – передвижение обезьяной ящика в точку V пола;3) Взобраться – обезьяна взбирается на ящик;4) Схватить – обезьяна хватает связку бананов.Условия применимости и действие этих операторов легко определить в виде правил продукцийвида: аргумент оператора → результат оператора,причемX, Y, Z, W, V обозначают переменные:1.

Перейти (W) :(X, П, Y, Z ) → (W, П, Y, Z)2. Передвинуть (V) :(X, П, X, Z) → (V, П, V, Z)3. Взобраться :(X, П, X, Z) → (X, Я, X, Z)4. Схватить:(ТБ, Я,ТБ, 0) → (ТБ, Я, ТБ, 1)Будем считать, что для решения задачи значимы лишь вышеупомянутые точки пола ТО, ТЯ,ТБ , тогда получим пространство состояний задачи, изображенное на рис. 4. Это пространствосодержит только 13 состояний, дуги графа-пространства промаркированы порядковым номеромприменяемого оператора. Пространство содержит четыре цикла хождения обезьяны между тремязначимыми точками (с ящиком или без него).

В пространстве есть также две тупиковые ветви –когда обезьяна залезает на ящик, но не под связкой бананов. Жирными дугами (стрелками)показан решающий путь, состоящий из четырех операторов: Перейти (ТЯ); Передвинуть(ТБ);Взобраться; Схватить.Рис. 4(ТО,Я,ТО,0)3(ТО,П,ТЯ,0)1121112314(ТО,П,ТБ,0)(ТБ,Я,ТБ,1)(ТБ,Я,ТБ,0)(ТБ,П,ТЯ,0)11(ТБ,П,ТБ,0)(ТЯ,П,ТЯ,0)2(ТБ,П,ТО,0) (ТЯ,П,ТБ,0)(ТО,П,ТО,0)(ТЯ,Я,ТЯ,0)13(ТЯ,П,ТО,0)Рассмотренный на прошлой лекции пример (задача об обезьяне и банане) показывает,сколь важен для успешного и эффективного решения задачи выбор представления задачи.

Такоенебольшое по размерам пространство состояний получено, в частности, вследствие того, чтоигнорировались все точки пола, кроме трех, соответствующих первоначальному расположениюобезьяны, ящика и бананов.Мощным приемом сужения пространств состояний является применение так называемыхсхем состояний и схем операторов, в которых для описаний состояний и операторовиспользуются переменные. Тем самым схема состояния описывает целое множество состояний, ане только одно, так же как схема оператора определяет все множество действий некоторого типа.В рассмотренном нами представлении задачи об обезьяне использовались схемы операторов, ноне схемы состояний.Алгоритмы поиска решенияКлассификация алгоритмовКак уже отмечалось, поиск в пространстве состояний базируется на последовательномпостроении (переборе) вершин графа состояний – до тех пор, пока не будет обнаружено целевоесостояние.

Введем несколько терминов, которые будем использовать для описания различныхалгоритмов поиска.Вершину графа, соответствующую начальному состоянию, естественно назвать начальнойвершиной, а вершину, соответствующую целевому состоянию – целевой. Вершины,непосредственно следующие за некоторой вершиной, т.е. получившиеся в результате примененияк последней допустимых операторов, будем называть дочерними, а саму исходную вершину –родительской. Основной операцией, выполняемой при поиске в графе, будем считать раскрытиевершины, что означает порождение (построение) всех ее дочерних вершин, путем применения ксоответствующему описанию состояния задачи всех допустимых операторов.Поиск в пространстве состояний можно представить как процесс постепенного раскрытиявершин и проверки свойств порождаемых вершин.

Свежие статьи
Популярно сейчас