rilevare quando moltiplicazione matriciale è possibile

Ecco un problema interessante che ho incontrato in un concorso di programmazione:rilevare quando moltiplicazione matriciale è possibile

dichiarazione Problema: date le dimensioni del n matrici, determinare se esiste un ordine tale che le matrici possono essere moltiplicata. Se ne esiste uno, stampare le dimensioni (prodotto delle dimensioni) della matrice risultante.

mie osservazioni: Ciò riduce al problema NP-completo percorso hamiltoniano se si considera ciascuna matrice come un vertice e disegnare un bordo diretto tra matrici che possono essere moltiplicati. Ho risolto questo problema semplicemente forzando il problema, ma questo è chiaramente molto lento. Mi stavo chiedendo se ci sono ottimizzazioni intelligenti per questa particolare istanza del problema.

fonte

2012-02-13 tskuzzy

Tutti i problemi risolvibili (e verificabili) in modo efficiente riducono a problemi NP-completi. È la riduzione da un problema NP-completo al tuo problema che dovrebbe infastidire. – aelguindy

Come ha detto @ElKamina, è un problema di Eulerian Trail, vedi anche la mia risposta [qui] (http://stackoverflow.com/a/9046177/1011995). –

Creare un nodo per ogni lunghezza di quota. Cioè, se c'è una matrice di dimensione (m, n), allora m e n saranno vertici nel grafico.
Per ogni matrice di dimensione (m, n) connettere i nodi m e n con un bordo diretto (possono esserci più spigoli tra due nodi).
Ora la ricerca di una traccia euliana darebbe l'ordine di moltiplicazione.

Vedere http://en.wikipedia.org/wiki/Euler_path per trovare sentieri Eularian. La complessità è abbastanza vicino alla lineare (O (nlog^3n loglogn) dove n è il numero di fronti = numero di matrici).

fonte

2012-02-13 22:18:48 ElKamina

+1 bravo! Vorrei averlo inventato io stesso. – Gangnus

Creare una matrice di compatibilità (chiamiamola CM) come CM [x, y] = 1 se la matrice x può essere multidata di y, 0 se non lo è. se Determinante (CM) <> 0 c'è un ordine.

È solo un'intuizione, mi scuso se ho torto (sfortunatamente non sono riuscito a trovare una prova solida).

fonte

2012-02-13 22:39:01 loscuropresagio

Sicuramente falso. Si consideri il caso di due matrici 2x2. Quindi la tua matrice è [[1,1] [1,1]], che ha un determinante di 0. –

Questo è vero, ma questo significa anche che tu consideri che una matrice può essere moltiplicata da sola. Nel caso di una matrice quadrata, è assolutamente vero, ma in questo particolare scenario stiamo cercando una sequenza di matrici moltiplicate l'una dall'altra, il che significa che dovremmo considerare una matrice non compatibile con se stessa. Questo ovviamente non è una prova che ho ragione, solo una considerazione. Grazie per il commento, se trovi un altro controesempio, lo apprezzerò. – loscuropresagio

Buon punto. Che ne dici di una matrice 1x2 e 2x3. Quindi penso che la tua matrice sia [[0,1] [0,0]], che ha anche un determinante di 0, anche se puoi moltiplicare questi elementi insieme. –

rilevare quando moltiplicazione matriciale è possibile

risposta

Problemi correlati