quadratic_assignment(method=’2opt’)

scipy.optimize.quadratic_assignment(A, B, метод='faq', опции=None)

Решить квадратичную задачу назначения (приближенно).

Эта функция решает квадратичную задачу о назначениях (QAP) и задачу сопоставления графов (GMP) с использованием алгоритма 2-opt [1].

Квадратичное назначение решает задачи следующего вида:

\[\begin{split}\min_P & \ {\ \text{trace}(A^T P B P^T)}\\ \mbox{s.t. } & {P \ \epsilon \ \mathcal{P}}\\\end{split}\]

где \(\mathcal{P}\) является множеством всех матриц перестановок, \(A\) и \(B\) являются квадратными матрицами.

Сопоставление графов пытается максимизировать той же целевой функции. Этот алгоритм можно рассматривать как поиск выравнивания узлов двух графов, которое минимизирует количество индуцированных расхождений рёбер или, в случае взвешенных графов, сумму квадратов разностей весов рёбер.

Обратите внимание, что задача квадратичного назначения является NP-трудной. Результаты, приведённые здесь, являются приближениями и не гарантируют оптимальности.

Параметры:

A2-D массив, квадратный

Квадратная матрица \(A\) в целевой функции выше.

B2-D массив, квадратный

Квадратная матрица \(B\) в целевой функции выше.

методstr в {'faq', '2opt'} (по умолчанию: 'faq')

Алгоритм, используемый для решения задачи. Это специфичная для метода документация для '2opt'. ‘faq’ также доступен.

Возвращает:

resOptimizeResult

OptimizeResult содержащий следующие поля.

col_indОдномерный массив

Индексы столбцов, соответствующие наилучшей найденной перестановке узлов B.

funfloat

Целевое значение решения.

nitint

Количество итераций, выполненных во время оптимизации.

Смотрите также

Для документации по остальным параметрам см. scipy.optimize.quadratic_assignment

Опции:

——-

максимизироватьbool (по умолчанию: False)

Максимизирует целевую функцию, если True.

rng{None, int, numpy.random.Generator, опционально

Состояние генератора псевдослучайных чисел. См. quadratic_assignment подробности.

partial_match2-D массив целых чисел, опционально (по умолчанию: None)

Исправляет часть сопоставления. Также известен как "начальное значение" [2].

Каждая строка partial_match определяет пару сопряжённых узлов: узел partial_match[i, 0] of A соответствует узлу partial_match[i, 1] of B. Массив имеет форму (m, 2), где m не больше, чем количество узлов, \(n\).

Примечание

partial_match должен быть отсортирован по первому столбцу.

partial_guess2-D массив целых чисел, опционально (по умолчанию: None)

Предположение для сопоставления между двумя матрицами. В отличие от partial_match, partial_guess не фиксирует индексы; они все еще могут быть оптимизированы.

Каждая строка partial_guess определяет пару сопряжённых узлов: узел partial_guess[i, 0] of A соответствует узлу partial_guess[i, 1] of B. Массив имеет форму (m, 2), где m не больше, чем количество узлов, \(n\).

Примечание

partial_guess должен быть отсортирован по первому столбцу.

Примечания

Это жадный алгоритм, который работает аналогично сортировке пузырьком: начиная с начальной перестановки, он итеративно меняет местами пары индексов для улучшения целевой функции, пока такие улучшения возможны.

Ссылки

[1]

“2-opt,” Википедия. https://en.wikipedia.org/wiki/2-opt

[2]

D. Fishkind, S. Adali, H. Patsolic, L. Meng, D. Singh, V. Lyzinski, C. Priebe, “Seeded graph matching”, Pattern Recognit. 87 (2019): 203-215, https://doi.org/10.1016/j.patcog.2018.09.014