С++.Алгоритм рекурсивной процедуры перебора.

Пример использования brute force
Исходная задача заключается в вычислении данной цепочки (матричного произведения) за наименьшее время. Можно реализовать тривиальный последовательный алгоритм, вычисляющий искомое произведение. Поскольку матричное произведение является ассоциативной операцией, можно вычислить цепочечное произведение, произвольно выбирая пару элементов цепочки ~(A_i A_1), i=1..n-1 и заменяя её результирующей матрицей ~A^1_i \colon A^1_i = (A_i A_1). Если повторять описанную процедуру n-1 раз, то оставшаяся результирующая матрица ~A^1_k и будет ответом: ~A^1_k = (A^2_k A^2_1) = ...= A_1 A_2 A_3 ...A_n, k=1..n-1. Эта формула может быть проиллюстрирована следующим образом. Рассмотрим матричную цепочку: ~\left\langle A_1, A_2, A_3, A_4 \right\rangle. Существуют следующие 5 способов вычислить соответствующее этой цепочке произведение ~A_1 A_2 A_3 A_4:

~(A_1 (A_2 (A_3 A_4))),
~(A_1 ((A_2 A_3) A_4)),
~((A_1 A_2) (A_3 A_4)),
~((A_1 (A_2 A_3)) A_4),
~(((A_1 A_2) A_3) A_4).
Выбрав правильный порядок вычислений, можно добиться значительного ускорения вычислений. Чтобы убедиться в этом, рассмотрим простой пример цепочки из 3-х матриц. Положим, что их размеры равны соответственно 10 \times 100, 100 \times 5, 5 \times 50 . Стандартный алгоритм перемножения двух матриц размерами p \times q, q \times r требует время вычисления, пропорциональное числу pqr (число вычисляемых скалярных произведений) [3]. Следовательно, вычисляя цепочку в порядке ((A_1 A_2) A_3), получаем 10 \cdot 100 \cdot 5 = 5000 скалярных произведений для вычисления (A_1 A_2), плюс дополнительно 10 \cdot 5 \cdot 50 = 2500 скалярных произведений, чтобы вычислить второе матричное произведение. Общее число скалярных произведений: 7500. При ином выборе порядка вычислений получаем 100 \cdot 5 \cdot 50 = 25000 плюс 10\cdot 100 \cdot 50 = 50000 скалярных произведений, то есть 75000 скалярных произведений [3].

Таким образом, решение данной задачи может существенно сократить временные затраты на вычисление матричной цепочки. Это решение может быть получено полным перебором: необходимо рассмотреть все возможные последовательности вычислений и выбрать из них ту, которая при вычислении цепочки занимает наименьшее число скалярных произведений. Однако надо учитывать, что этот алгоритм сам по себе требует экспоненциальное время вычисления [2], так что для длинных матричных цепочек выигрыш от вычисления цепочки самым эффективным образом (оптимальная стратегия) может быть полностью потерян временем нахождения этой стратегии [4].