Алгоритмы эвристического поиска

Лекция: 4)МЕТОДЫ СОЗДАНИЯ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ проектирования .

СИСТЕМЫ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ.

Изучаемые вопросы:

Методы поиска решений в пространстве

Алгоритмы эвристического поиска

АЛГОРИТМ МИНИМАКСА

Вопросы для самостоятельного изучения

Структура системы инженерной подготовки производства

Модели системы конструирования изделия класса «черный ящик»

Аннотация:В лекции рассматриваются методы поиска решений в пространстве состояний, процедура BACKTRACK, алгоритмы эвристического поиска, алгоритм минимакса, алгоритм наискорейшего спуска, алгоритм оценочных функций, алгоритм штрафных функций, альфа-бета - процедура, поиск решений на основе исчисления предикатов, метод резолюции, поиск решений в продукционных системах.

Ключевые слова:метод поиска решений, поиск решений в пространстве состояний, алгоритм эвристического поиска, поиск решений на основе исчисления предикатов, метод резолюции, поиск, метод поиска решений на основе систем продукций, семантическая сеть, бэктрекинг, процедура BACKTRACK, алгоритм, алгоритм наискорейшего спуска, глубина вершины, эвристика, целевая функция, поиск в ширину, поиск в глубину, длина пути, алгоритм минимакса, минимакс, отсечение, стратегия поиска решений в продукционных ЭС, A-GPS, strip, problem, план последовательности действий робота, игровая программа, семантика, исчисление предикатов, логический вывод, высказывание, предикат, место, подмножество, правильно построенная формула, аксиома, истинность формул, правило вывода, логическое программирование, множества, принцип резолюции, запрос, логика предикатов, импликация, прямой, обратный, вывод, ПРОЛОГ, дизъюнктивная нормальная форма, отрицание, nil, база данных, значение, выражение, входной, Prolog, programming, logic, программа, вес, Lisp, Java, планирование последовательности действий, робототехника, атомарность, планировщик , грани, множество предикатов, grip, захват, planning, system, управление роботами, список, система продукций, конфликтное множество, 'clip', база целей, очередь, strategy, default, lexing, сортировка, simplicity, specificity, complexity, random, механизмы, СПЗ, reasoning, CBR

Традиционными методами поиска решений в ИC считаются: методы поиска в пространстве состояний на основе различных эвристических алгоритмов, методы поиска на основе предикатов ( метод резолюции и др.), поиск решений в продукционных системах, поиск решений в семантических сетях и т. д. Рассмотрим эти методы подробно.

Методы поиска решений в пространстве

Методы поиска решений в пространстве состояний начнем рассматривать с простой задачи о миссионерах и людоедах. Три миссионера и три людоеда находятся на левом берегу реки и им нужно переправиться на правый берег, однако у них имеется только одна лодка, в которую могут сесть лишь 2 человека. Поэтому необходимо определить план, соблюдая который и курсируя несколько раз туда и обратно, можно переправить всех шестерых. Однако если на любом берегу реки число миссионеров будет меньше, чем число людоедов, то миссионеры будут съедены. Решения принимают миссионеры, людоеды их выполняют.

Основой метода являются следующие этапы.

1. Определяется конечное число состояний, одно из состояний принимается за начальное и одно или несколько состояний определяются как искомое (конечное, или терминальное). Обозначим состояние S тройкой S=(x,y,z), где x и y - число миссионеров и людоедов на левом берегу, z= {L,R} - положение лодки на левом ( L ) или правом ( R ) берегах. Итак, начальное состояние S₀=(3,3, L ) и конечное (терминальное) состояние S_k=(0,0, R ).

2. Заданы правила перехода между группами состояний. Введем понятие действия M:[u, v]w, где u - число миссионеров в лодке, v - число людоедов в лодке, w - направление движения лодки ( R или L ).

3. Для каждого состояния заданы определенные условия допустимости (оценки) состояний: x >= y ; 3-x >= 3-y ; u+v <= 2.

4. После этого из текущего (исходного) состояния строятся переходы в новые состояния, показанные на рис. 3.1. Два новых состояния следует сразу же вычеркнуть, так как они ведут к нарушению условий допустимости (миссионеры будут съедены).

5. При каждом переходе в новое состояние производится оценка на допустимость состояний и если при использовании правила перехода для текущего состояния получается недопустимое состояние, то производится возврат к тому предыдущему состоянию, из которого было достигнуто это текущее состояние. Эта процедура получила название бэктрекинг (bac tracing или BACKTRACK ).

Рис. 3.1.Переходы из исходного состояния

Рис. 3.2.Метод поиска в пространстве состояний

Теперь мы можем проанализировать полностью алгоритм простейшего поиска решений в проблемном пространстве, описанный группами состояний и переходами между состояниями на рис. 3.2. Решение задачи выделено на рис. 3.2 жирными стрелками. Такой метод поиска S₀ => S_k называется прямым методом поиска. Поиск S_k => S₀ называют обратным поиском. Поиск в двух направлениях одновременно называют двунаправленным поиском.

Как уже упоминалось, фундаментальным понятием в методах поиска в ИС является идея рекурсии и процедура BACKTRACK. В качестве примера многоуровневого возвращения рассмотрим задачу размещения на доске 8 x 8 восьми ферзей так, чтобы они не смогли "съесть" друг друга.

Допустим, мы находимся на шаге размещения ферзя в 6 ряду и видим, что это невозможно. Процедура BACKTRACK пытается переместить ферзя в 5 строке и в 6 строке опять неудача. Только возврат к 4 строке и нахождение в ней нового варианта размещения приведет к решению задачи. Читатель сам может завершить решение этой задачи на основе процедуры BACKTRACK.

x
		x
				x
	x
			x

Алгоритмы эвристического поиска

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

Дата добавления: 2018-04-15; просмотров: 353; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!