Интеллектуальные робототехнические системы
Аннотация: В лекции рассматриваются методы поиска решений в пространстве состояний, процедура BACKTRACK, алгоритмы эвристического поиска, алгоритм минимакса, алгоритм наискорейшего спуска, алгоритм оценочных функций, алгоритм штрафных функций, альфа-бета - процедура, поиск решений на основе исчисления предикатов, метод резолюции, поиск решений в продукционных системах.
Традиционными методами поиска решений в ИC считаются: методы поиска в пространстве состояний на основе различных эвристических алгоритмов, методы поиска на основе предикатов ( метод резолюции и др. ), поиск решений в продукционных системах, поиск решений всемантических сетях и т. д. Рассмотрим эти методы подробно.
Методы поиска решений в пространстве
Методы поиска решений в пространстве состояний начнем рассматривать с простой задачи о миссионерах и людоедах. Три миссионера и три людоеда находятся на левом берегу реки и им нужно переправиться на правый берег, однако у них имеется только одна лодка, в которую могут сесть лишь 2 человека. Поэтому необходимо определить план, соблюдая который и курсируя несколько раз туда и обратно, можно переправить всех шестерых. Однако если на любом берегу реки число миссионеров будет меньше, чем число людоедов, то миссионеры будут съедены. Решения принимают миссионеры, людоеды их выполняют.
Основой метода являются следующие этапы.
1. Определяется конечное число состояний, одно из состояний принимается за начальное и одно или несколько состояний определяются как искомое (конечное, или терминальное). Обозначим состояние S тройкой S(x,y,z), где x и y - число миссионеров и людоедов на левом берегу, z L,R - положение лодки на левом ( L ) или правом ( R ) берегах. Итак, начальное состояние S0
Страницы: 1 | 2 | 3 > >>