Участник:Zerika: различия между версиями

Версия от 20:02, 9 декабря 2025

Седловой элемент матрицы [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 соответствующего столбца с кандидатом, и при обнаружении большего элемента проверка прекращается.

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

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

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

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

Схема реализации последовательного алгоритма

Для каждой строки i:

Найти индекс позиции j минимального элемента строки.
Проверить, является ли A_i,j максимальным в столбце j.
Если да — вернуть (i,j) как седловую точку.
Если ни для одной строки условие не выполнено — сообщить об отсутствии седловой точки.

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

Для матрицы размером m×n
Поиск минимума в строке занимает — O(n)
Проверка максимума в столбце — O(m)
Итого на каждую строку — O(m+n)
Общая сложность — O(m(m+n)), что при квадратной матрице n = m равно O(n^2)

Информационный граф

Информационный граф отражает две основные операции над каждой строкой: поиск минимума и проверку максимума в столбце. Между итерациями отсутствуют зависимости, параллелизм возможен по строкам.

Граф относительно прост и состоит из двух последовательных уровней вычислений для каждой строки.

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

Уровень 2 (Проверка кандидатов): m вершин (по одной на каждого кандидата). Каждая вершина i на этом уровне использует результат вершины i с первого уровня (столбец-кандидат) и требует данные всего столбца d из исходной матрицы для проверки на максимум. Вершины этого уровня также независимы друг от друга.

Связь между уровнями: Результат работы вершины i Уровня 1 (значение d) является входным данным для вершины i Уровня 2.

Ресурс параллелизма алгоритма

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

При наличии m процессоров поиск минимумов во всех строках можно выполнить за O(n) времени (время обработки одной строки).
Проверку всех кандидатов на наличие максимума в столбцах, при наличии m процессоров, можно выполнить за O(m) времени (время прохода по одному столбцу). Таким образом, общая параллельная сложность составляет O(n + m).
Параллелизм реализуется на уровне итераций по строкам — независимые проверки каждой строки и связанных с ними операций.

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

Входные и выходные данные алгоритма

Входные данные: Прямоугольная числовая матрица A размером m x n. Тип элементов - целый или вещественный. Особых свойств от матрицы не требуется.

Выходные данные: Координаты найденных седловых точек (i, j) или индикатор ее отсутствия (например, None).

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

В матрице может быть несколько седловых точек или ни одной
Алгоритм устойчив к дублирующимся значениям

Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

def find_all_saddle_points_optimized(matrix):

   if not matrix or not matrix[0]:
       return []
   
   m = len(matrix)  # количество строк
   n = len(matrix[0])  # количество столбцов
   
   saddle_points = []
   
   for i in range(m):
       # Шаг 1: Находим все индексы минимальных элементов в строке i
       min_in_row = matrix[i][0]
       min_indices = [0]
       
       for j in range(1, n):
           if matrix[i][j] < min_in_row:
               min_in_row = matrix[i][j]
               min_indices = [j]
           elif matrix[i][j] == min_in_row:
               min_indices.append(j)
       
       # Шаг 2: Для каждого минимального элемента проверяем,
       # является ли он максимальным в своем столбце
       for j in min_indices:
           is_saddle = True
           for k in range(m):
               if matrix[k][j] > matrix[i][j]:
                   is_saddle = False
                   break
           
           if is_saddle:
               saddle_points.append({
                   'row': i,
                   'col': j,
                   'value': matrix[i][j]
               })
   
   return saddle_points

2.2 Возможные способы и особенности параллельной реализации алгоритма

   def find_all_saddle_points_parallel(matrix):
   if not matrix or not matrix[0]:
       return []
   
   m = len(matrix)
   n = len(matrix[0])
   
   def process_row(i):
       """
       Обработка одной строки для поиска ВСЕХ потенциальных седловых точек
       """
       row_results = []
       
       # Находим все минимальные элементы в строке
       min_in_row = matrix[i][0]
       min_indices = [0]
       
       for j in range(1, n):
           if matrix[i][j] < min_in_row:
               min_in_row = matrix[i][j]
               min_indices = [j]
           elif matrix[i][j] == min_in_row:
               min_indices.append(j)
       
       # Для каждого минимального элемента проверяем условие
       for j in min_indices:
           is_saddle = True
           for k in range(m):
               if matrix[k][j] > matrix[i][j]:
                   is_saddle = False
                   break
           
           if is_saddle:
               row_results.append((i, j, matrix[i][j]))
       
       return row_results
   
   # Параллельная обработка строк
   saddle_points = []
   with concurrent.futures.ThreadPoolExecutor(max_workers=min(m, 4)) as executor:
       futures = [executor.submit(process_row, i) for i in range(m)]
       
       # Собираем все результаты
       for future in concurrent.futures.as_completed(futures):
           row_results = future.result()
           for result in row_results:
               saddle_points.append({
                   'row': result[0],
                   'col': result[1],
                   'value': result[2]
               })
   
   return saddle_points