Otimize a multiplicação da cadeia da matriz

Esse desafio é calcular a ordem de multiplicação mais eficiente para um produto de várias matrizes.

O tamanho das matrizes é especificado em uma única linha de entrada padrão. Você deve imprimir na saída padrão uma lista de números inteiros indicando a ordem na qual as multiplicações devem ser realizadas para minimizar o custo total da multiplicação.

Exemplo 1

entrada

5x6 6x12 12x100 100x7

resultado

3 2 1

A linha de entrada será uma lista separada por espaços de tamanhos de matriz, cada um com o número de linhas, seguido por um x, seguido pelo número de colunas. Por exemplo, existem 4 matrizes para multiplicar juntas (portanto, 3 multiplicações totais) e, como a multiplicação de matrizes é associativa, elas podem ser feitas em qualquer ordem.

A saída deve ser a ordem na qual executar as multiplicações para minimizar o custo total. Essa deve ser uma lista de números inteiros separados por espaço, representando o índice da multiplicação a ser executado em seguida. Para matrizes N, essa lista deve conter os números 1 a N-1, inclusive. Por exemplo 1, a saída 3 2 1significa que você deve fazer a 12x100 * 100x7multiplicação primeiro, depois a 6x12 * 12x7multiplicação (a segunda matriz vezes o resultado da etapa anterior) e, finalmente, a 5x6 * 6x7multiplicação resultante .

As multiplicações da matriz sempre serão compatíveis, ou seja, o número de colunas de uma matriz corresponderá ao número de linhas da matriz subsequente. Suponha que o custo de multiplicar duas matrizes AxB * BxCseja A*B*C.

Seu código deve manipular listas de até 100 matrizes, cada uma das dimensões até 999 e fazê-lo em um tempo razoável.

exemplo 2

entrada

5x10 10x5 5x15 15x5

resultado

1 3 2

ou

3 1 2

exemplo 3

entrada

22x11 11x78 78x123 123x666 666x35 35x97 97x111 111x20 20x50

resultado

2 3 4 5 6 7 8 1

Nota: para verificação, o melhor custo total para os três exemplos é 9114, 750 e 1466344.

O código mais curto vence!

Ruby, 176 172 205 caracteres

Aqui está outra versão (vários caracteres a mais) que também será executada para grandes entradas em tempo razoável.

q=(gets.split<<$_[/\d+$/]).map &:to_i
r=Hash.new{|h,i|h[i]=Hash.new{|h,j|h[j]=1e12;h[j]=i==j ?[0,[]]:(i...j).map{|k|a,c=r[i][k];b,d=r[k+1][j];[a+b+q[i-1]*q[k]*q[j],c+d+[k]]}.min}}
$><<r[1][q.size-1][1]*' '

Primeira versão: implementação recursiva direta em Ruby. Ele faz uma pesquisa completa e, portanto, pode ser lento em entradas grandes.

k=->m{m[2]?(1..m.size-2).map{|l|s=k[m[0,l]+m[l+1..-1]];[m[l-1]*m[l]*m[l+1]+s[0],[l]+s[1].map{|u|u<l ?u:u+1}]}.min: [0,[]]}
$><<k[(gets.split<<$_[/\d+$/]).map &:to_i][1]*' '