Реферат Курсовая Конспект
Методы поиска решений в пространстве - Лекция, раздел Образование, Лекция: Методы поиска решений Методы Поиска Решений В Пространстве Состояний Начнем Рассматривать С Простой...
|
Методы поиска решений в пространстве состояний начнем рассматривать с простой задачи о миссионерах и людоедах. Три миссионера и три людоеда находятся на левом берегу реки и им нужно переправиться на правый берег, однако у них имеется только одна лодка, в которую могут сесть лишь 2 человека. Поэтому необходимо определить план, соблюдая который и курсируя несколько раз туда и обратно, можно переправить всех шестерых. Однако если на любом берегу реки число миссионеров будет меньше, чем число людоедов, то миссионеры будут съедены. Решения принимают миссионеры, людоеды их выполняют.
Основой метода являются следующие этапы.
Рис. 3.1. Переходы из исходного состояния
Рис. 3.2. Метод поиска в пространстве состояний
Теперь мы можем проанализировать полностью алгоритм простейшего поиска решений в проблемном пространстве, описанный группами состояний и переходами между состояниями на рис. 3.2. Решение задачи выделено на рис. 3.2 жирными стрелками. Такой метод поиска S0 Sk называется прямым методом поиска. Поиск Sk S0 называют обратным поиском. Поиск в двух направлениях одновременно называют двунаправленным поиском.
Как уже упоминалось, фундаментальным понятием в методах поиска в ИС является идея рекурсии и процедура BACKTRACK. В качестве примера многоуровневого возвращения рассмотрим задачу размещения на доске 8 x 8 восьми ферзей так, чтобы они не смогли "съесть" друг друга.
Допустим, мы находимся на шаге размещения ферзя в 6 ряду и видим, что это невозможно. Процедура BACKTRACK пытается переместить ферзя в 5 строке и в 6 строке опять неудача. Только возврат к 4 строке и нахождение в ней нового варианта размещения приведет к решению задачи. Читатель сам может завершить решение этой задачи на основе процедуры BACKTRACK.
x | |||||||
x | |||||||
x | |||||||
x | |||||||
x | |||||||
– Конец работы –
Эта тема принадлежит разделу:
В лекции рассматриваются методы поиска решений в пространстве состояний процедура BACKTRACK алгоритмы эвристического поиска алгоритм минимакса...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Методы поиска решений в пространстве
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов