Обнаружение, когда возможно умножение матриц

Question

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

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

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

Answer 1

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

2. Для каждой матрицы размера (m, n) соедините узлы m и n с направленным ребром (между двумя узлами может быть несколько ребер).

3. Теперь при нахождении следа элариана будет получен порядок умножения.

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

Answer 2

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

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