Zoptymalizuj mnożenie łańcucha macierzy

Wyzwanie polega na obliczeniu najbardziej wydajnego rzędu mnożenia dla iloczynu kilku macierzy.

Rozmiar macierzy jest określony w jednym wierszu standardowego wejścia. Powinieneś wydrukować na standardowe wyjście listę liczb całkowitych wskazującą kolejność wykonywania mnożenia, aby zminimalizować całkowity koszt pomnożenia.

Przykład 1

Wejście

5x6 6x12 12x100 100x7

wynik

3 2 1

Wiersz wejściowy będzie oddzieloną spacjami listą rozmiarów macierzy, z których każdy jest liczbą wierszy, po której xnastępuje, a następnie liczba kolumn. Na przykład istnieją 4 macierze do pomnożenia razem (czyli 3 mnożenia całkowite), a ponieważ mnożenie macierzy jest asocjacyjne, można je wykonać w dowolnej kolejności.

Dane wyjściowe powinny być w kolejności wykonywania mnożenia, aby zminimalizować całkowity koszt. Powinna to być rozdzielona spacjami lista liczb całkowitych reprezentujących indeks mnożenia do wykonania w następnej kolejności. W przypadku macierzy N lista ta powinna zawierać liczby od 1 do N-1 włącznie. Na przykład 1, wynik 3 2 1oznacza, że ​​powinieneś najpierw wykonać 12x100 * 100x7pomnożenie, następnie 6x12 * 12x7pomnożenie (druga macierz razy wynik z poprzedniego kroku), a na końcu wynikowe 5x6 * 6x7pomnożenie.

Mnożenie macierzy zawsze będzie kompatybilne, tzn. Liczba kolumn macierzy będzie zgodna z liczbą wierszy kolejnej macierzy. Załóżmy, że koszt pomnożenia dwóch macierzy AxB * BxCwynosi A*B*C.

Twój kod musi obsługiwać listy do 100 macierzy, każda o wymiarze do 999, i robić to w rozsądnym czasie.

przykład 2

Wejście

5x10 10x5 5x15 15x5

wynik

1 3 2

lub

3 1 2

przykład 3

Wejście

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

wynik

2 3 4 5 6 7 8 1

Uwaga: do weryfikacji najlepszy całkowity koszt dla trzech przykładów to 9114, 750 i 1466344.

Najkrótszy kod wygrywa!

Ruby, 176 172 205 znaków

Oto kolejna wersja (kilka znaków dłuższa), która również będzie działać w przypadku dużych nakładów w rozsądnym czasie.

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]*' '

Pierwsza wersja: prosta rekurencyjna implementacja w Ruby. Wykonuje pełne wyszukiwanie, a zatem może być powolne przy dużych wejściach.

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]*' '