detectar cuándo la multiplicación de matrices es posible

Aquí es un problema interesante que me encontré en un concurso de programación:detectar cuándo la multiplicación de matrices es posible

Planteamiento del problema: Dadas las dimensiones de n matrices, determinar si existe un orden tal que las matrices pueden ser multiplicado. Si existe uno, imprima el tamaño (producto de las dimensiones) de la matriz resultante.

Mis observaciones: Esto reduce al problema de la ruta hamiltoniana NP-completa si considera cada matriz como un vértice y dibuja un borde dirigido entre las matrices que se pueden multiplicar. Resolví esto simplemente forzando el problema, pero esto es claramente muy lento. Me preguntaba si hay optimizaciones inteligentes para esta instancia particular del problema.

Fuente

2012-02-13 tskuzzy

Todos los problemas solucionables de manera eficiente (y comprobables) se reducen a problemas de NP-complete. Es la reducción de un problema NP-completo a su problema lo que debería ser molesto. – aelguindy

Como dijo @ElKamina, es un problema de sendero de Euler, vea también mi respuesta [aquí] (http://stackoverflow.com/a/9046177/1011995). –

Cree un nodo para cada longitud de cota. Es decir, si hay una matriz de dimensión (m, n), entonces myn serán vértices en el gráfico.
Para cada matriz de tamaño (m, n) conecta los nodos myn con un borde dirigido (puede haber múltiples bordes entre dos nodos).
Ahora encontrar un sendero eularian daría la orden de multiplicación.

Ver http://en.wikipedia.org/wiki/Euler_path para encontrar rastros Eularian. La complejidad es bastante similar a la lineal (O (nlog^3n loglogn) donde n es el número de aristas = número de matrices).

Fuente

2012-02-13 22:18:48 ElKamina

+1 bravo! Me gustaría inventarlo yo mismo. – Gangnus

Cree una matriz de compatibilidad (llamémosla CM) como CM [x, y] = 1 si la matriz x puede ser multiplicada por y, 0 de lo contrario. si es determinante (CM) <> 0 hay un pedido.

Es solo una intuición, me disculpo si me equivoco (desafortunadamente no pude encontrar una prueba sólida).

Fuente

2012-02-13 22:39:01 loscuropresagio

Definitivamente falso. Considere el caso de dos matrices de 2x2. Entonces su matriz es [[1,1] [1,1]], que tiene un determinante de 0. –

Eso es cierto, pero esto también significa que usted considera que una matriz se puede multiplicar por sí misma. En el caso de una matriz cuadrada, eso es absolutamente cierto, pero en este escenario particular buscamos una secuencia de matrices multiplicadas entre sí, lo que significa que debemos considerar una matriz no compatible consigo misma. Obviamente, esto no es una prueba de que estoy en lo cierto, solo una consideración. Aunque gracias por el comentario, si encuentras otro contraejemplo, lo agradeceré. – loscuropresagio

Buen punto. ¿Qué tal una matriz de 1x2 y 2x3? Entonces creo que su matriz es [[0,1] [0,0]], que también tiene un determinante de 0, aunque puede multiplicar estos elementos juntos. –

detectar cuándo la multiplicación de matrices es posible

Respuesta

Cuestiones relacionadas