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 [34325 просмотров]
К этой статье пока нет комментариев, Ваш будет первым
Вариант решения с учетом возможных повторений минимумов и максимумов.
Не претендует на идеальный, памяти многовато ест. скорее всего можно оптимизировать.
Временная сложность O(MxN), Использование дополнительной памяти O(MxN)
Код на C#, но кроме двумерных массивов в данном фрагменте все идентично C++, адаптация не должна стать проблемой.
int m;//Количество столбцов
int n;//Количество строк
//читаем M и N
int[,] source = new int[m, n];//исходная матрица
int[,] finder = new int[m, n];//матрица поиска
//заполняем исходную матрицу любым способом
//заполняем матрицу поиска нулями
for (int j = 0; j < n; j++){
//ищем минимум в строке
int minInd = 0;
for (int i = 1; i < m; i++)
if (source[minInd,j]>source[i,j])
minInd = i;
//Отмечаем на матрице поиска все минимумы прибавляя 1
for (int i = 0; i < m; i++)
if (source[minInd, j] == source[i, j])
finder[i, j]++;
}
//Повторяем все то же для максимумов столбцов
for (int i = 0; i < m; i++){
int maxInd = 0;
for (int j = 1; j < n; j++)
if (source[i, maxInd] < source[i, j])
maxInd = j;
for (int j = 0; j < n; j++)
if (source[i, maxInd] == source[i, j])
finder[i, j]++;
}
int result = 0;
for (int j = 0; j < n; j++)
for (int i = 1; i < m; i++)
if (finder[i, j] == 2)//если минимум строки и максимум столбца
result++; //совпали, ячейка матрицы поиска будет равна 2
//из result забираем количество найденных седловых элементов
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <time.h> #include <stdio.h> #include <stdlib.h> enum {N=4, M=5}; void printf_arr (int [][M], int, int); void random_arr (int [][M], int, int); int max_in_col (int [][M], int, int, int); int min_in_row (int [][M], int, int, int); void saddle_point (int [][M], int, int); int main (void) { int a[N][M] = { { 2, 12, 6, 45, 77}, { 2, 3, 1, 79, 105}, { 2, 44, 3, 32, 21}, { 0, 83, 0, 19, -6} }; int b[N][M] = { {0} }; random_arr(b, N, M); puts("массив a:"); printf_arr(a, N, M); saddle_point(a, N, M); puts("nмассив b:"); printf_arr(b, N, M); saddle_point(b, N, M); return 0; } // ------------------------------------------------------------- void printf_arr (int a[][M], int rows, int columns) { for (int i=0; i<rows; i++, puts("")) for (int k=0; k<columns; k++) printf("% 4d", a[i][k]); puts(""); } // ------------------------------------------------------------- void random_arr (int a[][M], int rows, int columns) { srand( (unsigned int)time(NULL)/2 ); for (int i=0; i<rows; i++) for (int k=0; k<columns; k++) a[i][k] = rand() %101 - 50; } // ------------------------------------------------------------- int max_in_col (int a[][M], int rows, int columns, int column) { int max = 0; for (int i=1; i<rows; i++) if (a[i][column] > a[max][column]) max = i; return max; // возвращает строку } // ------------------------------------------------------------- int min_in_row (int a[][M], int rows, int columns, int row) { int max = 0; for (int k=1; k<columns; k++) if (a[row][k] < a[row][max]) max = k; return max; // возвращает столбец } // ------------------------------------------------------------- void saddle_point (int a[][M], int rows, int columns) { int i, k, min[N], max[M]; for (i=0; i<rows; i++) min[i] = a[i][min_in_row(a, rows, columns, i)]; for (k=0; k<columns; k++) max[k] = a[max_in_col(a, rows, columns, k)][k]; int found = 0; for (i=0; i<rows; i++) for (k=0; k<columns; k++) if (a[i][k] == min[i] && a[i][k] == max[k]) { printf("%4d", a[i][k]); found++; } if (found < 1) puts("В массиве нет седловых точек!"); else printf("nВыявлено %d седловые точки.n", found); } // ------------------------------------------------------------- |
Рассмотрим
игру m
× n с
матрицей P
= (aij ),
i = 1, 2, …, m; j = 1, 2, …, n и
определим наилучшую среди стратегий A1, A2,
…, Am.
Выбирая стратегию Ai игрок А должен
рассчитывать, что игрок В ответит
на нее той из стратегий Bj ,
для которой выигрыш для игрока А минимален
(игрок В стремится
«навредить» игроку А).
Обозначим через αi ,
наименьший выигрыш игрока А при
выборе им стратегии Ai для
всех возможных стратегий игрока В (наименьшее
число в i-й
строке платежной матрицы), т.е.
Среди
всех чисел αi (i
= 1, 2, …, m) выберем
наибольшее: . Назовем α нижней
ценой игры,
или максимальным
выигрышем (максимином).
Это гарантированный выигрыш игрока А при
любой стратегии игрока В.
Следовательно,
13. Седловая точка.
Седловая
точка — это наибольший элемент
столбца матрицы
игры,
который одновременно является наименьшим
элементом соответствующей строки
(в игре
двух лиц с нулевой суммой).
В этой точке, следовательно, максимин
одного игрока равен минимаксу другого;
С. т. есть точка равновесия.
Понятие
седловой точки
Если
в игре с матрицей А нижнее и
верхнее, чистые цены игры совпадают
т.е. 
,
то говорят, что эта игра имеет седловую
точку, в чистых выражениях и чистую
цену игры:
Седловая
точка — это пара чистых стратегий
(i0, j0)
первого и второго игрока, при котором
достигается равенство 
.
В
понятии седловой точки вложен следующий
смысл:
если
один из игроков придерживается стратегии,
соответствующей седловой точки, то
другой игрок не может поступить лучше,
чем придерживаться стратегии,
соответствующей седловой точки.
—отклонение
первого игрока от седловой точки может
приводить только к уменьшению его
выигрыша.
—отклонение
второго игрока от седловой точки может
приводить к увеличению его проигрыша 
.
Седловой
элемент 
—
является минимальным элементом строки
и максимальным элементом в столбце.
Для
определения седлового элемента
необходимо последовательно в каждой
точке определить минимальный элемент,
а затем проверять является ли он
максимальным элементом столбца и если
является, тогда таким образом найдена
седловая точка — цена игры, оптимальные
стратегии первого и второго игрока:
14.
Оптимальные стратегии.
В
матричной игре каждый из игроков
выбирает свои стратегии, не имея сведений
о действиях другого игрока. Выясним,
на какие наилучшие гарантированные
выигрыши они могут рассчитывать.
Первый игрок, выбрав некоторую
стратегию i, может получить в
качестве выигрыша один из двух
элементов аi1, аi2 матрицы
А в зависимости от того, какую
стратегию применит второй игрок. В
худшем случае он должен рассчитывать
на минимальный выигрыш, т. е. на
.
В
то же время при удачном выборе
стратегии i = i* первый
игрок может получить максимальный
выигрыш из минимальных:
(5.2)
Второй
игрок рассуждает сходным образом. При
выборе стратегии j его
максимальный проигрыш из двух
возможных а1 j, а2 j
равен
.
Если
выбор стратегии j = j* оказался
удачным, то он может рассчитывать на
минимальный проигрыш из максимальных:
.
(5.3)
Формулы
(5.2), (5.3) определяют наилучшие гарантированные
выигрыши игроков. Если они совпадают,
то их общее значение можно считать
приемлемым для игроков компромиссом,
а соответствующие стратегии i*, j*
— оптимальными стратегиями.
Непосредственные
вычисления по формулам (5.2), (5.3) с
использованием (5.1) дают
Здесь
наилучшие гарантированные выигрыши
не равны и оптимальных стратегий не
существует.
Причина
отсутствия оптимальных стратегий
кроется, очевидно, в их определении.
Попробуем изменить определение
оптимальных стратегий, не упуская из
вида игрового смысла задачи и целей
игроков.
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
Задана матрица 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.