обнаруживая при умножении матриц можно

Вот интересная проблема, что я столкнулся в программировании конкуренции:обнаруживая при умножении матриц можно

Постановка задачи: Учитывая размеров n матриц, определить, существует порядок, что матрицы могут быть умноженный. Если он существует, распечатайте размер (произведение размеров) результирующей матрицы.

Мои наблюдения: Это сводится к NP-полной гамильтоновой траектории, если вы рассматриваете каждую матрицу как вершину и рисуете направленное ребро между матрицами, которые можно умножить. Я решил это просто грубо заставляя проблему, но это явно очень медленно. Мне было интересно, есть ли какая-нибудь умная оптимизация для этого конкретного экземпляра проблемы.

источник

2012-02-13 tskuzzy

Все эффективно разрешаемые (и проверяемые) проблемы сводятся к NP-полным проблемам. Это сокращение от NP-полной проблемы к вашей проблеме, которая должна раздражать. – aelguindy

Как @ElKamina сказал, это проблема Эйлера, см. Также мой ответ [здесь] (http://stackoverflow.com/a/9046177/1011995). –

Создайте узел для каждой длины измерения. То есть, если есть матрица размерности (m, n), то m и n будут вершинами в графе.
Для каждой матрицы размера (m, n) соединяйте узлы m и n с направленным ребром (между двумя узлами могут быть несколько ребер).
Теперь нахождение эулярной тропы даст порядок умножения.

См. http://en.wikipedia.org/wiki/Euler_path для поиска Eularian trails. Сложность довольно близка к линейной (O (nlog^3n loglogn), где n - количество ребер = число матриц).

источник

2012-02-13 22:18:48 ElKamina

+1 bravo! Хотелось бы, чтобы я сам это придумал. – Gangnus

Создайте матрицу совместимости (назовем ее CM), такой как CM [x, y] = 1, если матрица x может быть мультиплексирована с помощью y, 0, если нет. если определитель (CM) <> 0 есть заказ.

Это просто интуиция, я прошу прощения, если я ошибаюсь (к сожалению, я не смог найти убедительное доказательство).

источник

2012-02-13 22:39:01 loscuropresagio

Определенно неверно. Рассмотрим случай двух матриц 2x2. Тогда ваша матрица [[1,1] [1,1]], которая имеет детерминант 0. –

Это правда, но это также означает, что вы считаете, что матрица может быть умножена сама по себе. В случае квадратной матрицы это абсолютно верно, но в этом конкретном сценарии мы ищем последовательность матриц, умноженных друг на друга, что означает, что мы должны рассматривать матрицу, несовместимую с самим собой. Это, очевидно, не является доказательством того, что я прав, просто соображения. Спасибо, хотя для комментария, если вы найдете другой контрпример, я буду признателен. – loscuropresagio

Хорошая точка. Как насчет матрицы 1x2 и 2x3. Тогда я думаю, что ваша матрица [[0,1] [0,0]], которая также имеет детерминант 0, даже если вы можете умножить эти элементы вместе. –

обнаруживая при умножении матриц можно

ответ

Смежные вопросы