(3,3, L ) и конечное (терминальное) состояние Sk(0,0, R ).
2. Заданы правила перехода между группами состояний. Введем понятие действия M:u, vw, где u - число миссионеров в лодке,v - число людоедов в лодке, w - направление движения лодки ( R или L ).
3. Для каждого состояния заданы определенные условия допустимости (оценки) состояний: x y ; 3-x 3-y ; uv Sk называется прямым методом поиска. Поиск Sk S0 называют обратным поиском. Поиск в двух направлениях одновременно называют двунаправленным поиском.
Как уже упоминалось, фундаментальным понятием в методах поиска в ИС является идея рекурсии и процедура BACKTRACK. В качестве примера многоуровневого возвращения рассмотрим задачу размещения на доске 8 x 8 восьми ферзей так, чтобы они не смогли "съесть" друг друга.
Допустим, мы находимся на шаге размещения ферзя в 6 ряду и видим, что это невозможно. Процедура BACKTRACK пытается переместить ферзя в 5 строке и в 6 строке опять неудача. Только возврат к 4 строке и нахождение в ней нового варианта размещения приведет к решению задачи. Читатель сам может завершить решение этой задачи на основе процедуры BACKTRACK.
x
x
x
x
x
Алгоритмы эвристического поиска
В рассмотренных примерах поиска решений число состояний невелико, поэтому перебор всех возможных состояний не вызвал затруднений. Однако при значительном числе состояний время поиска возрастает экспоненциаль
Страницы: << < 1 | 2 | 3 | 4 > >>