3. Лекция: Методы поиска решений
В лекции рассматриваются методы поиска решений в пространстве состояний, процедура BACKTRACK, алгоритмы эвристического поиска, алгоритм минимакса, алгоритм наискорейшего спуска, алгоритм оценочных функций, алгоритм штрафных функций, альфа-бета - процедура, поиск решений на основе исчисления предикатов, метод резолюции, поиск решений в продукционных системах.
Традиционными методами поиска решений в ИC считаются: методы поиска в пространстве состояний на основе различных эвристических алгоритмов, методы поиска на основе предикатов (метод резолюции и др.), поиск решений в продукционных системах, поиск решений в семантических сетях и т. д. Рассмотрим эти методы подробно.
Методы поиска решений в пространстве
Основой метода являются следующие этапы.
Определяется конечное число состояний, одно из состояний принимается за начальное и одно или… Рис. 3.1. Переходы из исходного состояния
Рис. 3.2. Метод поиска в пространстве состояний
Алгоритмы эвристического поиска
В рассмотренных примерах поиска решений число состояний невелико, поэтому перебор всех возможных состояний не вызвал затруднений. Однако при значительном числе состояний время поиска возрастает экспоненциально, и в этом случае могут помочь алгоритмы эвристического поиска, которые обладают высокой вероятностью правильного выбора решения. Рассмотрим некоторые из этих алгоритмов.
Алгоритм наискорейшего спуска по дереву решений
Рис. 3.3.
Задача состоит в том, чтобы, начиная с города А, найти минимальный путь,… Рис. 3.4.
Алгоритм оценочных (штрафных) функций
Эвристические процедуры поиска на графе стремятся к тому, чтобы минимизировать некоторую комбинацию стоимости пути к цели и стоимости поиска. Для… где d(n) - глубина вершины n на дереве поиска и w(n) - число находящихся не на… Рассмотрим вопрос о сравнительных характеристиках оценочных целевых функций на примере функций для игры в…
Алгоритм минимакса
Рис. 3.5. Дерево ходов
Развивая метод минимакса, назначим вероятности для выполняемых действий в… Интуитивно понятно, что посылать одного людоеда или одного миссионера менее эффективно, чем двух человек, особенно на…
Альфа-бета-процедура
Основная идея метода состоит в сравнении наилучших оценок, полученных для полностью изученных ветвей, с наилучшими предполагаемыми оценками для… Рис. 3.6. - отсечение
Если мы захотим опуститься до узла Z, лежащего на уровне произвольной глубины, принадлежащей той же стороне, что и…
Методы поиска решений на основе исчисления предикатов
В исчислении высказываний основным объектом является переменное высказывание (предикат), истинность или ложность которого зависит от значений… В исчислении предикатов имеется множество правил вывода. В качестве примера… которое читается так "если истинна формула A и истинно, что из A следует B, то истинна и формула B".…
Задачи планирования последовательности действий
В наших рассуждениях будут использованы примеры традиционной робототехники (современная робототехника во многом основывается на реактивном… goto(X,Y,Z)перейти в местоположение X,Y,Z
pickup(W)взять блок W и держать его
Поиск решений в системах продукций
CLIPS поддерживает семь стратегий разрешения конфликтов.
Стратегияглубины (depth strategy) является стратегией по умолчанию (default… Стратегияширины (breadth strategy) - только что активизированное правило помещается ниже всех правил с таким же…