L'algoritmo di Dijkstra è una soluzione adeguata a questo problema di routing del segnale?

Question

L'algoritmo di Dijkstra è una soluzione adeguata a questo problema di routing del segnale?

#1 da (4 voti)
#2 da (2 voti)

12

Sono in procinto di sviluppare un modulo di gestione dei segnali e di routing per un sistema audiovisivo integrato e lo sto progettando con l'intento di essere il più flessibile possibile attraverso diverse reti di distribuzione del segnale. L'intento del modulo è di gestire il routing su un numero di matrici stacked ¹ e gestire la conversione del formato necessaria.

La soluzione migliore che ho esplorato a questo punto è quella di mappare la rete a un grafico con vertici discreti per ogni tipo di segnale supportato dai commutatori e che vengono poi uniti tramite nodi che rappresentano i processori video che gestiscono la conversione del formato.

Icolorirappresentanoiformatidelsegnale.Inodirotondisonoswitcher,sorgentiosink.Inodiquadratisonoprocessorivideocheeseguonolaconversionedelformato.

Dalìpossousareun'implementazionedi l'algoritmo di Dijkstra per identificare il percorso che deve essere formato per per ottenere l'input X sull'output Y. Ciò dovrebbe consentire l'inoltro dei dati sulla configurazione di input / output di tutti gli switcher e processori e il modulo adattarsi di conseguenza.

Questa è una soluzione appropriata o esiste un approccio alternativo che potrebbe valere la pena di investigare?

_{¹ alias "crossbar switch", un router video con ingresso M x N output che supporta connessioni uno-a-molti. Ogni dispositivo fisico può gestire più formati di segnale e può o meno essere in grado di eseguire qualsiasi conversione di formato.}

modifica: come accennato da Péter Török, il grafico non sarà necessariamente un albero, il diagramma è un semplice esempio per illustrare l'idea. Se implementati nel "mondo reale" possono esistere percorsi multipli che offrono vari livelli di definizione (DVI > VGA > component > composite) che stavo progettando di rappresentare con la ponderazione del bordo.

modifica 2: Ecco un esempio un po 'più completo con direttività indicato e che mostra una rete composta da due tipi di segnale. L'esempio iniziale è stato leggermente modificato in modo che ogni input e output su un dispositivo sia definito come un nodo discreto in quanto fornirà i dati richiesti per controllare la selezione del routing / input della matrice.

design algorithms

posta Kim Burgess 06.12.2011 - 07:15

fonte

2 risposte

2

Potresti essere in grado di usare A * (la forma più generale dell'algoritmo di Dijkstra) per cercare il grafico in questione. Hai menzionato i costi delle ponderazioni nel tuo commento:

Additive. The theory being this will allow it to be defined such that the higher the definition of the signal path, the lower the weighting. Edges which connect nodes that perform format conversion would then be given a weighting higher than that assigned to edges which connect non-conversion nodes. This would route the signal in it's native format if possible, only involving format conversion (and associated signal degradation and equipment utilisation) when necessary

Se ho capito bene, vuoi trovare il percorso del percorso dal costo più basso dall'inizio alla meta. Se fornisci ad ogni nodo sia un costo effettivo che una stima (euristica) rispetto all'obiettivo (che è sia ammissibile che coerente), allora A * è garantito per fornire una soluzione ottimale. Potrebbe essere eccessivo, a seconda di quanto comprendo bene il tuo problema.

risposta data 07.12.2011 - 03:21

fonte

Leggi altre domande sui tag design algorithms

È possibile utilizzare il compilatore Intel C / C ++ su Linux per creare file oggetto da collegare su Windows? Test unitario in Django

score 4 · Accepted Answer

Questo è un albero, Dijkstra è O ( n ^ 2 ) overkill. La ricerca di ampiezza O ( n ) è sufficiente.

EDIT: avvia il BFS in qualsiasi nodo con almeno due gradi.

EDIT2: Poiché il grafico non è garantito come un albero, usa Dijkstra, se vuoi ottimizzare un po ', puoi prima "spogliare" il grafico di tutti i vertici del grado uno (per loro, il percorso è banale) , compresi quelli che acquisiscono il grado uno a causa dello stripping dei loro ex-vicini di casa, e fanno il Dijkstra sul resto (che è esattamente la parte "non-albero").

Inoltre, direi che vuoi percorsi da ogni nodo a ogni altro, vero? L'algoritmo di Dijsktra fa solo percorsi da uno a tutti gli altri. Forse l'algoritmo di Floyd-Warshall sul resto spogliato. Naturalmente, se la topologia è molto dinamica, è meglio fare il (stripping e) Dijkstra, ad hoc.