рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Вид работы: Лекции
/
Алгоритм минимакса

Реферат Курсовая Конспект

Выберите учебное заведение

Алгоритм минимакса

Алгоритм минимакса - Лекция, раздел Образование, Лекция: Методы поиска решений В 1945 Году Оскар Моргенштерн И Джон Фон Нейман Предложили Метод Минимакса, Н...

В 1945 году Оскар Моргенштерн и Джон фон Нейман предложили метод минимакса, нашедший широкое применение в теории игр. Предположим, что противник использует оценочную функцию (ОФ), совпадающую с нашей ОФ. Выбор хода с нашей стороны определяется максимальным значением ОФ для текущей позиции. Противник стремится сделать ход, который минимизирует ОФ. Поэтому этот метод и получил название минимакса. На рис. 3.5 приведен пример анализа дерева ходов с помощью метода минимакса (выбранный путь решения отмечен жирной линией).

Рис. 3.5. Дерево ходов

Развивая метод минимакса, назначим вероятности для выполняемых действий в задаче о миссионерах и людоедах:

P([2 : 0]R) = 0; 8; P([1 : 1]R) = 0; 5;P([0 : 2]R) = 0; 9;P([1 : 0]R) = 0; 3; P([0 : 1]R) = 0; 3:

Интуитивно понятно, что посылать одного людоеда или одного миссионера менее эффективно, чем двух человек, особенно на начальных этапах. На каждом уровне мы будем выбирать состояние по критерию P_i. Даже такой простой подход позволит нам избежать части тупиковых состояний в процессе поиска и сократить время по сравнению с полным перебором. Кстати, этот подход достаточно распространен в экспертных продукционных системах.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Лекция: Методы поиска решений

В лекции рассматриваются методы поиска решений в пространстве состояний процедура BACKTRACK алгоритмы эвристического поиска алгоритм минимакса...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм минимакса

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Методы поиска решений в пространстве
Методы поиска решений в пространстве состояний начнем рассматривать с простой задачи о миссионерах и людоедах. Три миссионера и три людоеда находятся на левом берегу реки и им нужно переправиться н

Алгоритм наискорейшего спуска по дереву решений
Пример построения более узкого дерева рассмотрим на примере задачи о коммивояжере. Торговец должен побывать в каждом из 5 городов, обозначенных на карте (рис. 3.3).

Алгоритм оценочных (штрафных) функций
Умело подобранные оценочные функции (в некоторых источниках - штрафные функции) могут значительно сократить полный перебор и привести к решению достаточно быстро в сложных задачах. В нашей задаче о

Альфа-бета-процедура
Теоретически, это эквивалентная минимаксу процедура, с помощью которой всегда получается такой же результат, но заметно быстрее, так как целые части дерева исключаются без проведения анализа. В осн

Методы поиска решений на основе исчисления предикатов
Семантика исчисления предикатов обеспечивает основу для формализации логического вывода. Возможность логически выводить новые правильные выражения из набора истинных утверждений очень важна. Логиче

Задачи планирования последовательности действий
Многие результаты в области ИИ достигнуты при решении " задач для робота ". Одной из таких простых в постановке и интуитивно понятных задач является задача планирования последовательности

Поиск решений в системах продукций
Поиск решений в системах продукций наталкивается на проблемы выбора правил из конфликтного множества, как это указывалось в предыдущей лекции. Различные варианты решения этой проблемы рассмотрим на