Министерство образования и науки российской федерации федеральное агентство по образованию санктпетербургский государственный университет
 Скачать 1.41 Mb.
|
|
Last) :- stuff(X), % выбираем груз, X <> Last, % не тот, что везли только что и member(X, R), % который есть на правом берегу excl(X, R, RR), % исключаем из списка правого берега not(conflict(RR)), % на правом берегу конфликта нет incl(X, L, LL), % включаем в список левого берега write(L,"<--",X,”--”,RR), % выводим сообщение go_right(LL, RR, X). % гребем назад и помним, что везли Х goal go_right(([wolf, goat, cabbage], [ ], nil). /* Конец программы */ 26 1.11. Контрольные вопросы 1. Напишите правило для отношения двоюродный брат или сестра. Используйте правила, приведенные в подразд.1.4. 2. Имеется программа, состоящая из двух экземпляров правила a: a :- b, c, !, d, fail. a :- e. Какие предикаты будут вызваны при выполнении правила a, если каждый из предикатов b, c, d, e заканчивается успехом, а предикат fail — стандартный предикат для искусственного вызова неудачи? Что изменится, если убрать предикат отсечения? 3. Имеется предикат dosomething([]). dosomething([H|T]) :- member(H,T), dosomething(T). dosomething([H|T]) :- write(H), dosomething(T). Какой результат даст вызов dosomething([1,0, 0,1, 2,0,10])? 4. Какое отсечение, красное или зеленое, стоит в следующем правиле. Обоснуйте. sister(X,Y) :- sibling(X,Y), !, female(X). 5. Правомерно ли использование отсечения в следующем правиле? Почему? grandfather(X,Y) :- father(X,Z), !, parent(Z,Y). 27 2. Решение проблем методом поиска 2.1. Что такое метод поиска Рассмотренная в предыдущем разделе задача о волке, козе и капусте является типичным примером задачи поиска. В примере решения задачи осознанно использовался «программистский подход». На самом деле такие задачи достаточно просто формализуются к единому шаблону. Они характеризуются наличием дискретных состояний, одно из которых является начальным, другое – конечным, а также заданной логикой перехода из одного состояния в другое. Следовательно, для их решения достаточно описать начальное и конечное состояния, а также алгоритм перехода из одного состояния в другие (выбор преемника). В зависимости от того, важен ли путь к цели, может потребоваться запоминание пройденных состояний. Например, для задачи о фермере важен только путь к цели, поскольку конечное состояние задано. В других задачах наоборот, не важен путь, а нужно конечное состояние. Пример – задача о восьми ферзях, где требуется на шахматной доске расставить так, чтобы ни один из них не бил другого. Преобразуем задачу про волка, козу и капусту в новый вид. Обозначим четырьмя булевыми переменными наличие или отсутствие на левом берегу волка, козы, капусты и лодки соответственно (начальное состояние 1,1,1,1). Необходимо переместить всех на правый берег (конечное состояние 0,0,0,0). Описывать то, что находится на правом берегу нет необходимости. То, чего нет на одном берегу, есть на другом. С учетом ограничений (волка нельзя оставлять с козой, а козу – с капустой) все допустимые переходы можно отобразить в виде графа состояний (рис.2.1.). Для записи пути к цели введем еще пару переменных типа «список». В первой будет накапливаться последовательность пройденных вершин дерева решений, последняя будет использоваться для возврата результата. Запишем это на Прологе: farmer(0,0,0,0,Path,Path). % конечное состояние – все на правом берегу farmer(W,G,C, F, P, Path) :- % W,G,C,B - текущее состояние next(W,G,C,F, W1,G1,C1,F1), % выбор преемника farmer(W1,G1,C1,F1 [[W,G,C,B] | P],Path). % переход к следующему % состоянию next(W,G,C,1, W,G,C,0) :- % выбор преемника move(W,G,C,F, W1,G1,C1,F1), not(conflict(W,G,C,B)). move (1,G,C,1, 0,G,C,0). % везем волка вправо move (W,1,C,1, W,0,C,0). % везем козу вправо move (W,G,1,1, W,G,0,0). % везем капусту вправо move(W,G,C,1, W,G,C,0). % идем порожняком вправо move (W,G,C,0, W,G,C,1). % идем порожняком влево move (0,G,C,0, 1,G,C,1). % везем волка влево 28 move (W,0,C,0, W,1,C,1). % везем козу влево move (W,G,0,0, W,G,1,1). % везем капусту влево % конфликтные состояния conflict(1,1,_,0). % волк и коза на левом берегу, фермер – на правом conflict(_,1,1,0). % коза и капуста на левом берегу, фермер – на правом conflict(0,0,_,1). % волк и коза на правом берегу, фермер – на левом conflict(_,0,0,1). % коза и капуста на правом берегу, фермер – на левом Рис.2.1. Граф состояний для задачи о волке, козе и капусте Изобразим дерево решений для данной программы (рис.2.2). Поскольку Пролог начинает унифицировать предикаты в порядке их следования в программе, он реализует поиск методом «сначала вглубь» (поиск в глубину). Даже не запуская программу, мы видим, что, спускаясь по левой ветви дерева решений, Пролог впадает в бесконечную рекурсию. При этом фермер катается порожняком с одного берега на другой. В этом состоит главный недостаток метода поиска в глубину: если есть бесконечные ветви дерева, то поиск не может быть завершен. 1111 1010 1011 1000 0010 0111 1101 0100 0101 0000 Все на левом берегу Фермер и коза на правом берегу На правом берегу только коза На левом берегу только волк На правом берегу только капуста На левом берегу коза На правом берегу волк и капуста Все на правом берегу На левом берегу только капуста На правом берегу только волк 1110 Фермер на правом берегу 29 Рис.2.2. Дерево решений задачи о волке, козе и капусте Модификация данного метода путем исключения повторного перехода на уже посещенные узлы позволяет избежать бесконечного спуска по дереву: farmer(W,G,C, F, P, Path) :- % W,G,C,B - текущее состояние next(W,G,C,F, W1,G1,C1,F1), % выбор преемника not(member([W,G,C,B], P)), % исключение повторного посещения farmer(W1,G1,C1,F1 [[W,G,C,B] | P],Path). % переход к следующему % состоянию Если теперь задать предикат цели farmer(1,1,1,1,[],Path). то переменная Path будет содержать список состояний от начального до конечного по кратчайшему пути к цели. 2.2. Неинформированный поиск Рассмотренный выше пример демонстрирует неинформированный (слепой) поиск, при котором отсутствует информация о том, в правильном ли направлении он ведется. Такой поиск представляет собой комбинаторную задачу, размерность которой определяется коэффициентом ветвления (b) и глубиной (d) по формуле b d+1 . В худшем случае при поиске нужно развернуть b d+1 – 1 узлов (сам целевой узел не развертывается), а в среднем – b d+1 / 2 узлов. Размерность даже не очень сложных комбинаторных задач поражает воображение. Например, для оценки алгоритмов поиска часто используют упомянутую выше задачу о восьми ферзях, которые надо так расставить на шахматной доске, чтобы ни один из них не бил другого. Пространство состояний для такой задачи составляет приблизительно 3*10 14 узлов. При развертывании 10000 узлов в секунду на обход всего дерева потребуется приблизительно 1000 лет! В то же время человек в состоянии решить данную 1010 1111 1011 1010 1011 1010 1110 1010 1111 1111 1111 1011 0111 1011 1111 1110 1111 1110 1111 0010 1000 30 задачу за считанные минуты. Рассмотрим, какие существуют варианты и методы улучшения неинформированного поиска. Поиск в ширину. Вначале развертывается корневой узел, затем все ее преемники, затем – преемники преемников и т.д. В отличие от поиска в глубину этот метод быстро обнаруживает решение, которое находится неглубоко, и не впадает в бесконечные углубления. Существенным недостатком данного метода является необходимость запоминать все узлы- предки, количество которых также определяется формулами комбинаторики. Для упомянутой задачи о восьми ферзях при расходе памяти 1000 байт на вершину объем требуемой памяти измеряется сотнями петабайтов (1 терабайт = 1024 гигабайта, 1 петабайт = 1024 терабайта). Очевидно, что этот недостаток существенно ограничивает применимость метода. Поиск по критерию стоимости. В этом случае вначале развертывается узел с наименьшей стоимостью пути. Данный поиск применяется, если стоимости переходов от узла к узлу различны. При одинаковых стоимостях метод вырождается в поиск в ширину. Поиск по критерию стоимости дает хорошие результаты, хотя и не свободен от бесконечных блужданий. Поиск с ограничением глубины. Идея метода заключается в том, что заранее оценивается предельная глубина дерева, и спуск по ветви дерева прекращается по достижении данной глубины. Это помогает предотвратить бесконечный спуск и длительные бесцельные блуждания. Недостаток метода – необходимость располагать оценкой сложности задачи. Если установленная предельная глубина будет слишком большой, это повлечет лишние затраты на поиск, если слишком малой – цель не будет достигнута. Поиск в глубину с итеративным углублением – это поиск с ограничением глубины, которая постепенно увеличивается. Вначале устанавливается глубина 1, затем 2 и т.д. Несмотря на то, что поиск каждый раз начинается сначала, это не приводит к большим затратам. Затраты времени ненамного выше, чем при поиске в ширину, зато не требуется хранить данные о вершинах-предках. Двунаправленный поиск. Эта разновидность поиска используется в тех случаях, когда конечное состояние нам известно, а нужно найти путь к цели. Один поиск запускается с начального узла, другой – с конечного. Задача завершается, когда оба поиска находят общий узел. Преимущество метода очевидно. Пусть глубина поиска d = 6, а коэффициент ветвления b = 2. Поиск в одном направлении потребует 2 6 = 64 шага, а двунаправленный поиск 2 6/2 = 8 шагов. Недостатком данного метода является необходимость вычислимости узла – предшественника, что бывает не всегда возможным. Предотвращение формирования повторяющихся состояний. В примере задачи о фермере мы уже использовали эту модификацию метода поиска, правда, там запоминались только узлы текущего пути. В случае ложного пути в этой программе выполняется откат, и Пролог «забывает» уже пройденные узлы. Правильная модификация алгоритма поиска должна включать в список все 31 пройденные вершины. Следует, однако, заметить, что в некоторых задачах повторяющиеся состояния являются неизбежными. Одной из разновидностей метода предотвращения повторяющихся состояний является использование свойств симметричности. Например, сложность задачи о восьми ферзях или игра в крестики-нолики сокращается в четыре раза, поскольку игровое поле квадратное. Сравнительные характеристики методов неинформированного поиска сведены в таблицу 2.1.. Здесь используются следующие обозначения: b – коэффициент ветвления; d – глубина самого поверхностного решения; m - максимальная глубина дерева; e - предел глубины; С – стоимость решения; n – средняя стоимость одного шага. Таблица 2.1. Характеристики методов неинформированного поиска Метод Полнота Временная сложность Затраты памяти Оптимальност ь Поиск в ширину Да b d+1 b d+1 Да Поиск по критерию стоимости Да b 1+C/n b 1+C/n Да Поиск в глубину Нет b m bm Нет Поиск с ограничением глубины Нет b e be Нет Поиск с итеративным углублением Да b d bd Да Двунаправленный поиск Да b d/2 b d/2 Да 2.3. Информированный поиск В предыдущем разделе было показано, что в условиях отсутствия информации задача поиска может быть решена успешно, но при этом затраты времени и памяти могут быть совершенно неприемлемыми. Если задачу о ферзях попытаться решить на доске 100*100, то количество состояний будет около 10 400 . Пусть вас не введет в заблуждение компактная экспоненциальная форма представления этого числа. Число атомов в видимой части вселенной составляет около 10 80 В этой связи представляется целесообразным улучшить слепой поиск в тех случаях, когда имеется какая-либо дополнительная информация. Разумеется, мы не рассматриваем случай, когда точно известен путь к цели. В последнем случае задача уже решена. Речь идет об информации, которая наблюдается, но не дает прямого ответа, как двигаться к цели. Рассмотрим следующую задачу. Пусть нам нужно добраться из Таллина в 32 Москву воздушным транспортом. Расстояния между городами и воздушные трассы показаны на рис.2.3. Рис.2.3. Пример воздушных трасс к задаче поиска Если бы мы не располагали никакими данными о расстояниях, то имел бы место слепой (неинформированный) поиск. Если мы знаем только расстояние от текущей точки до соседних, то мы в состоянии выполнить поиск по критерию стоимости. Ближайший пункт от Таллина – Хельсинки (100км), затем – Петербург (295), Рига (476), Тверь (716), Москва(161). Общая протяженность пути – 1748 км, и она существенно отличается от оптимальной – 957 км. Предположим, что нам известно расстояние от каждого из городов до Москвы по прямой (рис.2.4). Эта информация может использоваться для выбора следующего пункта маршрута. Так, доступными пунктами из Таллина являются Хельсинки (897 км), С.Петербург (634) и Рига (839). Стремясь на каждом шаге максимально приблизиться к цели, мы выберем на первом шаге С.Петербург, на втором шаге – Тверь, затем – Москву. Общая протяженность пути равна оптимальной. Данный вид поиска называется жадным поиском по первому наилучшему соответствию. Каждый последующий узел для развертывания выбирается на основе функции оценки f(n). В связи с тем, что мы не располагаем точными оценками, используются эвристические функции h(n) или эвристики. В рассмотренном примере эвристическая функция – это расстояние до цели по прямой. Рига 161 483 716 476 276 100 377 313 295 Хельсинки С.Петербург Таллин Тверь 839 Москва 33 Рис.2.4. Расстояния до пункта назначения по прямой Эта эвристика не является заведомо оптимальной. Если, например, между Тверью и Москвой самолеты не летают, то оптимальный маршрут Таллин – Рига – Москва будет существенно отличаться от предложенного алгоритмом жадного поиска по первому наилучшему совпадению: Таллин – С.Петербург – Тверь – Рига – Москва. Рис.2.5. Жадный поиск по первому наилучшему соответствию Таллин (864) 483 716 476 276 100 377 313 295 Хельсинки (897) С.Петербург (634) Рига (839) Тверь (161) 839 Москва (0) Москва (0) 716 Рига (839) Таллин (864) 161 483 476 276 100 377 313 295 Хельсинки (897) С.Петербург (634) Тверь (161) 839 34 Жадный поиск по первому наилучшему совпадению напоминает поиск в глубину и страдает от тех же недостатков. На последней схеме без предотвращения повторяющихся состояний возможно бесконечное блуждание по отрезку С.Петербург – Тверь – С.Петербург и т.д. В наихудшем варианте сложность метода составляет b m , где b – коэффициент ветвления, m – максимальная глубина пространства поиска. Однако, хорошая эвристическая функция позволяет существенно снизить такую сложность. Оптимальный маршрут имеет минимальную протяженность, и это факт желательно использовать на каждом шаге поиска, а не в самом конце для оценки результата. Поскольку полными данными мы не располагаем, но у нас есть точная информация о пройденном пути и эвристическая оценка, мы можем использовать их для оценки общей протяженности пути на каждом этапе. Этот метод минимизации суммарной оценки стоимости решения называется А* (А звездочка). Функция оценки f(n) на каждом шаге вычисляется как f(n) = g(n) + h(n) где g(n) – стоимость достижения n-го узла, h(n) – эвристическая функция стоимости достижения цели из n-го узла. Рассмотрим функцию оценки для последнего варианта схемы воздушных трасс. При развертывании узлов от Таллина функция оценки будет принимать следующие значения. Следовательно, для развертывания узла будет выбран С.Петербург, как имеющий минимальное значение функции оценки. На втором шаге мы уже имеем накопленный путь 313 км, и функция оценки для развертывания узлов из С.Петербурга будет иметь следующие значения: Таллин Рига 276+(839) =1115 Хельсинки 100+(897) =997 С.Петербург 313+(634) =947 Таллин Рига 313+476+(839) =1628 Хельсинки 313+295+ (897) =1505 Тверь 313+483+ (161) = 957 Рига 276+(839) =1115 Хельсинки 100+(897) =997 С.Петербург 313+(634) =947 35 Следующим пунктом маршрута будет выбрана Тверь. Из Твери есть путь только в Ригу, но функция оценки намного выше, чем при движении по маршруту Таллин – Рига. Следовательно, эта ветвь (Таллин – С.Петербург – Тверь – Рига – …) заведомо не дает оптимального решения, и для развертывания нужно вместо С.-Петербурга выбрать другой город. Следующим после С.Петербурга по возрастанию функции оценки является Хельсинки. При его развертывании получаем следующие значения функции оценки: Здесь также имеем функции оценки для Риги и С.Петербурга выше, чем в ранее развернутых узлах. Следовательно, необходимо развернуть узел Рига: Из Риги мы прямо попадаем в Москву. Решение найдено и оно является оптимальным. Заметим, что функция оценки является оптимистичной, поскольку ее часть – это расстояние по прямой, а реальный путь никак не может быть короче. Таллин Рига 313+476+(839) =1628 Хельсинки 313+295+ (897) =1505 Тверь 313+483+ (161) = 957 Рига 276+(839) =1115 Хельсинки 100+(897) =997 С.Петербург 313+(634) =947 Рига 313+483+(839) =1635 Таллин Рига 100+377+(839) =1316 С.Петербург 100+295+ (634) = 1029 Рига 276+(839) =1115 Хельсинки 100+(897) =997 С.Петербург 313+(634) =947 36 В задачах поиска важным является рациональный выбор эвристической функции. Рассмотрим еще один пример логической задачи. У нас она известна как игра «15». Мы же рассмотрим упрощенный вариант на девяти клетках с восемь фишками (игра «8»). Начальное и конечное состояния могут быть, например, следующими. Фишки можно двигать по горизонтали и вертикали на свободную клетку. Средняя сложность решения составляет 22 хода. Коэффициент ветвления – 3 (4, если свободная клетка в центре, 2, если – в углу). Число состояний примерно 3 22 или 3.1*10 10 . Устраняя повторяющиеся состояния, можно сократить их количество примерно в 170 000 раз. Это состояние уже поддается контролю, но соответствующее количество состояний для игры в 15 равно 10 13 , поэтому нужно найти хорошую эвристическую функцию. В качестве таких могут использоваться следующие функции: h 1 – количество фишек, стоящих не на своем месте. На левом рисунке все фишки стоят не на своем месте, т.е. h 1 = 8. Данная эвристическая функция является допустимой, поскольку каждую фишку, стоящую не на своем месте, нужно переместить, по меньшей мере, один раз. h 2 – сумма расстояний всех фишек от их целевых позиций. Функция также является допустимой, поскольку перемещение любой фишки на одну позицию меняет функцию на единицу. Данная функция более точно отражает степень расхождения текущей и целевой позиции. Расстояние измеряется в горизонтальных и вертикальных перемещениях. На левом рисунке h 2 = 18. Вернемся к задаче о восьми ферзях. Комбинаторная сложность этой задачи диктует необходимость оценки каждой ситуации на шахматной доске, чтобы выбрать, как следует изменить расположение фигур. В качестве эвристической функции можно выбрать количество пар ферзей, которые атакуют друг друга прямо или косвенно (например, если все ферзи находятся на одной горизонтали, то реально бьют друг друга только соседние ферзи, а косвенно – каждый каждого). Используя такую эвристическую функцию, можно использовать алгоритмы |