Материал: Учебное пособие Немирко Манило

b

Рис. 2.20

Выравнивание слова T2 строится по той же траектории. Отличия заключаются лишь в том, что движение по верхней горизонтали клетки (i, j) означает вставку символа, стоящего в T1 на i -м месте, а движение по левой вертикали – удаление j -го символа в T2 .

Как видно из табл. 2.6, длина слов T1 и T2 , полученных в результате трансформации цепочек символов T1 и T2 , стала одинаковой (l = 9 ), причем пустые символы стоят в них в разных позициях.

Процедура временного выравнивания и величина W (T1, T2 ), оцениваю-

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

торая описывает некоторый класс сигналов, величина W (T1, T2 ) отождествляется с расстоянием от анализируемой цепочки T1 до этого эталона. При

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

66

3. ПРИМЕНЕНИЕ ТЕОРИИ ИГР ДЛЯ ОПТИМИЗАЦИИ КЛИНИЧЕСКИХ РЕШЕНИЙ В ХИРУРГИИ

3.1. Игры и методы их решения

Рассмотрим игру (модель конфликтной ситуации), в которой участвуют два игрока A и B , имеющие прямо противоположные интересы, поэтому выигрыш одного равен проигрышу другого. Такая игра называется парной игрой с нулевой суммой. Если игрок A выигрывает a , то игрок B при этом выигрывает −a , поэтому сумма выигрышей всегда равна нулю. Процесс игры заключается в последовательных ходах (личных – сознательных и случайных) противников, а совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от сложившейся ситуации называется стратегией игрока [6]. При конечном числе стратегий игра

ходящую стратегию. Для данного игрока среди всех стратегий имеется оптимальная, обеспечивающая ему максимальный выигрыш. Задача теории игр – нахождение оптимальных стратегий игроков в предположении одинаковой «разумности» противников.

По матрице игры определяются нижняя α и верхняя β цены игры. Пусть

67

Принцип выбора противниками стратегий, соответствующих получению ими выигрышей α и β называется принципом минимакса, а сами стратегии – минимаксными. Известно [7], что минимаксные стратегии устойчивы по отношению к информации о поведении другой стороны только в случае, если α =β. Тогда матрица игры имеет седловую точку, а величина γ = α =β называется ценой игры. Стратегии Ai и B j , при которых достигается выигрыш γ,

называются оптимальными чистыми стратегиями, а их совокупность – решением игры.

Более часто α ≠β, и тогда для получения наибольшего выигрыша игроку выгодно не применять одну (чистую) стратегию, а чередовать случайным образом несколько стратегий. Такие стратегии, состоящие в случайном чередовании чистых стратегий, называются смешанными и задаются соответ-

игроком A стратегии Ai , q j – вероятность применения игроком B стратегии B j , причем

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

(S*A, SB* ), обладающих следующим свойством: если один из игроков при-

держивается своей оптимальной стратегии, то другому не может быть вы годно отступить от своей [6]. Выигрыш, соответствующий решению, называется, как и раньше, ценой игры и в общем случае (при применении смешанной стратегии) лежит в интервале α ≤ γ ≤β. Самая простая конечная игра – игра 2 ×2 . Ее матрица имеет вид табл. 3.2.

68

стратегий, а любая точка внутри этого отрезка соответствует некоторой смешанной стратегии S*A = (p1, p2 ). В этом случае ординаты прямой B1B1 , про-

веденной так, как показано на рис 3.1, соответствуют выигрышу игрока A при применении им любой стратегии (чистой или смешанной) с условием, что B применяет B1. Прямая B2B2 также отражает выигрыш игрока A

в случае, когда B применяет B2 . Жирной линией отмечена нижняя граница выигрыша B1NB2 (минимальный выигрыш игрока A при любой его смешан-

ной стратегии). Очевидно, решение достигается в точке максимума нижней границы (N на рис. 3.1). Геометрические построения легко осуществляются по элементам матрицы игры, которые откладываются на вертикальных осях. По рисунку легко находятся α, β, γ и проводится анализ игры.

Геометрическим способом также легко анализируются и решаются игры 2 ×n . Они задаются матрицей игры, представленной в табл. 3.3, а на рис. 3.2 представлена геометрическая интерпретация этой игры для случая n = 4 .

69