Введение в теорию игр. Жариков И.А - 44 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

44
Если некоторая вершина такого графа имеет непосредственно
следующие за ней (дочерние) вершины, то либо все они являются
И-вершинами, либо все они – ИЛИ-вершины. Заметим, что если у не-
которой вершины И/ИЛИ-графа имеется ровно одна дочерняя верши-
на, то ее можно считать как И-вершиной, так и ИЛИ-вершиной − как,
например, вершину F на рис. 9, б.
На языке И/ИЛИ-графов применение некоторого оператора
редукции задачи означает, что сначала строится промежуточная
И-вершина, а затем непосредственно следующие за ней ИЛИ-вершины
подзадач. Исключение составляет случай, когда множество задач со-
стоит только из одного элемента; в этом случае образовывается ровно
одна вершина и будем для определенности считать ее ИЛИ-вершиной.
Вершину И/ИЛИ-графа, соответствующую описанию исходной
задачи, назовем начальной вершиной. Вершины же, которые соответ-
ствуют описаниям элементарных задач, назовем заключительными
вершинами. Поиск, осуществляемый путем перебора вершин графа,
применим и в подходе, основанном на редукции задач. Цель поиска на
И/ИЛИ-графе – показать, что разрешима исходная задача, т.е. началь-
ная вершина. Разрешимость этой вершины зависит от разрешимости
других вершин графа.
Сформулируем общее рекурсивное определение разрешимости
вершины в И/ИЛИ-графе:
− заключительные вершины разрешимы, так как они соответст-
вуют элементарным задачам;
− вершина, не являющаяся заключительной и имеющая дочер-
ние И-вершины, разрешима тогда и только тогда, когда разрешима по
крайней мере одна из ее дочерних вершин;
− вершина, не являющаяся заключительной и имеющая дочер-
ние ИЛИ-вершины, разрешима тогда и только тогда, когда разрешима
каждая из ее дочерних вершин.
Если в процессе поиска удалось показать, что начальная вершина
разрешима, то это значит, что обнаружено решение исходной задачи,
которое заключено в так называемом решающем графе. Решающий
граф – это подграф И/ИЛИ-графа, состоящий только из разрешимых
вершин и доказывающий разрешимость начальной вершины.
Пример. Задача символьного интегрирования.
В качестве примера применения метода редукции рассмотрим
решение задачи символьного интегрирования, т.е. нахождения неопре-
деленного интеграла
∫
dxxF )(
. Обычно эта задача решается путем
последовательного преобразования интеграла к выражению, содержа-
щему известные табличные интегралы. Для этого используется

Страницы