racy.
Method :ref:`'2opt' <optimize.qap-2opt>` can be computationally expensive,
but may be a useful alternative, or it can be used to refine the solution
returned by another method.

References
----------
.. [1] J.T. Vogelstein, J.M. Conroy, V. Lyzinski, L.J. Podrazik,
       S.G. Kratzer, E.T. Harley, D.E. Fishkind, R.J. Vogelstein, and
       C.E. Priebe, "Fast approximate quadratic programming for graph
       matching," PLOS one, vol. 10, no. 4, p. e0121002, 2015,
       :doi:`10.1371/journal.pone.0121002`

.. [2] D. Fishkind, S. Adali, H. Patsolic, L. Meng, D. Singh, V. Lyzinski,
       C. Priebe, "Seeded graph matching", Pattern Recognit. 87 (2019):
       203-215, :doi:`10.1016/j.patcog.2018.09.014`

.. [3] "2-opt," Wikipedia.
       https://en.wikipedia.org/wiki/2-opt

Examples
--------
>>> import numpy as np
>>> from scipy.optimize import quadratic_assignment
>>> rng = np.random.default_rng()
>>> A = np.array([[0, 80, 150, 170], [80, 0, 130, 100],
...               [150, 130, 0, 120], [170, 100, 120, 0]])
>>> B = np.array([[0, 5, 2, 7], [0, 0, 3, 8],
...               [0, 0, 0, 3], [0, 0, 0, 0]])
>>> res = quadratic_assignment(A, B, options={'rng': rng})
>>> print(res)
     fun: 3260
 col_ind: [0 3 2 1]
     nit: 9

The see the relationship between the returned ``col_ind`` and ``fun``,
use ``col_ind`` to form the best permutation matrix found, then evaluate
the objective function :math:`f(P) = trace(A^T P B P^T )`.

>>> perm = res['col_ind']
>>> P = np.eye(len(A), dtype=int)[perm]
>>> fun = np.trace(A.T @ P @ B @ P.T)
>>> print(fun)
3260

Alternatively, to avoid constructing the permutation matrix explicitly,
directly permute the rows and columns of the distance matrix.

>>> fun = np.trace(A.T @ B[perm][:, perm])
>>> print(fun)
3260

Although not guaranteed in general, ``quadratic_assignment`` happens to
have found the globally optimal solution.

>>> from itertools import permutations
>>> perm_opt, fun_opt = None, np.inf
>>> for perm in permutations([0, 1, 2, 3]):
...     perm = np.array(perm)
...     fun = np.trace(A.T @ B[perm][:, perm])
...     if fun < fun_opt:
...         fun_opt, perm_opt = fun, perm
>>> print(np.array_equal(perm_opt, res['col_ind']))
True

Here is an example for which the default method,
:ref:`'faq' <optimize.qap-faq>`, does not find the global optimum.

>>> A = np.array([[0, 5, 8, 6], [5, 0, 5, 1],
...               [8, 5, 0, 2], [6, 1, 2, 0]])
>>> B = np.array([[0, 1, 8, 4], [1, 0, 5, 2],
...               [8, 5, 0, 5], [4, 2, 5, 0]])
>>> res = quadratic_assignment(A, B, options={'rng': rng})
>>> print(res)
     fun: 178
 col_ind: [1 0 3 2]
     nit: 13

If accuracy is important, consider using  :ref:`'2opt' <optimize.qap-2opt>`
to refine the solution.

>>> guess = np.array([np.arange(len(A)), res.col_ind]).T
>>> res = quadratic_assignment(A, B, method="2opt",
...     options = {'rng': rng, 'partial_guess': guess})
>>> print(res)
     fun: 176
 col_ind: [1 2 3 0]
     nit: 17

N)