PDA

View Full Version : :silly: Help! Problema di Ragionamento!


Reiser DarkSide
25-09-2002, 09:42
Allora, studiando i grafi mi è venuto in mente di creare un programmino (il linguaggio poi lo scelgo ma non è un problema) che gestisce ad esempio una rete ferroviaria di 10 nodi.

Dando in ingresso in una matrice tutti i nodi ed i vari cammini riesco, tramite la moltiplicazione tra matrici, ad avere tutti
gli ordini di raggiungibilità e la matrice finale di raggiungibilità che determina se è possibile raggiungere un nodo da un'altro
determinato nodo.

Ora, dato un nodo di partenza ed uno di arrivo riesco facilmente, andando a consultare le matrici, a trovare il numero di cammini
minimo per arrivarci, i vari cammini di ordine successivo, ma non riesco ad elaborare i nodi intermedi tra un cammino e l'altro
se c'è più di un cammino dello stesso ordine! Far provare al computer tutti i cammini è impensabile.. devo trovare una soluzione matematica!

So d non esssere stato chiaro quindi provo a farlo con qualche disegnino


Prendiamo ad esempio un grafo con 4 nodi:

http://utenti.lycos.it/reisershop/grafo.jpg

semplifichiamo mettendo i nomi dei nodi con le iniziali della città..

la matrice di ordine 1 è composta dai soli cammini che collegano le città e questa va inserita in input.

quindi...


Mat1 :

TO MI NA RO

TO 0 1 0 0 se parto da TO posso raggiungere solo MI..

MI 1 0 0 0

NA 1 0 0 1

RO 1 1 0 0


bene, ora se moltiplico questa matrice per se stessa trovo tutti i cammini di ordine 2, ovvero se utilizszando due cammini posso raggiungere un'altra cità.
se poi moltiplico la prima con la seconda trovo tutti i cammini di ordine 3 ecc.. l'ultima matrice sarà quella di raggiungibilità (si crea con la somma logica di tutte le matrici) che mi consente di vedere
se da una città posso raggiungerne un'altra.. ad esempio napoli non è raggiungibile da nessuna città in nessun modo.

Ora, inserita la prima matrice, riesco a ricavare tutte le altre matrici... ma quando volgio sapere in quanti modi è possibile arrivare da una città ad un'altra mi inceppo!

ok, riesco a determinare, consultando la matrici se è possibile arrivarci conun cammin, con due, con tre ecc..
ma una volta determinato che ad esempio ci posso arrivare con 5 cammini, non riesco a tracciare il percorso.. magari ci son più modi di arrivarci con 5 cammini..
la matrice di ordine 5 mi dice solo se è possibile arrivarci con 5 cammini, ma non mi dice in quanti modi ci si arriva con 5 cammini e i nodi intermedi!

(ovviamente era un esempio quelo dei 5 cammini.. nel grafo delle città non è fattibile perchè ha solo 4 nodi e quindi non si fa la matrice di ordine 5, al max la matrice di ordine 3)


Si, lo so.. spiego in modo pietoso, ma se qualcuno ha presente di cosa sto parlando avrà sicuramente capito.. vi prego datemi una manooooooo!!!

DM Ilweran
25-09-2002, 18:59
Non ho la più pallida idea di cosa tu stia chiedendo.
Messo in chiaro questo punto (non so di cosa stai parlando e di conseguenza non so cosa ti sto rispondendo):
NODI = {RO, TO, MI, NA}
ARCHI = {(RO, TO), (RO, MI), (TO, MI), (MI, TO), (NA, TO), (NA, RO)}
Questi sono i dati del grafo orientato.
Senza scartabellare tra libretti e libronzoli (li ho a casa, non qui) direi che devi usare una Breadth-First-Search per visitare e marcare tutti i nodi in base agli archi, se vuoi te la scrivo in pseudo.
Praticamente visiti i nodi in ordine crescente dal nodo di partenza, mantenendo una lista dei nodi già visitati. E', a tutti gli effetti, una coda. Alla fine ti ritrovi con una traccia.
Ovviamente devi elaborare l'algoritmo originale.
Spero di aver capito quello che volevi.
Senza visitare ogni nodo non so, dovrei studiare l'algoritmo per trovare una soluzione. Magari nel weekend quando ho i miei libri.
Ciao