Лекция: Методы поиска решений - Лекция, раздел Образование, 3. Лекция: Методы Поиска Решений
...
3. Лекция: Методы поиска решений
В лекции рассматриваются методы поиска решений в пространстве состояний, процедура BACKTRACK, алгоритмы эвристического поиска, алгоритм минимакса, алгоритм наискорейшего спуска, алгоритм оценочных функций, алгоритм штрафных функций, альфа-бета - процедура, поиск решений на основе исчисления предикатов, метод резолюции, поиск решений в продукционных системах.
Традиционными методами поиска решений в ИC считаются: методы поиска в пространстве состояний на основе различных эвристических алгоритмов, методы поиска на основе предикатов (метод резолюции и др.), поиск решений в продукционных системах, поиск решений в семантических сетях и т. д. Рассмотрим эти методы подробно.
Основой метода являются следующие этапы.
Определяется конечное число состояний, одно из состояний принимается за начальное и одно или… Рис. 3.1. Переходы из исходного состояния
Рис. 3.2. Метод поиска в пространстве состояний
Алгоритмы эвристического поиска
В рассмотренных примерах поиска решений число состояний невелико, поэтому перебор всех возможных состояний не вызвал затруднений. Однако при значительном числе состояний время поиска возрастает экспоненциально, и в этом случае могут помочь алгоритмы эвристического поиска, которые обладают высокой вероятностью правильного выбора решения. Рассмотрим некоторые из этих алгоритмов.
Эвристические процедуры поиска на графе стремятся к тому, чтобы минимизировать некоторую комбинацию стоимости пути к цели и стоимости поиска. Для… где 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) - только что активизированное правило помещается ниже всех правил с таким же…
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Лекция: Методы поиска решений
Что будем делать с полученным материалом:
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Решение систем линейных алгебраических уравнений методом простых итераций и методом Зейделя
При использовании итерационных процессов, сверх того, добавляется погрешность метода.
Заметим, что эффективное применение итерационных методов существенно зависит… Сейчас разберем несколько определений которые будем использовать в этой работе.Система линейных уравнений с n…
Сравнение эффективности методов сортировки массивов: Метод прямого выбора и метод сортировки с помощью дерева
При прямом включении на каждом шаге рассматриваются только один очередной элемент исходной последовательности и все элементы готовой… Полностью алгоритм прямого выбора приводится в прогр. 3. Таблица 2. Пример… Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения.Для С имеем…
Новости и инфо для студентов