Newsgroup: it.scienza.informatica
Titolo: [Ricerca Operativa] - Lista di percorsi

Dunque.
Immaginiamo di avere il solito grafo di nodi ed archi ciascuno con il
suo peso, dove il peso č lo "sforzo" necessario per passare dal nodo x
al nodo y.
Nel mio caso si tratta del solito esempio della cartina geografica
dove i nodi sono alcune citta', mentre gli archi sono le distanze.
Ovviamente le citta' non sono tutte collegate, ma per ciascuna citta'
disponiamo delle distanze con le citta' limitrofe.
Ora, disponiamo anche di N percorsi oridnati:
A0,A1 ... An
B0,B1 ... Bn
C0,C1 ... Cn
Dove ciascuno step di ogni percorso č proprio una citta' ovvero un
nodo del grafo.
Supponiamo di dover eseguire tutti i percorsi, ovvero toccare tutti i
nodi di ciascun percorso in ordine.
Qual č la sequenza generale che minimizza il percorso totale?
L'assunto č quello che i nodi di ciascun percorso devono essere
toccati in ordine, ma nessuno vieta di mescolare i percorsi, es:
A5-B6-B7-C1-A6-C2, etc.
Non č ovviamente possibile percorrere anche solo un pezzo di un
percorso al contrario (ES: A5-B6-A6-A7-B5 xxx)
E' una sorta di "Commesso viaggiatore" o "Postino Cinese" un po'
piu'... non riesco neppure a capire se č piu' semplice o piu'
difficile.
Qualcuno a qualche idea su come informatizzare questo algoritmo, senza
ovviamente passare dalla forza bruta che č nel mio caso inaccettabile?
Grazie a chiunque voglia darmi un aiuto.
Ciao, Beppe.
g_...@libero.it

 ovviamente passare dalla forza bruta che è nel mio caso inaccettabile?
Sempre commesso viaggiatore e'. Vedi un po' tu che strumenti hai a
disposizione.
 Raffaello

 astrai dagli archi contenuti nei percorsi iniziali.
Grazie per la risposta.
Eppure non ci sono ancora.
Se avessi uno solo degli N percorsi da compiere, non si tratterebbe di
Commesso viaggiatore. Semplicemente il percorso sarebbe gia' stato dato, e
si tratterebbe al piu' di risolvere un Dijkistra (mai lo scrivero' giusto)
per ciascuno degli archi del mio percorso.
Il fatto invece è che ho N percorsi ordinati, e non riesco proprio a vedere
come fare entrare il commesso viaggiatore. Non devo toccare tutti i nodi
disordinatamente, ma in modo pseudo-ordinato.
In pratica, se disponessi di soli 2 percorsi, qualora decidessi di partire
con A0, successivamente avrei la scelta vincolata di andare o ad A1, oppure
a B0. Nessuna altra alternativa pemessa dal commesso viaggiatore ben piu'
libero di organizzarsi il percorso. Nulla vieterebbe di passare per quello
che è 
p.es
 il B5, ma è come se non fosse stato fatto, in quanto potro'
considerare B5 come soddisfatto solamente quando vi passero' dopo aver gia'
toccato B1, B2, B3 e B4, in ordine.
Mi accontenterei anche di una soluzione Greedy, non sto cercando l'ottimo in
assoluto.
Ho provato con il seguente:
Ad ogni passo dell'algoritmo, scelgo il prossimo nodo tra quelli
disponibili, che sono solo N (ovvero il numero dei percorsi). Quelli
disponibili infatti sono il primo nodo non ancora toccato per ciascun
percorso. Scelgo come prossimo nodo ovviamente quello piu' vicino
(risolvendo quindi N volte Dijkistra).
Questa soluzione Greedy non soddisfa pero' assolutamente il mio problema.
Riesco ancora a trovare ad "occhio" una soluzione migliore (ma che
ovviamente non mi soddisfa).
Altre idee?
Ciao, Beppe.
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/