Как найти седловую точку в матрице

Как найти седловую точку в матрице

БлогNot. C++: как найти все седловые точки в матрице

C++: как найти все седловые точки в матрице

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

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

Сначала листинг с «элементарно-переборным» подходом.

Функция int saddle (int n,int m,int **a,int is,int js) проверяет, является ли элемент a[is][js] матрицы a размерностью n*m её седловой точкой. Вернёт 1 (да) или 0 (нет).

Функция int *saddle_points (int n, int m, int **a, int &k) находит все седловые точки матрицы. Использует первую функцию. Возвращает количество седловых точек через параметр-ссылку k , а основная возвращаемая величина — вектор размерностью 2*k , содержащий координаты строк и столбцов всех седловых точек матрицы. Например если в матрице 2 седловых точки, находящихся в позициях (0,1) и (3,2) , вектор будет состоять из чисел (0,1,3,2) (нумерация с нуля).

В main интересен также способ переписать вектор из (n*m) элементов построчно в матрицу размерности n*m :

Это нужно для того, что мне захотелось передавать в функции параметр типа int **a , а при подстановке фактического параметра-адреса матрицы во многих компиляторах я рисковал бы получить ошибку вроде

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

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

Рассмотрим более «культурный» алгоритм поиска всех седловых точек матрицы. Покажем его работу на примере.

Требуется найти все её седловые точки.

Соберём наименьшие значения по всем строкам, получим вектор A=(-4, 2, 2, -3) .

Соберём наибольшие значения по всем столбцам, получим вектор B=(7, 2, 7, 2) .

Проверка: максимум первого набора никогда не может быть больше минимума второго.

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

Если максимум первого набора равен минимуму второго (в нашем случае число 2), мы нашли значение S седловой точки.

Теперь посмотрим, на каких позициях в векторах A и B находятся значения S .

При нумерации с единицы, в первом наборе это позиции 2 и 3, а во втором — позиции 2 и 4.

На произведении этих множеств располагаются все седловые точки. В нашем случае <2, 3>* <2, 4>= < <2, 2>, <3, 2>, <2, 4>, <3, 4>> — координаты в матрице всех седловых точек, опять же, при нумерации с единицы.

4. Седловая точка матричной игры

Во всех рассмотренных примерах выполнено неравенство: α ≤ β. Легко убедиться, что это неравенство выполняется в любой матричной игре, т.е. нижняя цена матричной игры всегда не превосходит ее верхней цены.

Рассмотрим случай, когда максимин α равен минимаксу β. Обозначим их общее значение ν, т.е.

Число ν называется ценой игры. В этом случае максиминная стратегия игрока 1 и минимаксная стратегия игрока 2 образуют так называемую седловую точку.

Пусть А — платежная матрица размерности mxn. Элемент называется седловой точкой матрицы А, если для всех выполнены следующие неравенства:

то есть элемент одновременно является наименьшим в своей строке и наибольшим в своем столбце . Справедлива следующая теорема.

Теорема 2.1. Матрица А = (а_ij) имеет седловую точку тогда и только тогда, когда нижняя цена игры равна ее верхней цене, т.е. α = β.

Игра, в которой максимин α равен минимаксу β, называется игрой с седловой точкой. Если матрица имеет несколько седловых точек, то все они имеют одинаковые значения.

Нахождение седловой точки платежной матрицы

Чтобы проверить, имеет матрица седловую точку или нет, нужно найти в каждой строке минимум ее элементов и определить значение максимального из них – максимин. Затем следует найти в каждом столбце максимум его элементов и определить значение минимального из них – минимакс. Если максимин равен минимаксу, то матрица имеет, по крайней мере, одну седловую точку. Любая седловая точка находится на пересечении строки, минимум в которой равен максимину, и столбца, максимум в котором равен минимаксу.

В примере 2.1 платежная матрица имеет одну седловую точку: элемент а₂₂ (см. таблицу 2.1). В примере 2.2 платежная матрица имеет две седловые точки: это элементы а₂₂ и а₃₂, равные 26. Отметим, что хотя элемент а₃₄ также равен 26, он не является седловой точкой, так как максимум в третьем столбце равен 27, т.е. больше чем а₃₄ (см. таблицу 2.2). В примере 2.3 максимин не равен минимаксу, поэтому платежная матрица не имеет седловой точки (см. таблицу 2.3).

5. Оптимальные стратегии, их устойчивость

Пусть платежная матрица А имеет седловую точку . Тогда стратегия игрока 1 является его чистой максиминной стратегией, а стратегия игрока 2 — его чистой минимаксной стратегией.

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

Действительно, предположим, что игрок 1 выбрал другую чистую стратегию А_i — i-ю строку матрицы А, а игрок 2 придерживается прежней стратегии . Тогда значение выигрыша игрока 1 равно . Так как — седловая точка, то . Следовательно, выбрав другую стратегию, игрок 1 не сможет улучшить свой результат. Он может только потерять часть выигрыша, который ему гарантирован, если он придерживается своей оптимальной стратегии .

Аналогичными рассуждениями легко показать, что и игроку 2 нет смысла изменять свою стратегию, поскольку, если его противник будет придерживаться своей оптимальной стратегии , то в этом случае он может лишь ухудшить свой результат. В том случае, когда игрок 1 (игрок 2) имеет несколько чистых максиминных (минимаксных) стратегий, он может выбирать любую из них без изменения величины выигрыша.

Таким образом, если игра имеет седловую точку, то оптимальной стратегией игрока 1 является его чистая максиминная стратегия, а оптимальной стратегией игрока 2 — его чистая минимаксная стратегия. Выбрав эту стратегию, игрок 1 (игрок 2) обеспечивает себе максимальный выигрыш (минимальный проигрыш) независимо от действий противника, равный значению игры.

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

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

В примере 2.2 есть два решения. Их образуют пары оптимальных стратегий (А₂, В₃) и (А₃, В₃). Следовательно, фирма должна выпускать второй или третий вариант модели. В этом случае ее гарантированная прибыль составит 26 млн. руб. независимо от уровня покупательского спроса. Если же фирма выберет первый вариант модели, то при некоторых уровнях спроса она может получить меньшую прибыль. Поэтому выбор этого варианта связан с определенным риском.

В примере 2.3 (игра в орлянку) решения в чистых стратегиях нет, поэтому пока никаких рекомендаций дать нельзя.

Итак, если игра имеет седловую точку, то оптимальной стратегией игрока 1 будет любая чистая максиминная стратегия, а оптимальной стратегией игрока 2 — любая чистая минимаксная стратегия. Выбрав эту стратегию, игрок 1 (игрок 2) гарантирует себе максимальный выигрыш (минимальный проигрыш), равный цене игры, независимо от действий своего противника. Оптимальные стратегии игроков образуют ситуацию устойчивого равновесия: ни одному из них невыгодно отклоняться от своей стратегии.

Замечание. Все вышесказанное справедливо как для игры, состоящей из одной партии, так и для игры, состоящей из нескольких партий. В последнем случае игрок 1 (игрок 2), выбирая в каждой партии свою оптимальную стратегию, гарантирует себе независимо от поведения противника максимальный средний выигрыш (минимальный средний проигрыш), равный цене игры.

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

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

06. Принцип максимина в антагонистических играх. Седловая точка

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

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

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

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

При этом для выбора оптимальной стратегии используют Принцип максимина: Выбирай ту стратегию, чтобы при наихудшем для нас поведении противника получить максимальный выигрыш. Другими словами, принцип максимина предполагает выбор той стратегии, при которой наш минимальный выигрыш для различных стратегий максимален. Отсюда и название «принцип максимина».

Как видно, принцип максимина — это принцип крайне осторожного игрока, но именно он является основным принципом теории матричных игр.

Для пояснения принципа максимина рассмотрим пример 1 матричной игры G (4х5) с платежной матрицей, приведенной на рис. 2.2.

Какой стратегией игроку А воспользоваться? Есть соблазнительный выигрыш 12, при применении стратегии А3. Но при этом противник может выбрать стратегию В3, и игрок А получит выигрыш, равный всего трем.

Для определения оптимальной стратегии в соответствии с принципом максимина, запишем в правом добавочном столбце платежной матрицы минимальное значение AI в каждой строке (минимум строки). Из всех значений AI (правый столбец) выделим наибольшее. Ему соответствует стратегия А4. Выбрав эту стратегию, мы во всяком случае можем быть уверены, что при любом поведении противника выигрыш будет не менее пяти.

Эта величина — наш гарантированный выигрыш. Он называется Нижней ценой игры (или «максимином» — максимальный из минимальных выигрышей). Будем обозначать его A. В нашем примере a = Aij =5.

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

Припишем к платежной матрице (рис.2.2) нижнюю строку и в ней запишем наихудшее для игрока В возможные результаты (максимумы столбцов BJ.

Очевидно, осторожный противник должен выбрать стратегию, при которой величина BJ минимальна. Эта величина называется Верхней ценой игры (или “минимаксом” — минимальный из максимальных проигрышей). Будем обозначать ее B. В нашем примере b = Aij = 7.

Итак, исходя из принципа осторожности, игрок А должен выбрать стратегию А4, а его противник — В3. Такие стратегии называются максиминными или минимаксными стратегиями (вытекающие из принципа максимина).

До тех пор, пока обе стороны в нашем примере будут придерживаться своих максиминных стратегий, выигрыш игрока А и проигрыш игрока В будет равен А43=5.

Легко показать, что нижняя цена игры никогда не превосходит верхней цены игры.

Лемма 1. Пусть задана матрица выигрышей

А = êêaijêêи определены b= и a= .

Тогда .

Доказательство. По определению максимума и минимума для любых фиксированных значений I и J имеем

(2.1)

Поскольку левая часть неравенства (2.1) не зависит от I, то можем записать

(2.2)

Так как правая часть неравенства (2.1) не зависит от J, то

(2.3)

Объединяя неравенства (2.2) и (2.3), получаем неравенство (2.1), что и требовалось доказать. Итак, всегда B³A.

Случай B=A, соответствует наличию у платежной матрицы так называемой Седловой точки.

Определение. Точка (I*, J*) называется седловой точкой платежной матрицы ||AIj||, если для всех остальных i и j этой матрицы выполняется условие

Т. е. Аij является одновременно минимумом своей строки и максимумом своего столбца.

Приведем без доказательства следующую теорему.

Теорема 1. Для того чтобы

Необходимо и достаточно, чтобы матрица ||AIj|| имела седловую точку. Кроме того, если (I*, J*) — седловая точка матрицы ||AIj||, то

(2.4)

Говорят, что матричная игра имеет седловую точку, если соответствующая ей матрица выигрышей (платежная матрица) имеет седловую точку.

Пример 2. Найти решение игры G (3х3), платежная матрица которой имеет следующий вид:

Задача седловые элементы матрицы

Дана матрица a_ij размером n × m, состоящая из целых чисел. Требуется определить количество седловых элементов матрицы. Элемент матрицы a_ij называется седловым, если он является наименьшим в i-й строке и наибольшим в j-м столбце. Иными словами, элемент матрицы является седловым, если все элементы в соответствующей строке не меньше его, и при этом все элементы в соответствующем столбце не больше его

Моя ошибка заключается в превышении максимального времени работы (ограничение задачи 2 секунды)