Во всех рассмотренных примерах выполнено
неравенство: α ≤ β. Легко
убедиться, что это неравенство выполняется
в любой матричной игре, т.е. нижняя
цена матричной игры всегда не превосходит
ее верхней цены.
Рассмотрим случай, когда максимин α
равен минимаксу β. Обозначим их
общее значение ν, т.е.
ν =
.
Число ν называется ценой игры.
В этом случае максиминная стратегия
игрока 1 и минимаксная стратегия игрока
2 образуют так называемую седловую
точку.
Пусть А — платежная матрица
размерности mxn.
Элемент
называется седловой точкой матрицы
А, если для всех
выполнены следующие неравенства:
, (2.3)
то есть элемент
одновременно
является наименьшим в своей строке
и наибольшим в своем столбце
.
Справедлива следующая теорема.
Теорема 2.1.
Матрица А = (аij)
имеет седловую точку тогда и только
тогда, когда нижняя цена игры равна ее
верхней цене, т.е. α = β.
Игра, в которой максимин α равен
минимаксу β, называется игрой
с седловой точкой. Если матрица имеет
несколько седловых точек, то все они
имеют одинаковые значения.
Нахождение седловой точки платежной матрицы
Чтобы проверить, имеет матрица седловую
точку или нет, нужно найти в каждой
строке минимум ее элементов и определить
значение максимального из них – максимин.
Затем следует найти в каждом столбце
максимум его элементов и определить
значение минимального из них – минимакс.
Если максимин равен минимаксу, то матрица
имеет, по крайней мере, одну седловую
точку. Любая седловая точка находится
на пересечении строки, минимум в которой
равен максимину, и столбца, максимум в
котором равен минимаксу.
В примере 2.1 платежная матрица имеет
одну седловую точку: элемент а22
(см. таблицу 2.1). В примере 2.2 платежная
матрица имеет две седловые точки: это
элементы а22 и а32,
равные 26. Отметим, что хотя элемент а34
также равен 26, он не является седловой
точкой, так как максимум в третьем
столбце равен 27, т.е. больше чем а34
(см. таблицу 2.2). В примере 2.3 максимин не
равен минимаксу, поэтому платежная
матрица не имеет седловой точки (см.
таблицу 2.3).
5. Оптимальные стратегии, их устойчивость
Пусть платежная матрица А имеет
седловую точку
.
Тогда стратегия
игрока 1 является его чистой максиминной
стратегией, а стратегия
игрока 2 — его чистой минимаксной
стратегией.
Эти стратегии являются оптимальными
стратегиями для игроков. Они обладают
важным свойством устойчивости:
ни одному из игроков невыгодно
отклоняться от своей оптимальной
стратегии, так как это может привести
лишь к ухудшению его положения.
Действительно, предположим, что игрок
1 выбрал другую чистую стратегию Аi
— i-ю строку матрицы
А, а игрок 2 придерживается прежней
стратегии
.
Тогда значение выигрыша игрока 1 равно
.
Так как
— седловая точка, то
.
Следовательно, выбрав другую стратегию,
игрок 1 не сможет улучшить свой
результат. Он может только потерять
часть выигрыша, который ему гарантирован,
если он придерживается своей оптимальной
стратегии
.
Аналогичными рассуждениями легко
показать, что и игроку 2 нет смысла
изменять свою стратегию, поскольку,
если его противник будет придерживаться
своей оптимальной стратегии
,
то в этом случае он может лишь ухудшить
свой результат. В том случае, когда игрок
1 (игрок 2) имеет несколько чистых
максиминных (минимаксных) стратегий,
он может выбирать любую из них без
изменения величины выигрыша.
Таким образом, если игра имеет седловую
точку, то оптимальной стратегией игрока
1 является его чистая максиминная
стратегия, а оптимальной стратегией
игрока 2 — его чистая минимаксная
стратегия. Выбрав эту стратегию, игрок
1 (игрок 2) обеспечивает себе максимальный
выигрыш (минимальный проигрыш) независимо
от действий противника, равный значению
игры.
Любая пара оптимальных стратегий игроков
образует решение игры, которое также
называют ситуацией равновесия или
равновесием. Рассмотрим, какое
поведение игроков в наших примерах
считает оптимальным теория игр.
В примере 2.1 существует единственное
решение, которое образует пара оптимальных
стратегий (А2, В2).
Следовательно, каждая фирма должна
продавать на рынке свой второй вид
продукции. В этом случае первая фирма
получит прибыль, равную 10 млн. руб., а
вторая фирма понесет убытки на такую
же сумму. Отклонение от этих стратегий
ни одной из фирм невыгодно, так как если
ее конкурент будет придерживаться своей
оптимальной стратегии, то она лишь
ухудшит свой результат
В примере 2.2 есть два решения. Их образуют
пары оптимальных стратегий (А2,
В3) и (А3, В3).
Следовательно, фирма должна выпускать
второй или третий вариант модели. В этом
случае ее гарантированная прибыль
составит 26 млн. руб. независимо от уровня
покупательского спроса. Если же фирма
выберет первый вариант модели, то при
некоторых уровнях спроса она может
получить меньшую прибыль. Поэтому выбор
этого варианта связан с определенным
риском.
В примере 2.3 (игра в орлянку) решения в
чистых стратегиях нет, поэтому пока
никаких рекомендаций дать нельзя.
Итак, если игра имеет седловую точку,
то оптимальной стратегией игрока 1 будет
любая чистая максиминная стратегия, а
оптимальной стратегией игрока 2 — любая
чистая минимаксная стратегия. Выбрав
эту стратегию, игрок 1 (игрок 2) гарантирует
себе максимальный выигрыш (минимальный
проигрыш), равный цене игры, независимо
от действий своего противника. Оптимальные
стратегии игроков образуют ситуацию
устойчивого равновесия: ни одному из
них невыгодно отклоняться от своей
стратегии.
Замечание.
Все вышесказанное справедливо как для
игры, состоящей из одной партии, так и
для игры, состоящей из нескольких партий.
В последнем случае игрок 1 (игрок 2),
выбирая в каждой партии свою оптимальную
стратегию, гарантирует себе независимо
от поведения противника максимальный
средний выигрыш (минимальный средний
проигрыш), равный цене игры.
Если игра не имеет седловой точки (α
< β), то максиминная и минимаксная
стратегии игроков уже не обладают
свойством устойчивого равновесия.
Каждый из игроков может попытаться
изменить ситуацию в свою пользу и
добиться выигрыша γ, где α < γ
< β. Правда, в этом случае он рискует,
так как ни одна из его чистых стратегий
не способна обеспечить ему этот результат.
Чтобы определить оптимальные стратегии
игроков в ситуации, когда игра не имеет
седловой точки, нужно ввести в рассмотрение
так называемые смешанные стратегии,
частным случаем которых являются чистые
стратегии. Такое расширение множества
стратегий позволяет найти решение любой
матричной игры.
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
Седловой элемент матрицы 
— элемент матрицы 
, удовлетворяющий условиям 
, то есть элемент матрицы, который одновременно является минимальным элементом в соответствующей строке матрицы и максимальным элементом в соответствующем столбце матрицы. Из определения следует, что 
. Более того, для матрицы существует седловой элемент тогда и только тогда, когда 
.
Аналогичным образом можно определить понятие седловая точка для любой функции от двух переменных: точка 
является седловой точкой функции 
, определённой на декартовом произведении 
, если
[1]
Примеры[править | править код]
Матрица
имеет 1 седловой элемент, равный 4, который расположен в первой строке в третьем столбце матрицы, так как он одновременно является минимальным элементом в соответствующей строке матрицы (в данном случае в первой строке матрицы) и максимальным элементом в соответствующем столбце матрицы (в данном случае в третьем столбце матрицы).
Матрица
имеет 4 седловых элемента, равных 2, которые расположены в первой строке в первом столбце, в первой строке в четвёртом столбце, во второй строке в первом столбце, во второй строке в четвёртом столбце матрицы, соответственно.
Данный пример показывает, что матрица может иметь несколько (более одной) седловых точек.
Тем не менее, если матрица имеет несколько седловых точек, то все их значения равны.
Так, в матрице, все элементы которой равны друг другу, все элементы являются седловыми точками.
Матрица
не имеет седловой точки.
Применение[править | править код]
Вышеприведенное использование термина «седловая точка» имеет особое значение в теории игр. Так, например, в играх с нулевой суммой седловая точка платёжной матрицы является равновесием Нэша.
Примечания[править | править код]
- ↑ Седловая точка (в теории игр) — статья из Математической энциклопедии. В. Л. Крепс
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:
//Если число элементов items = n*m, код корректно перепишет вектор в матрицу (по строкам) for (i=0; i<n*m; i++) a[i/m][i%m]=items[i];
Проверьте, для матрицы размерностью 8*2 должен получиться порядок
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15а для 4*4 – как у нас,
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Это нужно для того, что мне захотелось передавать в функции параметр типа int **a, а при подстановке фактического параметра-адреса матрицы
int a[n][m];
во многих компиляторах я рисковал бы получить ошибку вроде
Cannot convert 'int [4] *' to 'int * *'
Код же из листинга должен работать независимо от настроек приведения типов.
#include <stdlib.h>
#include <stdio.h>
int saddle (int n,int m,int **a,int is,int js) {
int i,j,min,max;
min=a[is][0];
for (j=0; j<m; j++) if (a[is][j]<min) min=a[is][j];
max=a[0][js];
for (i=0; i<n; i++) if (a[i][js]>max) max=a[i][js];
return (a[is][js]==min && a[is][js]==max ? 1 : 0);
}
int *saddle_points (int n, int m, int **a, int &k) {
int i,j;
k=0;
for (i=0; i<n; i++)
for (j=0; j<m; j++) {
if (saddle(n,m,a,i,j)) k++;
}
if (k==0) return NULL;
int *s = new int [k*2];
if (s==NULL) return NULL;
int l=0;
for (i=0; i<n; i++)
for (j=0; j<m; j++) {
if (saddle(n,m,a,i,j)) { s[l++]=i; s[l++]=j; }
}
return s;
}
int main () {
const int n=4,m=4;
int **a;
int items[] = {
7,-1,-4,1,
3,2,3,2,
2,2,3,2,
4,-3,7,-2
};
int i,j;
a = new int * [n];
for (i=0; i<n; i++) a[i] = new int [m];
//Если число элементов items = n*m, код корректно перепишет вектор в матрицу (по строкам)
for (i=0; i<n*m; i++) a[i/m][i%m]=items[i];
printf ("nПолучена матрица:");
for (i=0; i<n; i++) {
printf ("n");
for (j=0; j<m; j++) printf ("%d ",a[i][j]);
}
int k=0;
int *s=saddle_points (n,m,a,k);
if (k>0) {
for (i=0; i<2*k; i+=2) {
printf ("na[%d,%d]=%d",s[i],s[i+1],a[s[i]][s[i+1]]);
}
}
else printf ("nНет седловых точек или не выделена память");
printf ("nENTER");
getchar();
return 0;
}
Для поиска всех седловых точек в матрицах большой размерности не нужно рассматривать каждый элемент отдельно.
Рассмотрим более “культурный” алгоритм поиска всех седловых точек матрицы. Покажем его работу на примере.
Дана матрица:
7 -1 -4 1 4 2 3 2 2 2 3 2 4 -3 7 -2
Требуется найти все её седловые точки.
Соберём наименьшие значения по всем строкам, получим вектор 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} } – координаты в матрице всех седловых точек, опять же, при нумерации с единицы.
Одна из возможных реализаций этого алгоритма:
#pragma hdrstop
#pragma argsused
#include <tchar.h>
/* в некоторых компиляторах нужно убрать 3 верхних строчки */
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <ctime>
int main ()
{
const int strok = 4 , stolbcov = 4;
int i,j,k,z, maxofmin,minofmax;
int matr[strok][stolbcov] = {{7,-1,-4,1},{4,2,3,2},{2,2,3,2},{4,-3,7,-2}};
int max[stolbcov], min[strok];
/* srand(time(0));
for (i = 0; i < strok; i++)
for (j = 0; j < stolbcov; j++)
matr[i][j]=rand()%9+1; */
for (i = 0; i < strok; i++)
{
std::cout << "n";
for (j = 0; j < stolbcov; j++)
{
std::cout<< std::setw(3)<<matr[i][j];
}
}
std::cout << std::endl;
j = 0;
for (i = 0; i < strok; i++)
{
for (j = 0; j < stolbcov; j++)
{
min[i] = matr[i][j];
if (min[i] > matr[i][j])
min[i] = matr[i][j];
}
}
j = 0;
for (j = 0; j < stolbcov; j++)
{
i=0;
max[j] = matr[i][j];
for (i = 0; i < strok; i++)
if (max[j] < matr[i][j])
max[j] = matr[i][j];
}
maxofmin = min[0];
for (i = 0; i < strok; i++)
if (maxofmin < min[i])
maxofmin = min[i];
minofmax = max[0];
for (i = 0; i < stolbcov; i++)
if (minofmax > max[i])
minofmax = max[i];
if (minofmax > maxofmin)
std::cout << "Sedlovix tochek net" << std::endl;
else
std::cout << "Sedlovie tochki = " <<std::endl;
for (i = 0; i < strok; i++)
if (min[i] == maxofmin)
for (j = 0; j < stolbcov; j++)
if (max[j] == minofmax)
std::cout << i << " " << j << std::endl;
system("pause");
return 0;
}
15.11.2013, 17:48 [34319 просмотров]
К этой статье пока нет комментариев, Ваш будет первым
Задана матрица K, содержащая n строк и m столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.
Найдите количество седловых точек заданной матрицы.
Входные данные
Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 750). Далее следуют n строк по m чисел в каждой. j-ое число i-ой строки равно kij. Все kij по модулю не превосходят 1000.
Выходные данные
Выведите ответ на задачу.
В чем ошибка?
type s = array[1..750,1..750] of integer;
type s2 = array[1..750] of integer;
var mas: s;
var masN,masX: s2;
var n,m,i,j,k: integer;
begin
k:=0;
readln(n,m);
for i:=1 to n do
for j:=1 to m do
read(mas[i,j]);
masN[1]:=mas[1,1];
for i:=1 to n do
begin
for j:=1 to m do
if mas[i,j]<masN[i] then
masN[i]:=mas[i,j];
masN[i+1]:=mas[i+1,1];
end;
masX[1]:=mas[1,1];
for j:=1 to m do
begin
for i:=1 to n do
if mas[i,j]>masX[j] then
masX[j]:=mas[i,j];
masX[j+1]:=mas[1,j+1];
end;
for i:=1 to n do
for j:=1 to m do
if (mas[i,j]=masN[i]) and (mas[i,j]=masX[j]) then
k:=k+1;
write(k);
end.Given a matrix of n x n size, the task is to find the saddle point of the matrix. A saddle point is an element of the matrix such that it is the minimum element in its row and the maximum in its column.
Examples :
Input: Mat[3][3] = { {1, 2, 3},
{4, 5, 6},
{7, 8, 9}}
Output: 7
7 is minimum in its row and maximum in its column.
Input: Mat[3][3] = {{1, 2, 3},
{4, 5, 6},
{10, 18, 4}}
Output: No saddle point
A simple solution is to traverse all matrix elements one by one and check if the element is Saddle Point or not.
An efficient solution is based on the below steps.
Traverse all rows one by one and do the following for every row i.
- Find the minimum element of the current row and store the column index of the minimum element.
- Check if the row minimum element is also maximum in its column. We use the stored column index here.
- If yes, then saddle point else continues till the end of the matrix.
Below is the implementation of the above steps.
C++
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
bool findSaddlePoint(int mat[MAX][MAX], int n)
{
for (int i = 0; i < n; i++)
{
int min_row = mat[i][0], col_ind = 0;
for (int j = 1; j < n; j++)
{
if (min_row > mat[i][j])
{
min_row = mat[i][j];
col_ind = j;
}
}
int k;
for (k = 0; k < n; k++)
if (min_row < mat[k][col_ind])
break;
if (k == n)
{
cout << "Value of Saddle Point " << min_row;
return true;
}
}
return false;
}
int main()
{
int mat[MAX][MAX] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
int n = 3;
if (findSaddlePoint(mat, n) == false)
cout << "No Saddle Point ";
return 0;
}
C
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
bool findSaddlePoint(int mat[MAX][MAX], int n)
{
for (int i = 0; i < n; i++)
{
int min_row = mat[i][0], col_ind = 0;
for (int j = 1; j < n; j++)
{
if (min_row > mat[i][j])
{
min_row = mat[i][j];
col_ind = j;
}
}
int k;
for (k = 0; k < n; k++)
if (min_row < mat[k][col_ind])
break;
if (k == n)
{
printf("Value of Saddle Point %d",min_row);
return true;
}
}
return false;
}
int main()
{
int mat[MAX][MAX] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
int n = 3;
if (findSaddlePoint(mat, n) == false)
printf("No Saddle Point ");
return 0;
}
Java
class Test
{
static boolean findSaddlePoint(int mat[][ ], int n)
{
for (int i = 0; i < n; i++)
{
int min_row = mat[i][0], col_ind = 0;
for (int j = 1; j < n; j++)
{
if (min_row > mat[i][j])
{
min_row = mat[i][j];
col_ind = j;
}
}
int k;
for (k = 0; k < n; k++)
if (min_row < mat[k][col_ind])
break;
if (k == n)
{
System.out.println("Value of Saddle Point " + min_row);
return true;
}
}
return false;
}
public static void main(String[] args)
{
int mat[][] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
int n = 3;
if (findSaddlePoint(mat, n) == false)
System.out.println("No Saddle Point ");
}
}
Python3
def findSaddlePoint(mat, n):
for i in range(n):
min_row = mat[i][0];
col_ind = 0;
for j in range(1, n):
if (min_row > mat[i][j]):
min_row = mat[i][j];
col_ind = j;
k = 0;
for k in range(n):
if (min_row < mat[k][col_ind]):
break;
k += 1;
if (k == n):
print("Value of Saddle Point ",
min_row);
return True;
return False;
if __name__ == '__main__':
mat = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]];
n = 3;
if (findSaddlePoint(mat, n) ==
False):
print("No Saddle Po");
C#
using System;
class GFG {
static bool findSaddlePoint(int [,] mat,
int n)
{
for (int i = 0; i < n; i++)
{
int min_row = mat[i, 0], col_ind = 0;
for (int j = 1; j < n; j++)
{
if (min_row > mat[i, j])
{
min_row = mat[i, j];
col_ind = j;
}
}
int k;
for (k = 0; k < n; k++)
if (min_row < mat[k, col_ind])
break;
if (k == n)
{
Console.WriteLine("Value of Saddle Point "
+ min_row);
return true;
}
}
return false;
}
public static void Main()
{
int [,] mat = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
int n = 3;
if (findSaddlePoint(mat, n) == false)
Console.WriteLine("No Saddle Point ");
}
}
PHP
<?php
$MAX = 100;
function findSaddlePoint( $mat, $n)
{
for ( $i = 0; $i < $n; $i++)
{
$min_row = $mat[$i][0];
$col_ind = 0;
for ( $j = 1; $j < $n; $j++)
{
if ($min_row > $mat[$i][$j])
{
$min_row = $mat[$i][$j];
$col_ind = $j;
}
}
$k;
for ($k = 0; $k < $n; $k++)
if ($min_row < $mat[$k][$col_ind])
break;
if ($k == $n)
{
echo "Value of Saddle Point " ,
$min_row;
return true;
}
}
return false;
}
$mat = array(array(1, 2, 3),
array(4, 5, 6),
array (7, 8, 9));
$n = 3;
if (findSaddlePoint($mat, $n) == false)
echo "No Saddle Point ";
?>
Javascript
<script>
function findSaddlePoint(mat, n)
{
for (let i = 0; i < n; i++)
{
let min_row = mat[i][0], col_ind = 0;
for (let j = 1; j < n; j++)
{
if (min_row > mat[i][j])
{
min_row = mat[i][j];
col_ind = j;
}
}
let k;
for (k = 0; k < n; k++)
if (min_row < mat[k][col_ind])
break;
if (k == n)
{
document.write("Value of Saddle Point " + min_row+"<br>");
return true;
}
}
return false;
}
let mat = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]];
let n = 3;
if (findSaddlePoint(mat, n) == false)
document.write("No Saddle Point ");
</script>
Output
Value of Saddle Point 7
Time Complexity: O(n*n)
Auxiliary Space: O(1)
Exercise :
Can there be more than one Saddle Points in a Matrix?
This article is contributed by Sahil Chhabra(KILLER). If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Last Updated :
02 Aug, 2022
Like Article
Save Article
