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

Теория Принятия Решений. Литература. Классика: 1. Пойя Д. “Математика и правдоподобные рассуждения.” М. Наука. 1975. 2. Нильсон Н. “Искусственный интеллект. Методы решения задач.” М. Мир. 1973 3. Попов Р. “Искусство решения проблем.” М. Мир. 1982 4. Александров “Основы теории эвристических решений.” М. Советское радио 1975. 5. Вагин В. Н. “Дедукция и обобщение в системах принятия решений.” М. Наука 1988. Современные: 1. Еремеев А. П. “Экспертные модели и методы принятия решений.” М. МЭИ 1995 2. Ларичев О. И. “Теория и методы принятия решений.” М. Логос 2000, 2002 3. Тратенгерц Э. В. “Компьютерная поддержка принятия решений.” М. Синтег. 1998 4. Башлыков А. А. Еремеев А. П. “Проектирование ЭС поддержки принятия решений в энергетике.” Введение. Принятие решений (ПР). Задача принятия решений (ЗПР). Методы теории принятия решений (ТПР). Принятие решений В узком смысле - построение последовательности действий для достижения поставленной цели. - выбор некоторой альтернативы из имеющегося множества альтернатив. В широком смысле - вся последовательность действий, начинающаяся с осмысливания ситуации и заканчивающаяся выбором найденной альтернативы. Этапы ПР: 1. Осмысливание проблемной ситуации. 2. Формулировка задачи принятия решения. Задача ПР – это любая задача, которая может быть сформулирована в терминах: цели, средства (альтернативы) и результаты. 3. Поиск (построение) множества альтернатив. 4. Оценка и выбор альтернатив для реализации. 5. Применение (реализация) альтернатив. 6. Оценка результата. (Подключается множество критериев оценок. Если результат удовлетворяет оценке, то он принимается в качестве решения. В противном случае возможен возврат на любой из этапов ПР. Чем выше этап, тем больший объём работы необходимо выполнять заново) - + конец Задача ПР = T = T(G, A, R, ) , где: G – цели, A – альтернативы, R – результат, критерии. Задача принятия решения В замкнутой форме - нет необходимости в дополнительной информации в процессе решения задачи В открытой форме - при наличии различного типа НЕ-факторов (неполнота знаний, нечёткость критериев и т.д.) В замкнутой форме Оптимальное решение ЗПР В открытой форме Приближённое решение (размерногсть велика, наличие НЕ-факторов) F(x) = ext Задача поиска в пространстве состояний. (Задача эвристического поиска). Считается, что любое состояние системы можно описать. T = (S, S*, Sн, Sк, P, ) S - множество состояний задачи (проблемной области) - множество допустимых состояний. - множество запрещённых состояний. - множество преобразований состояний pi, Spi – множество состояний, в которых можно делать преобразования. - множество критериев. Sн - множество начальных состояний. Sк - множество конечных состояний. Задача: Найти такую последовательность преобразований, применение которой к элементу из множества начальные состояний приведёт к получению элемента из множества конечных преобразований. Композиция определяется следующим образом: Если в итоге получаем несколько возможных решений, то выбираем лучшее из них по критериям . Любую задачу можно привести и решить как задачу поиска в пространстве состояний. Пример: Шахматы. Метод перебора. После первого хода получаем 400 вершин Партия длится в среднем 40 ходов и на каждом ходу 20 возможностей. Следовательно, полное дерево перебора будет иметь 40400 вершин. Применение метода перебора невозможно. В этом случае вводится эвристическая функция. Как правило, она позволяет найти только приближённое решение. В среднем количество весов не превышает 10 штук. Они характеризуют материал на шахматной доске, защищённость короля, возможности тяжёлых фигур. Важным параметром является динамическое изменение этих весов в зависимости от ситуации (атака, оборона). Методы Теории Принятия Решений. Строгие методы Ориентированы на поиск оптимального решения. ЗПР в замкнутой форме. Методы математической оптимизации. (линейное, нелинейное, дискретное программированиек) Решение оптимально   Дедуктивный вывод. (от общего к частному) AB A B Системы Принятия Решений (Decision Making ) Эвристические методы Поиск приемлемого (удовлетворяющего, допустимонго) решения. ЗПР в открытой форме. НЕ-факторы. - множество возмущений. Решение оптимально   - функция допустимости. R - отношение допустимости. Обычно это отношение нестрогого порядка . Свойства: 1) Рефлексивность a r a 2) Транзитивность arb & brc => arc 3) Асимметричность a r b & b r a =>a=b  Если в силу природы задачи не возможно отыскать оптимальное решение, то ищется приближённое. Индуктивный вывод. (от частного) AB B A Это правдоподобные методы, следовательно необходимо оценивать степень правдоподобия. Обобщённый modus ponens AB A* B* B*=A* (AB) AR1 A ~ a0 TR2 T ~ t0 (t - a0) (t - t0) => выбираем R1 Условия принятия решений. 1.Условия определенности. S – состояния. A(R) – альтернативы (частичное решение)  S  aA 2.Условия риска. Существуют ситуации, которым соответствует ряд возможных решений и их вероятности: а1,p1 S а2,p2 … Pi=1.0 an,pn 3.Условия неопределенности. Неполнота или противоречивость. Формализация цели в ЗПР. 1. Количественное задание цели ( с помощью целевой функции) Сведение ЗПР к задаче математической оптимизации. 2. Качественное задание цели. Выделяется 2 подзадачи: 1). Цель достигнута или цель не достигнута. Определяется целевое множество Xц 2). С помощью отношения предпочтения () на множестве альтернатив A . Пример. Задача сортировки (классы эквивалентности). Их частичный порядок можно задавать деревом или звездой. K1 K2 Спецификация плохо формализованных ЗПР. 1.Отсутствие явно (или количественно) выраженной целевой функции. 2.Отсутствие (априори) алгоритма поиска решения. Алгоритм строится и уточняется в процессе решения задачи. 3.Алгоритм существует, но его реализация очень сложна. 4.Существенная комбинаторность процесса поиска решения. 5.Диапазон данных и знаний, используемых в процессе решения задачи. 6.Возможность диалогового поиска решения (обращение к ЛПР в процессе решения). Пункты 1-6 влияют на процесс решения и мешают использовать методы оптимизации. Спецификация человеческого мышления при поиске решения. 1. Л.П.- рациональное мышление = дедукция + классическая аргументация. (-> A, A->B, |-B). В этом случае гипотеза принимается, если S аргументов “за” - S аргументов “против” q, где q – некоторое пороговое значение. 2. П.П. – образное мышление (правдоподобный вывод).= индукция + абдукция + аргументация(justification) A->B B___ A? Аргументация: Пусть есть аргументы “за” и аргументы “против” - веса, значения которых устанавливаются в зависимости от важности гипотез. 3. Case-based reasoning (рассуждение на основе здравого смысла). 4. Belief (вера, убеждение(мнение)). L - Квантор необходимости - Квантор возможности p  Lp Lp  LLp Mp LMp Теоретико-игровые модели принятия решения в конфликтных ситуациях. Игрой называется упрощённая формализованная модель конфликтной ситуации, а конфликликтующие стороны называются игроками. Ситуация называется конфликтной, если в ней сталкиваются интересы двух или более сторон, преследующих различные, в частном случае противоположные, цели. Однократный розыгрыш игра от начала до конца называется парией. Результатом партии являются платежи (выигрыши, проигрыши игроков) Игра состоит из ходов, то есть выборов игроков из множества возможных альтернатив. Ходы могут быть личными или случайными. Личный ход – ход, при котором игрок осуществляет сознательный выбор. Случайный ход – выбор варианта осуществляется на основе механизма случайного выбора. (бросание монеты, кости и т. п.). Игра, в которой присутствует хотя бы один личный ход, называется стратегической. Игра, состоящая из одних случайных ходов, назвается азартной. Задача Теории Игр: нахождение оптимальных стратегий игроков (т.е. обеспечение максимизации или минимизации проигрыша) в стратегических играх. Определение. Игра n лиц { A1, … , A1, H(A1 , … , An)}, где – Ai стратегия i игрока, H – платёж. Классификация Теоретико-Игровых Моделей. Дискретные Конечные Бесконечные Непрерывные Бесконечные N лиц Коалиционные (кооперативные) Некоалиционные (некооперативные) 2-х лиц Антагонистические (игры с нулевой суммой) (интересы сторон противоположны) Неантагонистические (интересы сторон не совпадают) С полной информацией (если игроку, делающему личный ход известна вся предыстория игры) С неполной информацей С нулевой суммой (суммарный платёж равен нулю) С ненулевой суммой Одноходовые Многоходовые Игровая модель для двух лиц. Игрок A :{Ai} – множество стратегий A (i=1..m) Игрок B :{Bj} – множество стратегий B (j=1..n) Игра антагонистическая. Представление игры. - в виде дерева игры. (можно построить для любой игры) - в виде матрицы (платёжной) игры. Представление игры в виде дерева. Вершины дерева – это ситуации или состояния, возможные в игре. Корень дерева отражает начальную ситуацию. Концевые вершины – это конечные состояния, взвешенные платежами. Дуги – возможные переходы из состояния под действием стратегии. Пример: Два игрока A, B. 1 ход (личный) А выбирает цифру 1 или 2. 2 ход (случайный) Если герб, то В сообщается о выборе А, иначе – нет. 3 ход (личный) В выбирает 3 или 4. Итог: Суммируются выборы игроков А и В, и если сумма чётная, то В выплачивает А, в противном случае А выплачивает В. В класс информации объединяется множество вершин дерева, в которых игроку, делающему личный ход, доступна одна и та же информация. Следовательно, данная игра распадается на две игры: с полной и с неполной информацией. Стратегии А: Стратегии В: A1 (1), Ai (2) 8 стратегий. B = (, ,) B1 = (3, 3, 3) B2 = (3, 3, 4) S2 S3 S4 … B8 = (4, 4, 4) Построение дерева игры. Поиск на дереве игры. - полный перебор (“в глубину”, “в ширину”, комбинированные методы). - сокращённый перебор (использование оценочных функций) - точная оценка (будет получено оптимальное решение) - эвристическая оценка (нет гарантий получения оптимального решения, будет получено допустимое решение). Определение. Алгоритм поиска решения называется допустимым, если он гарантирует нахождение оптимального решения. Определение. Допустимый алгоритм оптимален, если при нахождении решения, оценивается минимальное число вершин дерева. Оценка алгоритма – это оценка временных ресурсов, требуемых для оценки вершин. Методы сокращения перебора. - универсальные методы (не зависят от проблемной области). - эвристические методы (учитывают специфику задачи). Универсальные методы Метод максимина. Метод заключается в максимизации выигрыша, при минимизации проигрыша. (при отсутствии дополнительной информации). Этот метод позволяет отсекать неперспективные направления. Игрок А: (MAX) Игрок В: (MIN) Идея алгоритма: 1. Строится полное поисковое дерево на ту глубину, которую возможно позволить по затратам памяти, времени и т.д.. Число ходов должно быть чётно. 2. Концевые вершины дерева оцениваются оценочной функцией. 3. Совершается обратное движение по дереву от концевой к начальной вершине. Выбирается лучший ход игрока А. Отрицательной чертой алгоритма является то, что сначала строится всё (возможное) дерево, а затем оно оценивается. Лучшим решением было бы отсеивание неперспективных ветвей во время построения. Пример: Метод отсечения Идея метода была предложена Дж. Маккарти в 1961 г. В основе метода лежит то, что процессы построения и отсечения дерева происходят одновременно. Существуют 2 случая  отсечения: 1. Неглубокое(простое)  отсечение. 2. Глубокое  отсечение. 1.Неглубокое  отсечение Рассмотрим следующее дерево: S A A A B f(A)= ………… B C f(C)=z Пусть на известны оценки f(A)= и f(C)=z. Докажем, что если f(C), то ветви, исходящие из вершины B (на рисунке обозначенные синим цветом) можно отсечь. Т.к. игрок B стремится минимизировать оценочную функцию, следовательно оценка вершины B будет не больше z. Т.к. оценка вершины B - f(B)  f(C)  , следовательно вершина B не перспективна (потому что f(A)=, а игрок A стремится максимизировать оценочную функцию). Все вышесказанное справедливо для -отсечения. Для -отсечения : • ход делает игрок B • f(A)=  • f(C)= w 2.Глубокое  отсечение Рассмотрим следующее дерево: S A A A … ………… B f(A)= B C …… A D …… B E …… f(E)=z Пусть на известны оценки f(A)= и f(E)=z. Докажем, что если f(E), то ветви, исходящие из вершины D (на рисунке обозначенные синим цветом) можно отсечь. Т.к. игрок B стремится минимизировать оценочную функцию, следовательно оценка вершины D будет не больше z (f(D)  f(E)=z ). Т.к. игрок A стремится максимизировать оценочную функцию, следовательно оценка вершины С будет не меньше оценки вершины D (f(C)f(D)). Возможны 2 случая: 1). f(C)=f(D) , тогда f(C)=f(D)  f(E)  - т.е. имеем неглубокое  - отсечение. 2). f(C)f(D), тогда вершина D для получения оценки f(C) не использовалась. Пример. 5 S A A 5 3 B 5 7 3=z A  5 3 7=w=5 3 B 3 1 4 1=z=1 6 5 3 5 8 9 7 3=z 4 Ход Наилучшая оценка Позиция на глубину Оценка позиции Условие отсечения Действие Свой A(max)  Своя Z z -отсечение Противник B(min)  Противника W w -отсечение  возрастает при построении оценки снизу вверх  убывает при построении оценки снизу вверх Пусть оценивается дерево на n уровней. На каждом уровне имеется m вариантов выбора. Тогда сложность вычислений для метода максимина - для метода  отсечений - (при больших n ) Недостатки методов максимина и  отсечений 1). Оба метода не являются стратегиями и базируются на классических переборных алгоритмах, с использованием оценочной функции. 2). Эффект горизонта (никакие жертвы, которые не дают выигрыш в пределах обозрения программой не принимаются). Пример. Построение оценочной функции для игры в шахматы. f(s)= , f1 – оценка, учитывающая алгебраическую стоимость фигур; f2 – оценка, учиьываюшая относительную безопасность короля; f3 – оценка, учитывающая подвижность фигур; f4 - оценка, учитываюшая степень контроля центра; f5 - оценка, учиваюшая пешечный строй; f6 – оценка, учитывающая аттакующие позиции; Матричное представление парной антагонистической игры. Число стратегий конечно. Игрок A: {Ai} i=1…m Игрок B: {Bj} j=1…n Ai \Bj B1 … Bj … Bn A1 a11 … a1j … a1n … … … … … … Ai ai1 … aij … ain … … … … … Am am1 … amj … amn aij – это выигрыш игрока A при выборе им стратегии Ai, и игрок B отвечает ему стратегией Bj. Пример. Построим матрицу игры. Возможны два случая: 1. Ситуация с неполной информацией. (Игроку В не сообщается о выборе игрока А). 2. Ситуация с полной информацией. B3(+) - игрок В действует также, как и игрок А. Вводятся две величины: max min aij =  нижняя оценка цены игры i j min max aij =  верхняя оценка цены игры i j Докажем, что  <= Ai \Bj B1 … Bj’ … Bj … Bn A1 a11 … a1j … a1j … a1n … … … … … … … … Ai’ ai1 … ai’j’ … ai’j … ain … … … … … … … … Ai ai1 … aij’ … aij … ain … … … … … … Am am1 … amj … amj … amn aij’ =  <=aij<= ai’j’  Если  = = V, то говорят, что игра имеет седловую точку, а решением игры является пара чистых стратегий Ai*,Bj* , дающая максимальный выигрыш и минимальный проигрыш равный V равный цене игры. Теорема 1. Всякая парная антагонистическая игра с полной информацией решается в чистых стратегиях, причём это решение обладает свойством устойчивости. Пример: max min aij =  max min aij =  i j i j min max aij =  min max aij =  i j i j Седловой точки нет (A1 ,B4) = (A2 ,B4) = V = 5 Если нет седловой точки: 1) Однократно, следовательно, необходимо использовать наиболее осторожный метод maxmin. 2) Многократно – используются смешанные стратегии. то есть каждой стратегии соответствует вероятноть: Ai , pi pi Bj , qj qj Решением будет смешанная стратегия SA =( p1, p2…, pN) SB =( q1, q2…, qN) Теорема 2. (Основная теорема теории игр) Всякая парная антагонистическая игра имеет хотя бы одно решение, то есть пару стратегий SA*, SB* в общем случае смешанных, дающих устойчивый выигрыш равный цене игры V. И в этом случае можно доказать, что:  <=V<= SA - чистая стратегия, следовательно SA = (0, …, 0, 1, 0, …. ,0) Методы решения матричных игр. 1) Проверить на наличии седловой точки. 2) Если нет седловой точки, то матрицу игры упрощают. Из матрицы игры исключают доминируемые и дублируемые стратегии. Задача: найти стратегии SA =( p1, p2…, pN) и SB =( q1, q2…, qN), дающие максимальный средний выигрыш. Игра mxn, число активных стратегий будет равняться min(m,n) Определение. Стратегия Ai доминирует () Ak, то есть Ai Ak, значит: j aij akj Определение. Стратегия Ai дублирует (=) Ak, то есть Ai = Ak, значит: j aij = akj Стратегия Bj Br, i aij arj Стратегия Bj = Br, i aij = arj Пример: игра (5x5) A1 A4 A2 = A5 B1 B2 B1 B5 A21 = A5 Получим SA = (p1, p2, 0, 0, 0) SB = (q1, 0, q2, 0, 0) Метод Лагранжа Этот метод используется в играх с квадратной матрицей игры G(m,m). B1 B2 A1 а11 а12 A2 а21 а22 SA=(p1,p2) - вектор вероятностей выбора стратегий игроком А. SB=(q1,q2) - вектор вероятностей выбора стратегий игроком В. Пусть игрок А использует смешанные стратегии, а В чистые, тогда выигрыш составит: V1=a11*p1+a21*p2 V2=a12*p1+a22*p2 если же В также использует смешанные стратегии, то выигрыш составит: V=( a11*p1+a21*p2)*q1+( a12*p1+a22*p2)*q2 Строится функция Лагранжа: L=(a11*p1+a21*p2)*q1+(a12*p1+a22*p2)*q2+1*(p1+p2-1)+ 2*(q1+q2-1) q1 , q2 p1 , p2 p2 =1- p1 q2 =1- q1 Получим ; ; ; Пример. G(2,2) B1 B2 A1 4 2 A2 3 6 Метод линейного программирования Этот метод используется в играх с произвольной матрицей игры G(m,n). B1 B2 … Bj … Bn A1 а11 а12 … а1j … а1n A2 а21 а22 … а2j … а2n … … … … … … … Ai аi1 аi2 … аij … аin … … … … … … … Am аm1 аm2 … аmj … аmn SA=(p1,p2,…, pi,…, pn) - вектор вероятностей выбора стратегий игроком А. SB=(q1,q2,…, qj,…, qn) - вектор вероятностей выбора стратегий игроком B. Требование, накладываемое на матрицу - i , j aij>0 Для того, чтобы произвольная матрица удовлетворяла этому требованию ищется M=мах(|аij||aij0) и прибавляется ко всем элементам, получаем aij+M>0. Пусть А выбирает смешанную(оптимальную) стратегию, а В чистую: Введем величину0, i=1,…,m Тогда: (*) xi0 i=1,…,m Т.к. Получаем задачу линейного программирования: при системе ограничений (*). Решив ее, найдем (x1, x2,…, xm) и Зная V, найдем pi=xi*V. Итерационный метод Брауна-Робинсона Этот метод ориентирован на произвольную игру G(m,n). Не требует условия aij>0. Рассмотрим метод на примере игры G(3,3). B1 B2 B3 A1 7 2 9 A2 2 9 A3 9 11 SA=(p1,p2,p3) SB=(q1,q2,q3) Строится следующая матрица: k i B1 B2 B3 j A1 A2 A3 V V V* 1 3 9 11 2 2 9 9 4.5 2 2 11 9 11 2 4 18 4.5 9 6.75 3 2 13 18 11 3 13 18 11 3.67 6 4.84 4 … … … … … … … … … … … где: k – номер партии i – номер стратегии, выбираемой игроком A j – номер стратегии, выбираемой игроком В Bi – накопленный игроком А выигрыш за k партий, при условии, что в данной партии B выбирает стратегию Bi Аj – накопленный игроком В проигрыш за k партий, при условии, что в данной партии A выбирает стратегию Аj. V – нижняя оценка игры = min (накопленный выигрыш)/k V – верхняя оценка игры = max (накопленный проигрыш)/k Доказано, что V*=(V+V)/2, V*  V при k   и - cколько раз выбирается Аi стратегия - cколько раз выбирается Bj стратегия Пример. Задача о двух КБ Объявлен конкурс на выполнение 2-х проектов. На проект 1 выделено а денежных единиц. На проект 2 выделено b денежных единиц. В конкурсе участвуют 2 КБ: КБ1(А) – 4 отдела, КБ2(В) – 3 отдела. Практика показывает, что если КБ выделяет больше отделов на проект, то оно и получает этот проект, если же они выделяют одинаковое количество отделов, то получения проекта КБ1 и КБ2 равновероятны. Стратегии: (,) -  - количество отделов, выделяемых под первый проект  - количество отделов, выделяемых под второй проект КБ1(А): А1=(4,0); А2=(3,1); А3=(2,2); А4=(1,3); А5=(0,4). КБ2(В): В1=(3,0); В2=(2,1); В3=(1,2); В4=(0,3); Для того, чтобы свести парную игру к антагонистической, вычисляем средний выигрыш – (a+b)/2 и вычитаем его из V. G(5,4): В1 В2 В3 В4 А1 а/2 (a-b)/2 (a-b)/2 (a-b)/2 А2 b/2 a/2 (a-b)/2 (a-b)/2 А3 (b-a)/2 b/2 a/2 (a-b)/2 А4 (b-a)/2 (b-a)/2 b/2 a/2 А5 (b-a)/2 (b-a)/2 (b-a)/2 b/2 Пусть а=b. В1 В2 В3 В4 А1 a/2 А2 a/2 a/2 А3 a/2 a/2 А4 a/2 a/2 А5 a/2 В1 В4 А2 a/2 А4 a/2 SA=(0,1/2,0,1/2,0) SB=(1/2,0,0,1/2) p1=p2=1/2 q1=q2=1/2 V=( a11*p1+a21*p2)*q1+( a12*p1+a22*p2)*q2=a/4 VКБ1=a/4+a=5a/4 VКБ2=3a/4 Парная игра с произвольной суммой. (биматричная игра). Игра G(m,n) Выигрыши игрока А Выигрыши игрока В Две данные матрицы объединяют в одну: Нет общей теории решения биматричных игр. В данном классе игр могут быть коалиции, договорённости. Теория некооперативных игр Нэша. Необходимо найти решение в виде: SA =( p1, p2…, pN) SB =( q1, q2…, qN) Вводится понятие – ситуация равновесия: SA*=( pi*) i=1..m SB*=( qj*) j=1..n Определение. SA* и SB* является ситуацией равновесия, если онаудовлетворяет следующим условиям: Для игрока А : Для игрока В : По Нэшу, решением биматричной игры является ситуация равновесия при условии, что они взаимозаменяемы. Нэш доказал, что для любой биматричной игры существует ситуация равновесия, но нет общего метода её поиска. Модели биматричных игр, к которым плохо применима теория Нэша. 1. Проблема узника. Игра 2х2. Два узника находятся в разных камерах, Обвиняются в одном преступлении. Интерпретация стратегий: А1 В1 – кооперативная стратегия – молчать. А2 В2 – некооперативная стратегия – давать показания на другого. А2А1 и В2В1 вторые стратегии доминируют , и ситуацией равновесия будет А2 В2 = ( -6 , -6 ), но точка ( -1 , -1 ) более выгодна. 2. Конкурирующие фирмы. А1 В1 – сохранение уровня цен. А2 В2 – снижение цен. По теории Нэша: А2А1 и В2В1 , следовательно ситуацией равновесия будет А2 В2 = ( 3 , 3 ), но лучше точка А1 В1 = ( 5 , 5 ). 3. Семейный спор. А – муж. В – жена. А1 В1 – пойти на футбол. А2 В2 – пойти в театр. В данном случае получаем две ситуации равновесия (2,1) – А1 В1 и (1,2) – А2 В2 , но они неравноценны. Эти игры неразрешимы в смысле Нэша. Рефлексивные игры. В данном классе игр противники строят модели поведения друг друга. Игрок А начинает рассуждать за В. Матрица принимает следующий вид: В рефлексивной игре выигрывает тот игрок, у которого ранг рефлексии больше на единицу. Если ранг рефлексии больше более чем на единицу, то исход не ясен. Пример: В фирме есть два отдела: П – производственный Т – транспортный. Доход П от выпуска 1 машины = a. Затраты Т на перевоз 1 машины = c. Если продукт не вывозится, то затраты на хранение = b , и они делятся пополам между П и Т. В общем виде матрица игры имеет вид: Необходимо выяснить, что рекомендовать Производственному отделу. Пусть a = 10, b = 6, c =2. Воспользуемся методом maxmin. Если П и Т – враги, то рекомендуется стратегия П1, так как 37 –гарантированный выигрыш больше чем 22. Но поскольку П и Т это отделы одной фирмы, П рекомендуется выбрать стратегию П2. В этом случае Т выберет Т3 или лучше Т4, и выигрыш П будет 74 или 100. Основы теории стохастических решений (игры с “природой”) В этих играх существует некая объективная реальность, которая может влиять на процесс принятия решения. Рассмотрим игру в матричной форме G(m,n). Здесь аij – выигрыш игрока А при выборе им стратегии Аi в состоянии природы ПJ. Использование методов теории антагонистических игр невозможно, т.к. нет сознательного противодействия противника (за исключением метода максимина). В играх с природой вводят понятие риска: Риск: Т.о риск – это разность между выигрышем, который игрок получил бы, зная, в каких условиях Пj он принимает решение, и выигрышем, который он получает, не зная условий, когда он выбирает стратегию Ai. Пример: Матрица выигрышей Матрица рисков Возможны различные ситуации: 1. Ситуация 1 .Стохастическая неопределенность Известны вероятности состояний «природы»:  Пj  qj, j=1,…,n Тогда для поиска оптимального решения применяется критерий Лапласа: оптимальной является та стратегия, которая максимизирует средний выигрыш (матожидание выигрыша): Эта же стратегия будет минимизировать средний риск: Пример: q1=0.1; q2=0.5; q3=q4=0.2. a1 = 1*0.1+4*0.5+14*0.2=4.9 a2 = 3*0.1+8*0.5+7*0.2=5.7  А2 - оптимальная стратегия a3 = 4*0.1+6*0.5+8*0.2=5 r1 = 3*0.1+4*0.5+1*0.2=2.5 r2 = 1*0.1+0*0.5+8*0.2=1.7  А2 - оптимальная стратегия r3 = 0*0.1+2*0.5+7*0.2=2.4 2. Ситуация 2 . Вероятности qj неизвестны или их не существует. В этом случае может использоваться ряд критериев поиска оптимального решения: 1. Критерий Вальда (крайнего пессимизма) – стратегия максимизирующая минимальный выигрыш. 2. Критерий Сэвиджа – стратегия, минимизирующая максимальный риск 3. Компромиссный критерий Гурвица В качестве оптимальной выбирается стратегия, зависящая от параметра пессимизма (оптимизма). k - критерий осторожности или пессимизма 0k1 k=0 – максимизировать максимально возможный выигрыш k=1 – критерий Вальда Если нет дополнительной информации, то рекомендуется брать k  0.6 При выборе оптимальной стратегии брать надо ту, которую советуют большинство критериев. Замечание: В играх с природой не используются смешанные стратегии по следующим причинам: • в антагонистических играх смешанные стратегии применяютсячасто для того, чтобы обмануть, запутать противника, что в играх с природой не имеет смысла. - аппарат смешанных стратегий ориентирован на получение максимального среднего выигрыша - того выигрыша, который будет получен при многократном повторении игры, но этом накапливается вероятность qi, которая может дать информацию в чистых стратегиях. Пример: Матрица выигрышей Матрица рисков 1. Критерий Вальда - A1 2. Критерий Сэвиджа – A3 3. Критерий Гурвица - A3 Выбираем стратегию A3. Игры с упорядоченными исходами. Игры при наличии нескольких критериев. Пример: Ожидается нашествие вирусов В1, В2, В3 . В1, В2, В3 – типы вирусов. V1, …, V7 – типы вакцин. Эффективность вакцины Vi - i {1,2,3,4} Стоимость(дешевизна) - обратная индексу вакцины величина , т. е. вакцина с меньшим номером дороже всех. i {1,2,3,4,5,6,7} Vi(Bj)=(i, j)  (max, max) V2  V1 V5 V3, V4 V7 V6 Получили множество Парето {V2, V5, V7} а) вирус тяжелый, но не массовый - V2 б) вирус не очень сильный, но массовый - V7 в) средний случай - V5 Общие выводы по теоретико-игровым моделям. Игровая модель является математическим упрощением реального конфликта, и при этом вводятся следующие основные предположения: 1) Предполагается, что противник также разумен как и сам игрок. 2) Теория игр ориентирует ЛПР на наиболее осторожное поведение, на исключение риска (определенный риск в играх с “природой”) 3) Предполагается, что игроку известны все стратегии противника, неизвестно лишь то, какую он выберет в процессе игры. Пример. Нужно перевести груз по морю из начального пункта А в конечный пункт В П1 – шторм; П2 – туман; П3 – ясно. П1 П2 П3 i wi hi А1 10 20 20 8 А2 -100 200 -100 200 20 А3 10 10 10 10 10 10 П1 П2 П3 Si А1 10 180 180 А2 110 10 110 А3 190 190 Вальд - А3 Сэвидж - А2 Гурвиц - А2 Если все события равновероятны q1 =q2=q3=1/3 a1=10 a2=100/3  А2 a3=10 r1=190/3=63 r2=120/3=40  А2 r3=63 то и Лаплас дает вторую стратегию. Но путь А2 в 2/3 случаев опасен. Пример 2. Случай в Ново-Гвинейском море Японцы: Американцы: Я1 – юг А1 – послать самолеты на юг Я2 - север (есть три дня на бомбежку) А2 – послать самолеты на север (1день – поиск,2 – бомбежка) 2 – седловая точка Рациональное и иррациональное поведение ЛПР. Теория рационального поведения. (Теория ожидаемой полезности). Фон Нейман, О Моренштерн. 6 аксиом. Функция ожидаемой полезности. Лотерея: А – множество исходов: x, y, z, … Известны вероятности исходов: p, q, r, … (x, p, y) – вектор с двумя возможными исходами: x => p y => 1-p Лотерея обозначается следующим образом: Средняя цена лотереи (x, p, y): xp + y(1-p) Аксиомы рационального выбора: А1: Все возможные исходы должны принадлежать А. x (xA) А2: На множестве исходов должно быть задано отношение строго предпочтения P(>), нестрогого R(), безразличия I(), причём PR, IR и они удовлетворяют двум условиям: 1) Связности, то есть либо справедливо xRy, либо yRx. 2) Транзитивности, то есть из xRy & yRz => xRz. А3: Две лотереи ((x, p, y), q, y) и (x, pq, y), находятся в состоянии безразличия, то есть справедливо: ((x, p, y), q, y) I (x, pq, y) А4: Если xIy, то (x, p, z) I (y, p, z). А5: Если xPy, то xP(x, p, y)Py. А6: Если xPyPz, то существует вероятность p, такая, что yI(x, p, z). Теорема: Если выполняются аксиомы А1-А6, то существует информация полезности, определяемая на множестве исходов А, для которых выполняются следующие условия: 1) xRy  U(x) U(y). 2) U(x,p,y) = pU(x) + (1-p)U(y) U(x) U(y), aU(x) aU(y) При a>0 Пример. Есть два типа урн. 700 штук 300 штук Решение ЛПР: d1 +350 (если угадано верно) - 50 (если не верно) d2 +500 (если угадано верно) - 100 (если не верно) Тип урны Вероятность выбора урны Выигрыш при выборе d1 d2 1 0.7 350 -100 2 0.3 -50 500 U(d1) = 0.7*350 – 0.3*50 = 230 U(d2) = -0.7*100 + 0.3*500 = 80 d1 – предпочтительнее. Процесс выбора в ЛПР или ДР. - личный ход. – случайных ход. Pк(y1) = P(к|н1) = 0.6 Вероятность вытянуть красный шар из урны 1 Pк(y2) = 0.3 Pч(y1) = 0.4 Pч(y2) = 0.7 Pк = P(к) = Pк(y1)*P(y1) + Pк(y2)*P(y2) = = 0.6*0.7 + 0.3*0.3 = 0.51 Pч = 0.49 P(y1|к) = 0.6*0.7/0.6*0.7 + 0.3*0.3 = 0.82 P(y2|к) = 0,18 P(y1|ч) = 0,57 P(y2|ч) = 0,43 P(yi|к) = (Pк(yi)* P(yi)) / / (Pк(y1)*P(y1) + Pк(y2)*P(y2)) Парадоксальные поведения ЛПР. Парадокс Алле: U(5) = 1 U > 0.1*1 + 0.85*U U > 10/11 U < 10/11 U(2) = U U(0) = 0 Теория субъективной ожидаемой полезности Позволяет формализовать иррациональное поведение ЛПР. Пример. Парадокс генерала. Генерал проиграл сражение. Чтобы спасти остатки армии, у него есть 2 пути отступления: Ситуация Л1: 2000 спасены d1 1/3 6000 спасены d2 2/3 0 спасены Большинство ЛПР выбирают d1. Ситуация Л2: 4000 погибает d1 1/3 никто не погибает d2 2/3 6000(все) погибают Большинство ЛПР выбирают d2 В зависимости от того, в терминах выигрышей или потерь сформулирована задача, выбираютс различные решения. Для того чтобы учесть поведение человека, был исследован ряд эвристик, которые побуждают ЛПР действовать нерационально: 1. Суждение по представительности. Принимая решение, ЛПР сравнивает ситуацию a c типовой ситуацией из класса K и принимает такое же решение. Пример Пусть есть 2 группы специалистов Г1: 70 инженеров + 30 юристов Г2: 30 инженеров + 70 юристов Дается типовое описание представителя класса инженеров и юристов. Предъявляется субъект, и определяется, с какой вероятностью он является инженером и юристом. При этом ЛПР принимает решение, не учитывая вероятности. 2. Суждение по встречаемости. Принимая решение, ЛПР ориентируется на частоту встречаемости данного явления в своей повседневной жизни. 3. Суждение по точке отсчета. Начальная информация может существенно влиять на принятие решения. 4. Сверхдоверие ЛПР к собственному опыту. 5. Стремление к исключению риска. ЛПР, скорее всего, выберет не самое лучшее решение, чтобы избежать риска больших потерь. Причины нерационального поведения ЛПР 1. Недостаток информации у ЛПР в процессе принятия решения. 2. Недостаток опыта. 3. Поиск относительно множества критериев. 4. Временные ограничения. Основные постулаты теории субъективной ожидаемой полезности (Теории проспектов) 1). Эффект определенности ЛПР, как правило, предпочитает детерминированный исход недетерминированному. 2). Эффект отражения В зависимости от формулировки задачи (в терминах выигрыша или проигрыша) ЛПР принимает разные решения. 3). Эффект изоляции Если у ЛПР есть 2 варианта выбора и в них есть одинаковые исходы, то они выбрасываются. Проспект P(x,p,y,q) – проспект. В нем вводится вероятность q для исхода y, p+q<1. p x 1-p-q 0 q y Вводится функция субъективной ожидаемой полезности: V=W(p)*V(x)+W(q)*V(y) , где (*) V(x), V(y) – цены исходов x и y, W(p), W(q) – важности вероятностей p и q. По определению V(0)=0. На функции V и W накладываются определенные ограничения: V(x): 1). V(x) – монотонная функция 2). Спад V(x) круче при отрицательных x W(x): 1). W(x) монотонна и не подчиняется требованиям теории вероятностей W(p)+W(1-p)< 1 2). W(0)=0, W(1)=1 W(p) 0 1/2 1 p 3). W(p)>p при малых p; W(p)

W(0,1)*1+(0,89)*U U > W(0,1)/(1-W(0,89)) 0,1 5 d1 0,9 0 0.11 1 d2 0,89 0 ЛПР выбирает d1. W(0,1)*1 > W(0,11)*U U < W(0,1)/W(0,11) W(0,1)/W(0,11) >U > W(0,1)/(1-W(0,89)) W(p)+W(1-p) < 1 W(p) <1 - W(1-p) Парадокс теории проспектов p1=($101;0,5;$51;0,27) p2=($100;0,5;$50;0,3) Если ЛПР округляет вероятности, то предпочтительнее p1; Если ЛПР округляет выигрыши, то предпочтительнее p2; Если и то, и другое, то p1 I p2(они находятся в отношении безразличия). Для p1 ожидаемый выигрыш - 101*0,5+51*0,27=64,27 Для p2 - 100*0,5+50*0,3=65 Замечание Хотя процедура редактирования проспекта может привести к противоречию, теория проспектов все же является полезной аксиоматической теорией, позволяющей объединить дескриптивные знания о поведении ЛПР и нормативные правила их рационального поведения. Коллективное принятие решений. I. Принятие решений в больших группах. (Системы голосования.) Системы голосования: - демократичность (1 человек – 1 голос), - рациональность (отсутствие противоречий в системе голосования), - результативность (отыскание решения). 1) Принцип Кондорсе. - побеждает тот, кто является наилучшим при попарном сравнении с любым кандидатом. X – множество кандидатов. (множество решений). xi xj (xixj) xi – победитель. Парадокс системы Кондорсе. А, В, С – кандидаты. Всего 60 избирателей. Проводим сравнение: А и В: 23+10 = А(33) 17+2+8= В(27) => АВ А и С: 23+2 = А(25) 17+10+8= С(35) =>СА В и С: 17+2 = В(42) 23+10+8= С(18) =>ВС => АВ, ВС, СА нарушается условие транзитивности => не рациональна. Улучшение принципа Кондорсе. - победитель тот, кто набрал больше первых мест. А(33), В(19), С(18) => А – победитель. 2) Принцип большинства. 3) Метод Борда. Рейтинговое голосование. Если участвуют n кандидатов, то кандидат занявший первое место получает n баллов. Занявший второе место – n-1 балл, … , n - 1 балл. А: 23*3 + 2*2 +35*1 = 108 В: 19*3 + 16*2 + 25*1 = 114 С: 18*3 + 32*2 + 0*1 =138 => С – победитель. Для первого примера: А: 23*3 +12 *2 + 25 = 118 В: 19*3 + 31*2 + 10 = 124 С: 18*3 + 17*2 + 25 = 113 => В – победитель. Парадокс Борда. По Барду: А(122), В(121), С(137) => С – победитель. Многоуровневая система голосования. Пример: Во второй тур выйдут А(23) и В(19) Второй тур: А(33), В(27) => А – победитель. Изменим 3 строку: Во второй тур выйдут А(25) и С(18) Второй тур: А(25), В(35) => С – победитель. Аксиоматическая теория Эрроу (Arrow). Система голосования: - демократическая, - рациональная, - результативная. А1: УНИВЕРСАЛЬНОСТЬ. СГ – универсальна, следовательно она позволяет учитывать все возможные распределения голосов. А2: ЕДИНОГЛАСИЯ. Если кандидат побеждает относительно личных предпочтений, то он побеждает и относительно коллективного предпочтения. А3: НЕЗАВИСИМОСТИ. (от несвязанных альтернатив). Если есть несколько кандидатов и АВ, то отношение к кандидату не должно влиять на отношение между А и В. А4: ПОЛНОТЫ. СГ должна позволять сравнивать любую пару кандидатов (нет несравнимых). А5: ТРАНЗИТИВНОСТЬ. Если В “не лучше” А, а С “не лучше” В, то С “не лучше” А. Теорема. (О невозможности) Нельзя построить СГ, которая удовлетворяет всем трём принципам. Если СГ удовлетворяет всем пяти аксиомам, то эта система является диктатором. Она навязывает избирателям своё предпочтение. Недемократична. Были предприняты попытки изменить аксиомы. А1. Д. Блейк. АВ и ВС, А ближе, а С дальше. А5. А Сен. Принцип консенсуса: правило транзитивности работает только при строгом предпочтении. Иначе А и С равнозначны. Коллективное безразличие. I I. Коллективное принятие решений в малых группах. (Групповое принятие решений.) Традиционный метод – совещание. + Каждый может высказать своё мнение. + Каждый может выслушать мнение оппонента. – Чрезмерное влияние лидера / группы лидеров. – Большая и неэффективная трата времени, если мнения участвующих существенно расходятся. – Применение принципа большинства, что игнорируют мнение отдельных членах группы (КПР). Основные направления в области ГПР. 1. Использование теории неантагонистических игр (коалиционных). 2. Привлечение координатора. 3. Разработка систем поддержки принятия групповых решений. Многокритериальные ЗПР Пусть существует ряд критериев . Каждый критерий индуцирует отношение предпочтения на множестве X. Можно использовать свертку , называемую также обобщенным критерием, и решать задачу: . В качестве решения получим множество Парето. Возможны следующие ситуации: 1. Все критерии равнозначны (несравнимы). Т.е. глобальное предпочтение равно пересечению предпочтений по всем i критериям. Определение 1 x – оптимальное решение, если . Определение 2 Из двух решений решение называется доминирующим по отношению к (), если выполняется и, кроме того , по крайней мере для одного : . Определение 3 Решение называется улучшаемым, если существует хотя бы одно решение , такое, что , и хотя бы для одного : , в противном случае решение не улучшаемое или эффективное. Определение 4 Множество , состоящее из эффективных решений называется множеством решений, оптимальных по Парето. Пример. - множество Парето 2. Критерии сравнимы. 1. Метод выделения главного критерия Пусть имеется главный критерий . Тогда решаем задачу В этом случае может оказаться, что решения не существует. Тогда нужно ослабить требования - 2. Метод последовательных уступок. 1 шаг - получим решение 2 шаг ……………………… n шаг Если решение существует, то возможны 2 случая: a). Решение устраивает ЛПР b). Решение не устраивает ЛПР: - решение единственное - решение не единственное Проблема сокращения поискового пространства 1). Сочетание точных и грубых методов. Грубые методы - сокращают область поиска решения Точные методы - ищут оптимальное решение. 2). Использование эвристических функций. 3). Человеко-машинные процедуры поиска оптимального решения. 1). ЛПР задает начальное значение опорного плана и весовых коэффициентов - скорость изменения решения по i-му критерию. 2). Коректир. Поиск решения в пространстве состояний на основе эвристической функции Задача эвристического поиска , где S – множество состояний; - множество допустимых состояний; - множество начальных состояний; - множество конечных состояний; - множество преобразований. Задача: нахождение последовательности преобразований : Система поиска + U-ветвление. Вводится предикат P, определенный на множестве , который имеет значение истина, если это ветвление может быть применено. U- ветвление корректно  Способы сокращения поискового пространства 1). Укрупнение пространства поиска. Переход от элементарных состояний к макросостояниям. Проблема поиска решается в укрупненном пространстве. 2). Использрвание эвристик. 3). Изменение представления задачи. Пример Вопрос: сколько ходов нужно сделать, чтобы поменять коней местами. 1 2 3 4 5 6 7 8 9 Ответ: 16 ходов (4 – если разрешить им передвигаться || ) Поиск решения на основе эвристической функции. Допустимый алгоритм – это тот алгоритм, который гарантирует отыскание решения. Оптимальный алгоритм – это допустимый алгоритм, который находит решение за минимальное число шагов. f(s) = f1(s) + f2(s) -> min f1(s) – оценка пройденного пути. f2(s) – оценка оставшегося пути. _ _ _ f(s) = f1(s) + f2(s) -> min Теорема. Чтобы алгоритм, построенный на основе эвристической функций f был допустим, необходимо и достаточно, что . Алгоритм А1 более информирован, чем А2  Критерий эффективности алгоритма поиска. 1) Стоимость решающего пути. S -> min. (допустимый алгоритм) 2) Количество раскрываемых при поиске вершин. (оптимальный алгоритм) 3) Объём вычислений, требуемых для получения оценки V -> min. 4) Интегральная оценочная функция. S + N + V -> min Критерии оценки эффективности эвристических алгоритмов. 1) Критерий направленности. P L – длина найденного пути в числе раскрываемых вершин. T – общее число раскрываемых вершин. P = 1 => минимальное число вершин. 2) Критерий эффективности ветвлений. B 3) Оценка качества приближённого решения. K K = 0 => оптимальное решение. Базовые эвристики сокращения поискового пространства. 1) Перебор этапами (метод maxmin). 2) Ограничение числа дочерних вершин ( отсечение) 3) Упорядочение преобразований Pi () Пример: P(s) – сумма расстояний каждой фишки от своего места. Q(s) – Если фишка нецентральная, то за неё даётся 2 очка, когда за ней следует целевая (фишка на своём месте); Если фишка центральная, то за неё даётся 1 очка, когда за ней следует целевая (фишка на своём месте); Задача эвристического поиска Задача эвристического поиска , где S – множество состояний; - множество допустимых состояний; - множество начальных состояний; - множество конечных состояний; - множество преобразований. Правила преобразований (P: SS) могут быть заданы в виде продукционных правил: Пусть на вход поступает . Возможны следующие ситуации: 1). P не применимо к (). Возможны два случая: a). Нет применимых правил (база правил P не полна). b). Процесс поиска бесконечен. 2). P применимо к (). Возможны два случая: a). Результат конечен: - единственный; - неединственный (можно говорить о поиске оптимального (наилучшего) решения относительно критерия Q). b). Результат бесконечен. Допускается бесконечное ветвление, при том условии, что если был выбран какой-то путь, то до конца добираемся за конечное число шагов. Типы задач 1. Задача планирования. известны: и . найти: последовательность преобразований 2. Задача прогнозирования. известно: найти: 3. Задача диагностики. известно: найти: Поиск в системе продукций PS=<БП(БЗ), РП(БД),I> , где БП – база правил РП – рабочая память (база данных) I - интерпретатор, реализующий стратегии поиска. Продукционный цикл 1 этап. Сопоставление и множества продукций из P. Получаем конфликтное множество CS= ; CS - множество тех правил, левые части которых сопоставимы с . 2 этап. Разрешение конфликтов. Выбирается процедура(стратегия) разрешения конфликта. В результате получаем AS=; AS - активное множество. 3 этап. Выполнение правил из AS. В результате получаем множество . Если , то STOP. Иначе – goto 1.( ) Реализация выбора правил Детерминированный выбор Параллельное выполнение Недетерминированный выбор Детерминированный выбор Нужно применить одно из правил того множества, из которого выбираются правила. Могут быть использованы: 1. НАМ (нормальные алгоритмы Маркова). 2. Приоритет (частного перед общим). 3. Рейтинги. Условия корректности детерминированного выбора 1). Условие коммутативности 2). Недетерминированный выбор Возможны два случая: - мягкий недетерминизм (потом, на каком-то этапе узнаем, какой был сделан выбор) - жесткий приоритет (не узнаем, что было выбрано) Условия корректности недетерминированного выбора 1). Условие коммутативности 2). Условие идемпотентности 3). Условие ассоциативности 4). Условие дистрибутивности 5). Параллельное выполнение Условия корректности параллельного выполнения 1). Условие коммутативности 2). Условие ассоциативности 3). Условие дистрибутивности 4). Условие останова 5). (6). Условие идемпотентности Эффект интерференции Это означает, что результат параллельного выполнения правил Пример Правила , где {0,0} и {1,1} – не ожидаемые состояния - если в универсум входит подструктура , то она заменяется на Зависимости и : 1). По входу: 2). По выходу: 3). По входу / выходу: В каких случаях параллельное выполнение будет корректно или возможно? Есть P={} 1). Матрица параллелизма Q=|| || = = 2). После нахождения активного множества AS= для каждого правила определяем || множество. Поиск решений в пространстве целей. Цель редуцируется до тех пор, пока не получим решение тривиальной задачи. Поиск решений в пространстве целей отображается деревом целей. Существует два типа вершин: вершина И, вершина ИЛИ. Корень дерева – главная цель. Вершина типа И: чтобьы решить задачу, надо решить все её подзадачи. Вершина типа ИЛИ: чтобьы решить задачу, надо решить одну из её подзадач. Вершина разрешима, если существует путь, связывающий целевую вершину с подзадачами. Решающий подграф – это подграф исходного графа, показывающий, что начальная вершина разрешима. Если в дереве есть вершины типа ИЛИ, то решающий подграф может быть не единственным. Просмотр вершин от листьев к корню даёт план решения задачи. В пример это могут быть: Z3 Z4 Z5 Z1 Z2 Или Z3 Z4 Z6 Одним из универсальных методов редукции является метод уменьшения различий. (Generel Problem Solver. Nowell, Show, Simon). В этом методе редукция ведётся по принципу отщепления от главной задачи элементарных подзадач. Sн => Sк Три шага: 1. Задача: преобразовать sнSн в sкSк, уменьшить различие. Если D(sн,Sн)=0, то задача решениа. 2. Найти преобразование piP, устраняющее D(sн,Sн). Если sнSpi, то останов. 3. Применить pi. pi Выводы: 1) Может существовать неединственный оператор, устраняющий различия. 2) Ветвь может оказаться тупиковой. Если различия можно упорядочить по важности, то строится следующая матрица. В первую очередь применяются операторы, устраняющие главное различие. Эффективность данного метода низкая. Пример: Обезьяна и банан. s = (w, x, y ,z) О – обезьяна, Б – банан, Я – ящик. Система координат одномерная. w – координата О. y – координата ящика. x = 1, если О на Я 0, иначе. z = 1, если О схватила Б 0, иначе. sн = (a, 0, b, 0) sк = (c, 1, c, 1) Операторы (преобразования): P1(v) подойти в точку v. P1(v) = ((x, 0, y, z) (v, 0, y, z) P2(t) передвинуть ящик в точку t. P2(t) = ((x, 0, x, z) (t, 0, t, z)) P3 взобраться на ящик. P3 = ((x, 0, x, z) (x, 1, x, z)) P4 схватить банан. P4 = ((c, 1, c, 0) (c, 1, c, 1)) Главное различие z1 p4 Различия: D(a, 0, b, 0) Sp4 1) Я не в точке сP2(c) 2) О не в точке сP1(c) 3) О не на Я P3 P2(c) P1(c) P3 Различия: D(c, 0, c, 0) Sp4 О не на Я P3 P1(b) Элементарная подзадача P3 Обход снизу даёт решение: P1(b), P2(c), P3, P4. Проблема взаимодействия подцелей. Пример: Мир роботов и кубиков. X = {A, B, C, …} – множество кубоиков. H = {1, 2, …} - множество рук. CL(x) - кубик х свободен (на него можно ставить). ON(x,y) - кубик х стоит на у. ONT(x) - кубик х на столе. HE(k)ё - к-тая рука робота свободна. HL(x, k) - в к-той руке робота находится кубик. Продукция имеет вид: Левая часть = условие применимости продукции, Правая часть = список дополнения (истинные предикаты) и список исключения (ложные предикаты). P1(x, k) - взять кубик х со стола. P1(x, k) = (ONT(x)&CL(x)&HE(k)) HL(x,k)& ONT(x)&CL(x)&HE(k) P2(x, k) - поставить кубик х на стол рукой к. P2(x, k) = (HL(x, k)) ONT(x)&CL(x)&HE(x)& HE(x, k) P3(x, y, k) - поставить кубик х на кубик у к-той рукой. P3(x, y, k) = (HL(x, y, k)&CL(y)) ONT(x, y)&CL(x)&HE(k)& HL(x, k)& CL(y) P4(x, y, k) - снять кубик х с кубика у к-той рукой. P4(x, y, k) = (HE(k)&ON(x, y)&CL(x)) CL(y)&HE(x, k)& HE(k)& CL(x)& ON(x, y) Последовательная реализация целей. (однорукий робот). SнSк Sк = (ONT(B), ON(C, B), ON(A, C), CL(A), HE) ONT(B) ON(C,B) ON(A, C) CL(A) HE + + + + + + - + (X=A) + + + + - + (X=A) + • ON(C, B): P4(C, A), P3(C, B) ON(A, C): P1(A), P3(A, C) Решение: P4(C, A), P3(C, B), P1(A), P3(A, C) Параллельная реализация подцелей. (двурукий робот) 1. Независимые подцели. n одноруких роботов. 2. Зависимые подцели. SнSк + + + + + (X=C) + (X=C) P4(C, A, 2) t1 P2(C, 2) t3 P1(A, 2) t4 P3(A, C, 2) Рука 2 t P4(C, A, 1) t1 P3(C, B, 1) t2 Рука 1 t Согласование подцелей. 1. Супервизор. (Следит за процессом и строит реальный план.) P1(A, 2) t3 P3(A, C, 2) t4 Рука 2 t P4(C, A, 1) t1 P3(C, B, 1) t2 Рука 1 t Итоговое решение: P4(C, A, 1), P3(C, B, 1) || P1(A, 2), P3(A, C, 2) Последовательное выполнение: t = t4 + t3 + t1 + t2 Параллельное выполнение: t = t4 + max(t3, t1) + t2 2. Частично упорядоченные подцели. ON(C, B), ON(A, C) Таблица решений: