Седловая точка матрицы это

Блог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 :

Проверьте, для матрицы размерностью 8*2 должен получиться порядок а для 4*4 – как у нас,

Это нужно для того, что мне захотелось передавать в функции параметр типа 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>> – координаты в матрице всех седловых точек, опять же, при нумерации с единицы.

Читайте также:  Проблема с учетной записью майкрософт виндовс 10

Одна из возможных реализаций этого алгоритма (не проверено)

15.11.2013, 17:48; рейтинг: 26145

Матричные игры

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

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

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

2 Платёжная матрица, чистые стратегии, цена игры

В матричной игре её правила определяет платёжная матрица.

Рассмотрим игру, в которой имеются два участника: первый игрок и второй игрок. Пусть в распоряжении первого игрока имеется m чистых стратегий, а в распоряжении второго игрока – n чистых стратегий. Поскольку рассматривается игра, естественно, что в этой игре есть выигрыши и есть проигрыши.

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

Составим платёжную матрицу:

.

Если первый игрок выбирает i-ю чистую стратегию, а второй игрок – j-ю чистую стратегию, то выигрыш первого игрока составит aij единиц, а проигрыш второго игрока – также aij единиц.

Так как aij + (- aij) = 0, то описанная игра является матричной игрой с нулевой суммой.

Простейшим примером матричной игры может служить бросание монеты. Правила игры следующие. Первый и второй игроки бросают монету и в результате выпадает "орёл" или "решка". Если одновременно выпали "орёл" и "орёл" или "решка" или "решка", то первый игрок выиграет одну единицу, а в других случаях он же проиграет одну единицу (второй игрок выиграет одну единицу). Такие же две стратегии и в распоряжении второго игрока. Соответствующая платёжная матрица будет следующей:

.

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

3 Как происходит выбор стратегии в матричной игре?

Вновь посмотрим на платёжную матрицу:

.

Сначала определим величину выигрыша первого игрока, если он использует i-ю чистую стратегию. Если первый игрок использует i-ю чистую стратегию, то логично предположить, что второй игрок будет использовать такую чистую стратегию, благодаря которой выигрыш первого игрока был бы минимальным. В свою очередь первый игрок будет использовать такую чистую стратегию, которая бы обеспечила ему максимальный выигрыш. Исходя из этих условий выигрыш первого игрока, который обозначим как v1, называется максиминным выигрышем или нижней ценой игры.

При решении задач на цену игры и определение стратегии для этих величин у первого игрока следует поступать следующим образом. Из каждой строки выписать значение минимального элемента и уже из них выбрать максимальный. Таким образом, выигрыш первого игрока будет максимальным из минимальных. Отсюда и название – максиминный выигрыш. Номер строки этого элемента и будет номером чистой стратегии, которую выбирает первый игрок.

Читайте также:  Скайп для общения с девушками

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

При решении задач на цену игры и определение стратегии для определения этих величин у второго игрока следует поступать следующим образом. Из каждого столбца выписать значение максимального элемента и уже из них выбрать минимальный. Таким образом, проигрыш второго игрока будет минимальным из максимальных. Отсюда и название – минимаксный выигрыш. Номер столбца этого элемента и будет номером чистой стратегии, которую выбирает второй игрок. Если второй игрок использует "минимакс", то независимо от выбора стратегии первым игроком, он проиграет не более v2 единиц.

Пример 1. Дана матричная игра с платёжной матрицей

.

Определить максиминную стратегию первого игрока, минимаксную стратегию второго игрока, нижнюю и верхнюю цену игры.

Решение. Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы – наибольшие элементы в столбцах и выберем минимальный из них:

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

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

Итак, гарантированный выигрыш первого игрока: .

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

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

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

.

Пример 2. Дана матричная игра с платёжной матрицей

.

Определить максиминную стратегию первого игрока, минимаксную стратегию второго игрока, нижнюю и верхнюю цену игры.

Решение. Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы – наибольшие элементы в столбцах и выберем минимальный из них:

Читайте также:  Ремонт в связном отзывы

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

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

Если верхняя и нижняя цена игры одинаковая, то считается, что матричная игра имеет седловую точку. Верно и обратное утверждение: если матричная игра имеет седловую точку, то верхняя и нижняя цены матричной игры одинаковы. Соответствующий элемент одновременно является наименьшим в строке и наибольшим в столбце и равен цене игры.

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

В этом случае матричная игра имеет решение в чистых стратегиях.

Пример 3. Дана матричная игра с платёжной матрицей

.

Найти нижнюю и верхнюю цену игры. Имеет ли данная матричная игра седловую точку?

Решение. Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы – наибольшие элементы в столбцах и выберем минимальный из них:

Нижняя цена игры совпадает с верхней ценой игры. Таким образом, цена игры равна 5. То есть . Цена игры равна значению седловой точки . Максиминная стратегия первого игрока – вторая чистая стратегия, а минимаксная стратегия второго игрока – третья чистая стратегия. Данная матричная игра имеет решение в чистых стратегиях.

| следующая лекция ==>
Критерий Ходжа-Лемана | Матричные игры с оптимальной смешанной стратегией

Дата добавления: 2019-04-03 ; просмотров: 510 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

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

Примеры :

Рекомендуется: Пожалуйста, сначала попробуйте подход , прежде чем переходить к решению.

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

Эффективное решение основано на следующих шагах.
Пройдите по всем строкам одну за другой и сделайте следующее для каждой строки i.

  1. Найдите минимальный элемент текущей строки и сохраните индекс столбца минимального элемента.
  2. Проверьте, является ли минимальный элемент строки максимальным в своем столбце. Мы используем хранимый индекс столбца здесь.
  3. Если да, то седловая точка еще продолжается до конца матрицы.

Ниже приведена реализация вышеуказанных шагов.

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>