Участник:Zerika

Седловой элемент матрицы [math]\displaystyle{ A = (a_{i, j})_{i = 1, j = 1}^{m, n} }[/math] — элемент матрицы [math]\displaystyle{ a_{k, d} }[/math], удовлетворяющий условиям [math]\displaystyle{ a_{k, d} = \max_{1 \le i \le m} a_{i, d} = \min_{1 \le j \le n} a_{k, j} }[/math], то есть элемент матрицы, который одновременно является минимальным элементом в соответствующей строке матрицы и максимальным элементом в соответствующем столбце матрицы. Из определения следует, что [math]\displaystyle{ a_{k, d} = \max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j} }[/math]. Более того, для матрицы существует седловой элемент тогда и только тогда, когда [math]\displaystyle{ \max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j} }[/math]. Примеры
Матрица

[math]\displaystyle{ \begin{bmatrix} 5 & 6 & 4 & 5\\ -2 & 5 & 3 & 7\\ 8 & 7 & -2 & 6\\ \end{bmatrix} }[/math]

имеет 1 седловой элемент, равный 4, который расположен в первой строке в третьем столбце матрицы, так как он одновременно является минимальным элементом в соответствующей строке матрицы (в данном случае в первой строке матрицы) и максимальным элементом в соответствующем столбце матрицы (в данном случае в третьем столбце матрицы).

Матрица

[math]\displaystyle{ \begin{bmatrix} 2 & 3 & 5 & 2\\ 2 & 4 & 6 & 2\\ -2 & 7 & 2 & 0\\ \end{bmatrix} }[/math]

имеет 4 седловых элемента, равных 2, которые расположены в первой строке в первом столбце, в первой строке в четвёртом столбце, во второй строке в первом столбце, во второй строке в четвёртом столбце матрицы, соответственно.

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

Свойства и структура алгоритма

Общее описание алгоритма

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

Математическое описание

Пусть задана матрица A размерности m x n (m строк, n столбцов).

Элемент A_ij является седловой точкой, если выполняются два условия:

Он является минимальным элементом в своей строке i:

A_ij = min A_ik, k от 1 до n

Он является максимальным элементом в своем столбце j:

A_ij = max A_dj, d от 1 до m

Алгоритм можно описать как поиск таких индексов (i, j), для которых:

∀k: A_ij ≤ A_ik и ∀d: A_ij ≥ A_dj

Вычислительное ядро алгоритма

Вычислительное ядро алгоритма состоит из двух последовательных этапов:

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

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

Макроструктура алгоритма

Алгоритм состоит из двух последовательных макроопераций:

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

1. Проверка найденных кандидатов на максимальность в их столбцах. Эта операция представляет собой цикл по всем строкам-кандидатам, внутри которого для каждого кандидата выполняется полный проход по его столбцу.

Последовательная сложность алгоритма

Поиск минимумов в строках: Требуется просмотреть каждый элемент матрицы ровно один раз. Сложность = O(m * n).

Проверка кандидатов: В худшем случае (когда все минимумы строк находятся в разных столбцах) требуется для каждой из m строк проверить m элементов в столбце. Сложность = O(m * m) = O(m^2).

Общая последовательная сложность: O(m * n) + O(m^2). В худшем случае, когда матрица квадратная (m = n), сложность составляет O(n^2) + O(n^2) = O(n^2)