Проблем с реда на умножение на матрица

Проблемът за реда на умножение на матрицие класически проблем за динамично програмиране, в който последователност от матрици A 1 , A 2 , … , A n ,A_,\dots ,A_> и се изисква да се минимизира броят на скаларните операции за изчисляване на техния продукт. Приема се, че матриците са съвместими по отношение на умножението на матрица (тоест броят на колоните A i − 1>gt; е същият като броя на редовете A i>gt; на матрицата).

Съдържание

Матричният продукт е асоциативна операция, която приема като вход две матрициk×mиm×nи връща матрица с размерk×n, изразходвайкиkmnоперации за умножение [1] .

Нека анализираме 2 начина за решаване на проблема, за да покажем колко полезно е динамичното програмиране в този случай.

Изброяване на всички опции за поставяне на скоби

Намаляване на задача до подзадачи

Рекурсивно решение

Динамично програмиране

Ще съхраняваме резултатите от изчисленията за подзадачи в двумерен масив m, за да избегнем преизчисляване за вече изчислени подзадачи. След изчисленията отговорът ще бъде в m[1,n](Колко умножения са необходими за поредица от матрици от 1 до n - т.е. отговорът на проблема). Сложността на алгоритъма ще бъде O ( n 3 ) \right)> , тъй като имаме ( n 2 ) > избори i, j : 1 ≤ i ≤ j ≤ n и O ( N ) точки на разделяне за всеки избор. Подробностите ще станат ясни от изпълнението.

В основния метод - пример от началото на статията. Ако се стартира, ще изведе 7500, както се очаква.

Дадени са само методи, които директно извършват необходимите изчисления.

dataStore - клас обект, който съхранява всички данни

Функционални части на кода:

Този проблем се свежда до проблема с оптимизирането на безплатнотоенергия на РНК молекулата в биоинформатиката (тук чифт скоби в реда на РНК мономерите определя тяхното сдвояване). Такова динамично програмиране се реализира в алгоритмите на Nussinov или Zucker.

---