Encontre a permutação de um vetor que minimiza o padrão do produto do vetor da matriz

Você pode escrever uma implementação de força bruta muito mais rápida .

Em primeiro lugar, você pode usar uma multiplicação de matriz em vez de muitos produtos escalares trabalhando em blocos de permutações. O kernel de multiplicação de matrizes é altamente otimizado e, portanto, é executado muito mais rápido do que muitos produtos escalares.

Além disso, você pode pré-calcular parcialmente as permutações para acelerar o cálculo ainda mais, dividindo as permutações em duas partes. A ideia é primeiro construir um índice que contenha toda a permutação que consiste em escolher 5 elementos entre os 12. Em seguida, a ideia é encontrar toda a permutação de um array de 7 itens (os índices e não os próprios valores). Finalmente, todas as permutações podem ser construídas a partir dos dois índices.

Observe que otimizações adicionais são possíveis quando as duas otimizações acima são aplicadas juntas: pode-se calcular a multiplicação da matriz de forma mais eficiente se uma parte da permutação for constante .

O algoritmo resultante é complexo, mas muito mais eficiente do que o original. Aqui está o código:

def computeOptim(A):
    mini = 1000000

    permValues = np.array([2433, 2057, 1935, 1927, 1870, 1841, 1818, 1770, 1680, 1497, 1435, 1289])

    # Precompute partial permutations: high and low part of all the permutations.
    loPerms = np.array(list(itertools.permutations(range(7))))
    hiPerms = np.array(list(itertools.permutations(range(12), 5)))

    # Iterate over chunks (of 7!=5040 permutations)
    for hiPerm in hiPerms:
        # Find the remaining index to include in the low-part permutations
        loPermIndices = np.array(list(set(range(12))-set(hiPerm)))

        # Find all the possible low-part permutations for the current 
        # high-part permutation by reindexing the values.
        curLoPerms = loPermIndices[loPerms]

        # Compute the chunks of possible x values
        loPermValues = permValues[curLoPerms]
        hiPermValues = permValues[hiPerm]

        # A matrix multiplcation is used to compute many dot product in a row.
        # Compute effciently  B = A @ X  with  X the matrix containing all the permutations
        hiB = A[:,:len(hiPermValues)] @ hiPermValues[None,:].T
        loB = A[:,len(hiPermValues):] @ loPermValues.T
        B = hiB + loB

        multiCur = np.std(B, axis=0)
        minPos = np.argmin(multiCur)

        if multiCur[0,minPos] < mini:
            mini = multiCur[0,minPos]
            res = np.concatenate((hiPermValues, loPermValues[minPos]))

A = np.matrix('0,3,1,2,2,2,2,2,2,1,2,2;3,0,3,1,2,3,1,1,2,2,1,2;1,3,0,2,2,2,2,2,2,1,2,2;2,1,2,0,2,1,2,2,2,2,3,2;2,2,2,2,0,2,1,2,2,3,2,1;2,3,2,1,2,0,3,2,1,2,1,2;2,1,2,2,1,3,0,2,1,1,3,3;2,1,2,2,2,2,2,0,3,2,2,1;2,2,2,2,2,1,1,3,0,3,1,2;1,2,1,2,3,2,1,2,3,0,2,2;2,1,2,3,2,1,3,2,1,2,0,2;2,2,2,2,1,2,3,1,2,2,2,0')
computeOptim(A)

Consegui encontrar a solução ideal em 50 segundos na minha máquina, enquanto o código original levaria cerca de 5h30. Como resultado, esse código é cerca de 400 mais rápido .

A solução ideal encontrada é:

mini = 291.80729942892106
res = [2433 1841 1289 1818 2057 1927 1770 1870 1497 1680 1935 1435]