Задача поиска в пространстве состояний

Теория Принятия Решений.

 

Литература.

Классика:

1. Пойя Д. “Математика и правдоподобные рассуждения.” М. Наука. 1975.

2. Нильсон Н. “Искусственный интеллект. Методы решения задач.”

 М. Мир. 1973

3. Попов Р. “Искусство решения проблем.” М. Мир. 1982

4. Александров “Основы теории эвристических решений.”

 М. Советское радио 1975.

5. Вагин В. Н. “Дедукция и обобщение в системах принятия решений.”

 М. Наука 1988.

 

Современные:

1. Еремеев А. П. “Экспертные модели и методы принятия решений.” М. МЭИ 1995

2. Ларичев О. И. “Теория и методы принятия решений.” М. Логос 2000, 2002

3. Тратенгерц Э. В. “Компьютерная поддержка принятия решений.” М. Синтег. 1998

4. Башлыков А. А. Еремеев А. П. “Проектирование ЭС поддержки принятия решений в энергетике.”

 

Введение.

Принятие решений (ПР). Задача принятия решений (ЗПР).

Методы теории принятия решений (ТПР).

 

 

Принятие решений

 

 

В узком смысле

- построение последовательности действий для достижения поставленной цели.

- выбор некоторой альтернативы из имеющегося множества альтернатив.

 

В широком смысле

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

 

 

Этапы ПР:

1. Осмысливание проблемной ситуации.

2. Формулировка задачи принятия решения.

Задача ПР – это любая задача, которая может быть сформулирована в терминах: цели, средства (альтернативы) и результаты.

3. Поиск (построение) множества альтернатив.

4. Оценка и выбор альтернатив для реализации.

5. Применение (реализация) альтернатив.

6. Оценка результата.

(Подключается q - множество критериев оценок. Если результат удовлетворяет оценке, то он принимается в качестве решения. В противном случае возможен возврат на любой из этапов ПР. Чем выше этап, тем больший объём работы необходимо выполнять заново)

                   -      +     конец

 

Задача ПР = T = T(G, A, R, q), где:

G – цели, A – альтернативы, R – результат, q - критерии.

 

Задача принятия решения

 

В замкнутой форме

- нет необходимости в дополнительной информации в процессе решения задачи

 

В открытой форме

- при наличии различного типа

 НЕ-факторов (неполнота знаний, нечёткость критериев и т.д.)

 

В замкнутой форме                                                          Оптимальное решение

ЗПР

В открытой форме                                                           Приближённое решение

(размерногсть велика, наличие НЕ-факторов)

F(x) = ext

Задача поиска в пространстве состояний.

(Задача эвристического поиска).

 

Пример: Шахматы. S - все состояния. S* - разрешённые состояния. S\S*- король под ударом. P – мн. ходов, которые можно делать. pi – ладья не может ходить через фигуры.   q - поставить мат за минимальное количество ходов

Считается, что любое состояние системы можно описать.

T = (S, S*, S_н, S_к, P, q)

S - множество состояний задачи (проблемной области)

 - множество допустимых состояний.

 - множество запрещённых состояний.

- множество

преобразований состояний

p_i , S_pi – множество состояний, в которых

 можно делать преобразования.

q - множество критериев.

S_н - множество начальных состояний.

S_к - множество конечных состояний.

 

Задача:

       Найти такую последовательность преобразований, применение которой к элементу из множества начальные состояний приведёт к получению элемента из множества конечных преобразований.

          

 

Композиция определяется следующим образом:

 

Если в итоге получаем несколько возможных решений, то выбираем лучшее из них по критериям q.

Любую задачу можно привести и решить как задачу поиска в пространстве состояний.

	Sн     S11              …               S120     S21 … S220    …         S21 … S220

Пример: Шахматы.

Метод перебора.

После первого хода

получаем 400 вершин

Партия длится в среднем

40 ходов и на каждом

ходу 20 возможностей.

Следовательно, полное дерево перебора будет иметь 40⁴⁰⁰ вершин.

Применение метода перебора невозможно. В этом случае вводится эвристическая функция. Как правило, она позволяет найти только приближённое решение.

       В среднем количество весов a не превышает 10 штук. Они характеризуют материал на шахматной доске, защищённость короля, возможности тяжёлых фигур. Важным параметром является динамическое изменение этих весов в зависимости от ситуации (атака, оборона).