Участник:Zerika: различия между версиями
Zerika (обсуждение | вклад) Создание страницы и внесение первых правок, резервное сохранение |
Zerika (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== '''Свойства и структура алгоритма''' == | == '''Свойства и структура алгоритма''' == | ||
=== | === Общее описание алгоритма === | ||
Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной. | Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной. | ||
=== | === Математическое описание === | ||
Пусть задана матрица '''A''' размерности '''m x n''' (m строк, n столбцов). | Пусть задана матрица '''A''' размерности '''m x n''' (m строк, n столбцов). | ||
| Строка 19: | Строка 19: | ||
'''∀k: A<sub>ij</sub> ≤ A<sub>ik</sub> и ∀d: A<sub>ij</sub> ≥ A<sub>dj</sub>''' | '''∀k: A<sub>ij</sub> ≤ A<sub>ik</sub> и ∀d: A<sub>ij</sub> ≥ A<sub>dj</sub>''' | ||
=== | === Вычислительное ядро алгоритма === | ||
=== | Вычислительное ядро алгоритма состоит из двух последовательных этапов: | ||
=== | |||
=== | Поиск минимумов в строках, в котором для каждой строки i матрицы A последовательно сравниваются элементы A<sub>ij</sub> с текущим минимумом, и при нахождении меньшего значения обновляются минимальный элемент и его позиция столбец (d). | ||
=== | |||
=== | Проверка кандидатов в столбцах d, в котором для каждого найденного минимума строки последовательно сравниваются элементы A<sub>id</sub> соответствующего столбца с кандидатом, и при обнаружении большего элемента проверка прекращается. | ||
=== | === Макроструктура алгоритма === | ||
=== | Алгоритм состоит из двух последовательных макроопераций: | ||
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) | |||
=== Информационный граф === | |||
=== Ресурс параллелизма алгоритма === | |||
=== Входные и выходные данные алгоритма === | |||
=== Свойства алгоритма === | |||
== ''' Программная реализация алгоритма''' == | == ''' Программная реализация алгоритма''' == | ||
=== 2.1 Особенности реализации последовательного алгоритма === | === 2.1 Особенности реализации последовательного алгоритма === | ||
Версия от 22:37, 31 октября 2025
Свойства и структура алгоритма
Общее описание алгоритма
Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной.
Математическое описание
Пусть задана матрица A размерности m x n (m строк, n столбцов).
Элемент Aij является седловой точкой, если выполняются два условия:
Он является минимальным элементом в своей строке i:
Aij = min Aik, k от 1 до n
Он является максимальным элементом в своем столбце j:
Aij = max Adj, d от 1 до m
Алгоритм можно описать как поиск таких индексов (i, j), для которых:
∀k: Aij ≤ Aik и ∀d: Aij ≥ Adj
Вычислительное ядро алгоритма
Вычислительное ядро алгоритма состоит из двух последовательных этапов:
Поиск минимумов в строках, в котором для каждой строки i матрицы A последовательно сравниваются элементы Aij с текущим минимумом, и при нахождении меньшего значения обновляются минимальный элемент и его позиция столбец (d).
Проверка кандидатов в столбцах d, в котором для каждого найденного минимума строки последовательно сравниваются элементы Aid соответствующего столбца с кандидатом, и при обнаружении большего элемента проверка прекращается.
Макроструктура алгоритма
Алгоритм состоит из двух последовательных макроопераций:
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)