Il problema del commesso viaggiatore (array ricorsivo)

[buonste]

Per risolvere un algoritmo di routing sotto forma di Problema del Commesso Viaggiatore sono arrivato ad una soluzione "vicino più vicino" filtrando cioè solo le connessioni tra nodi (coordinate x,y) adiacenti.

Più nel dettaglio ho ottenuto un'array bidimensionale di nodi dove la chiave primaria è il nodo di partenza, la chiave secondaria il nodo di destinazione ed il valore il peso dell'arco:

Così, seguendo questo esempio...

array ( 
   [124,106] => Array (
      [124,110] => 4
      [128,106] => 4
   )
   [124,110] => Array (
      [124,106] => 4
      [128,110] => 4
      [124,114] => 4
   )
   [124,114] => Array (
      [128,114] => 4
      [124,118] => 4
      [124,110] => 4
   )
   [124,118] => Array (
      [128,118] => 4
      [124,114] => 4
   )
   [125,102] => Array (
      [127,100] => 2.8284271247462
   )
   [126,122] => Array (
      [128,123] => 2.2360679774998
   )
) 

Il nodo [124,106] è collegato ai nodi [124,110] e [128,106].
A sua volta il nodo [124,110] è collegato al nodo sorgente (che dovrà risultare "visitato" e quindi da ignorare) ed ai nodi [128,110] e [124,114] "da visitare".

Ogni "collegamento" (o arco) ha un peso ed il mio scopo è costruire un array multidimensionale e ricorsivo calcolando tutte le possibilità di intersezione e (possibilmente) avente come ultimo valore la somma di tutti gli archi per raggiungerlo.

array ( 
    [124,106] => Array (
        [124,110] => Array (
            [128,110] => Array (
            [...]
        )
        [124,114] => Array (
            [128,114] => Array (
            [...]
        )
            [124,118] => Array (
            [...]
        )
            [124,110] => Array (
            [...] = Array (
                        [...] = $somma_degli_archi
                    )
        )
    (...)
) 

E' fattibile? Da dove inizio?
Anticipatamente grato a chiunque mi potrà esser d'aiuto.

Ste

[Fractals87]

Ok provo a buttare una soluzione anche perchè interessa anche a me avere un parere da più esperti.

Se per soluzione vicino più vicino intendi spostarsi dal punto di partenza al più vicino io farei in questo modo :
Due cicli for

1° for della dimensione del array
dentro il primo form cancello il dato della mia partenza
2° for dimensione array (che ora sarà di meno uno dato l'eliminazione della dato di partenza)
calcolo la distanza tra tutti i punti e di volta in volta mi salvo il puù vicino (confrontando il valore calcolato con il precedente calcolo salvato in una apposita variabile)

Questa soluzione però non è corretta dato che non ti riporta al punto di partenza e di conseguenza il tragitto non è quello ottimale...

Esistono su internet diversi algoritmi da applicare per il calcolo del percorso ottimale siccome si tratta di un interrogativo molto discusso e gli algoritmi per ottenere un risultato soddisfacente sono Branch-&-Bound, Branch-&-Cut oppure euristiche come Nearest Neighbor.

Bo spero di essere stato di aiuto

[Santino83_02]

non ho capito che vuoi fare

vuoi trovare l'algoritmo per trovare il percorso a peso minimo in un grafo, oppure sai qual'è l'algoritmo ma non sai come realizzarlo in php? purtroppo ora non ho il libro di Ricerca Operativa sotto mano, però l'algoritmo esiste e in genere viene presentato in pseudocodice... ad esempio quà

http://www.unipa.it/valerio.lacagnin...eoriaGrafi.pdf

leggiti bene bene quello che ti dice il tizio e come funziona l'algoritmo, probabilmente più che arrevi ricorsivi ( se non ricordo male) se ne usavano un paio, uno per l'associazione nodo -> peso e uno per la rappresentazione del grafo nella forma nodo -> elenco_nodi_raggiungibili, ma è passato tanto tempo potrei sbagliarmi

[buonste]

Provo a spiegarmi più dettagliatamente...

L'approccio che ho bisogno di dare al problema del commesso viaggiatore è quello di tipo Nearest Neighbor. Più nel dettaglio su un piano cartesiano ho una lista di "n" (compreso tra 50 e 100) nodi (x,y).
Il mio scopo è trovare un algoritmo che possa toccarli tutti nel minor cammino possibile tenendo in considerazione che il nodo n+1 dev'essere adiacente al nodo n.

Ora sulla base di questa premessa proseguo con l'esempio pratico. Ho una mappa di nodi ordinati come si vede in questa figura e vorrei invece trovare un algoritmo di ordinamento degli stessi che mi produca un'output come questo o qualcosa di molto simile.

Nel primo caso il routing è chiaramente poco ottimizzato, nel secondo invece vorrei riuscire a creare un algoritmo euristico con la logica del "vicino più vicino".

Per lo scopo ho costruito un array aventi come chiave la coordinata del nodo "n"esimo e come valore la lista di nodi adiacenti:

Node [124,110] : Nearest are [124,106] , [128,106] , [128,110] , [124,114] , [128,114]
Node [124,106] : Nearest are [124,110] , [125,102] , [128,106] , [128,110]
Node [125,102] : Nearest are [124,106] , [127,100] , [128,106] , [129,102]
Node [127,100] : Nearest are [125,102] , [129,102] , [129,97] , [131,98]
Node [128,106] : Nearest are [124,110] , [124,106] , [125,102] , [128,110] , [132,106] , [129,102] , [132,110]
Node [128,110] : Nearest are [124,110] , [124,106] , [128,106] , [132,106] , [132,110] , [124,114] , [128,114] , [132,114]
Node [132,106] : Nearest are [128,106] , [128,110] , [129,102] , [132,110] , [136,106] , [133,102] , [136,110]
Node [129,102] : Nearest are [125,102] , [127,100] , [128,106] , [132,106] , [131,98] , [133,102]
Node [129,97] : Nearest are [127,100] , [131,98] , [133,94]
Node [131,98] : Nearest are [127,100] , [129,102] , [129,97] , [133,102] , [135,98] , [133,94]
Node [132,110] : Nearest are [128,106] , [128,110] , [132,106] , [136,106] , [136,110] , [128,114] , [132,114] , [136,114]
Node [136,106] : Nearest are [132,106] , [132,110] , [133,102] , [136,110] , [137,102] , [140,110] , [140,106]
Node [133,102] : Nearest are [132,106] , [129,102] , [131,98] , [136,106] , [135,98] , [137,102]
Node [135,98] : Nearest are [131,98] , [133,102] , [133,94] , [137,102] , [137,94] , [139,98]
Node [133,94] : Nearest are [129,97] , [131,98] , [135,98] , [137,94]
Node [124,118] : Nearest are [124,114] , [128,114] , [128,118] , [126,122]
Node [124,114] : Nearest are [124,110] , [128,110] , [124,118] , [128,114] , [128,118]
Node [136,110] : Nearest are [132,106] , [132,110] , [136,106] , [132,114] , [136,114] , [140,110] , [140,106] , [140,114]
Node [137,102] : Nearest are [136,106] , [133,102] , [135,98] , [140,106] , [141,102] , [139,98]
Node [137,94] : Nearest are [135,98] , [133,94] , [139,98] , [141,94]
Node [128,114] : Nearest are [124,110] , [128,110] , [132,110] , [124,118] , [124,114] , [128,118] , [132,114] , [132,118]
Node [128,118] : Nearest are [124,118] , [124,114] , [128,114] , [126,122] , [132,114] , [132,118] , [130,122]
Node [126,122] : Nearest are [124,118] , [128,118] , [128,123] , [129,126] , [130,122]
Node [128,123] : Nearest are [126,122] , [129,126] , [130,122]
Node [129,126] : Nearest are [126,122] , [128,123] , [130,122] , [133,126] , [133,128]
Node [132,114] : Nearest are [128,110] , [132,110] , [136,110] , [128,114] , [128,118] , [132,118] , [136,114] , [136,118]
Node [132,118] : Nearest are [128,114] , [128,118] , [132,114] , [130,122] , [136,114] , [136,118] , [134,122]
Node [130,122] : Nearest are [128,118] , [126,122] , [128,123] , [129,126] , [132,118] , [133,126] , [134,122]
Node [133,126] : Nearest are [129,126] , [130,122] , [133,128] , [134,122] , [137,126] , [137,128]
Node [133,128] : Nearest are [129,126] , [133,126] , [137,126] , [137,128]
Node [136,114] : Nearest are [132,110] , [136,110] , [132,114] , [132,118] , [136,118] , [140,110] , [140,114] , [140,118]
Node [136,118] : Nearest are [132,114] , [132,118] , [136,114] , [134,122] , [140,114] , [140,118] , [138,122]
Node [134,122] : Nearest are [132,118] , [130,122] , [133,126] , [136,118] , [137,126] , [138,122]
Node [137,126] : Nearest are [133,126] , [133,128] , [134,122] , [137,128] , [138,122] , [141,126] , [141,129]
Node [137,128] : Nearest are [133,126] , [133,128] , [137,126] , [141,126] , [141,129]
Node [140,110] : Nearest are [136,106] , [136,110] , [136,114] , [140,106] , [144,106] , [144,110] , [140,114] , [144,114]
Node [140,106] : Nearest are [136,106] , [136,110] , [137,102] , [140,110] , [141,102] , [144,106] , [144,110]
Node [141,102] : Nearest are [137,102] , [140,106] , [139,98] , [143,98] , [145,102] , [144,106]
Node [139,98] : Nearest are [135,98] , [137,102] , [137,94] , [141,102] , [141,94] , [143,96] , [143,98]
Node [141,94] : Nearest are [137,94] , [139,98] , [143,96] , [143,98]
Node [143,96] : Nearest are [139,98] , [141,94] , [143,98] , [147,98]
Node [143,98] : Nearest are [141,102] , [139,98] , [141,94] , [143,96] , [145,102] , [147,98]
Node [145,102] : Nearest are [141,102] , [143,98] , [144,106] , [147,98] , [148,101] , [149,102] , [148,106]
Node [144,106] : Nearest are [140,110] , [140,106] , [141,102] , [145,102] , [144,110] , [148,106] , [148,110]
Node [144,110] : Nearest are [140,110] , [140,106] , [144,106] , [148,106] , [148,110] , [140,114] , [144,114] , [148,114]
Node [147,98] : Nearest are [143,96] , [143,98] , [145,102] , [148,101] , [149,102]
Node [148,101] : Nearest are [145,102] , [147,98] , [149,102] , [151,105]
Node [149,102] : Nearest are [145,102] , [147,98] , [148,101] , [148,106] , [151,105]
Node [148,106] : Nearest are [145,102] , [144,106] , [144,110] , [149,102] , [148,110] , [151,105] , [151,109]
Node [148,110] : Nearest are [144,106] , [144,110] , [148,106] , [151,109] , [144,114] , [148,114] , [151,113]
Node [151,105] : Nearest are [148,101] , [149,102] , [148,106] , [151,109]
Node [151,109] : Nearest are [148,106] , [148,110] , [151,105] , [151,113]
Node [140,114] : Nearest are [136,110] , [136,114] , [136,118] , [140,110] , [144,110] , [140,118] , [144,114] , [144,118]
Node [140,118] : Nearest are [136,114] , [136,118] , [140,114] , [138,122] , [144,114] , [142,122] , [144,118]
Node [138,122] : Nearest are [136,118] , [134,122] , [137,126] , [140,118] , [142,122] , [141,126]
Node [144,114] : Nearest are [140,110] , [144,110] , [148,110] , [140,114] , [140,118] , [144,118] , [148,118] , [148,114]
Node [142,122] : Nearest are [140,118] , [138,122] , [141,126] , [145,126] , [146,122] , [144,118]
Node [141,126] : Nearest are [137,126] , [137,128] , [138,122] , [142,122] , [142,127] , [141,129] , [145,126]
Node [142,127] : Nearest are [141,126] , [141,129] , [145,126]
Node [141,129] : Nearest are [137,126] , [137,128] , [141,126] , [142,127] , [145,126]
Node [145,126] : Nearest are [142,122] , [141,126] , [142,127] , [141,129] , [146,122] , [148,124]
Node [146,122] : Nearest are [142,122] , [145,126] , [144,118] , [148,118] , [148,124] , [150,121]
Node [144,118] : Nearest are [140,114] , [140,118] , [144,114] , [142,122] , [146,122] , [148,118] , [148,114]
Node [148,118] : Nearest are [144,114] , [146,122] , [144,118] , [148,114] , [150,121] , [151,117]
Node [148,114] : Nearest are [144,110] , [148,110] , [144,114] , [144,118] , [148,118] , [151,117] , [151,113]
Node [148,124] : Nearest are [145,126] , [146,122] , [150,121]
Node [150,121] : Nearest are [146,122] , [148,118] , [148,124] , [151,117]
Node [151,117] : Nearest are [148,118] , [148,114] , [150,121] , [151,113]
Node [151,113] : Nearest are [148,110] , [151,109] , [148,114] , [151,117]

Posto che uno degli nodi adiacenti dev'esser sequenzialmente successivo al nodo corrente, come posso calcolare la lista di possibili combinazioni che mi permettando di toccare tutti i nodi (una sola volta naturalmente?!?).
Sulla base delle possibili combinazioni calcolo la distanza di ciascuna ed estraggo la minima.

Detto questo vi ringrazio per aver iniziato ad approcciare il mio problema.

Ciao,
Stefano

[Santino83_02]

Mi dovrei rileggere ricerca operativa a riguardo, sono molto arrugginito. cmq leggevo

http://en.wikipedia.org/wiki/Nearest...bour_algorithm
http://www.itccalo.it/progetti/FACEB...I/Commesso.htm

Puoi scegliere vari algoritmi che tendenizlamente possono darti una soluzione al problema, anche se non ottima (visto che non esiste un algoritmo che ti dia soluzione ottima al problema)

Quindi, come dice wikipedia, una possibile soluzione è

- These are the steps of the algorithm:
- stand on an arbitrary vertex as current vertex.
- find out the shortest edge connecting current vertex and an unvisited vertex V.
- set current vertex to V.
- mark V as visited.
- if all the vertices in domain are visited, then terminate.
- Go to step 2.

poi come leggi nel secondo link, esistono vari algoritmi che dovrebbero risolvere il tuo problema, come

http://en.wikipedia.org/wiki/Kruskal's_algorithm
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

carina questa sintesi:
http://raffaelemarino.altervista.org...ui%20grafi.htm

e relativi.

Rileggendo poi il tuo post ho notato che non avevi un peso vero e proprio degli archi, ma avevi punti cartesiani, quindi immagino che i primi algoritmi che cito in questa risposta non vadano bene. Invece nell'ultimo link c'è proprio Example 16.5. Implementation for Solving the Traveling-Salesman Problem che prende in input la lista dei vertici, il vertice di partenza, e calcola lo spanning tree minimo per unire tutti i vertici. Dovrebbe essere quello che cerchi.

Le mie conoscenze di teoria dei grafi finiscono qui, mi spiace

[buonste]

Ciao Santino,
la tua spiegazione è chiara ed esaustiva ma non risolve il mio problema.

I 2 algoritmi proposti (che avevo già studiato prima di aprire questo thread) non fanno al mio caso poichè quello di Dijkstra calcola il percorso minimo tra due nodi ma non prevede che si debba passare per tutti i nodi, mentre quello di Kruskal's prevede che si passi per tutti i nodi del grafo ma permettendo il passaggio per più volte dallo stesso nodo.

E' vero che nel mio primo esempio non l'ho specificato ma il peso degli archi è determinato/determinabile con il teorema di Pitagora tra un nodo e quelli nell'intorno.

Ad ogni modo apprezzo molto il tuo interesse e non voglio abusarne.

Anzi chiedo all'admin se ritiene opportuno spostare la discussione da PHP in qualche altro Forum OFF-Topic perchè la stessa si sta spostando da PHP a Ricerca Operativa e Analisi Matematica.

Grazie ancora a tutti!
Ste

[Santino83_02]

Originariamente inviato da buonste
Ciao Santino,
la tua spiegazione è chiara ed esaustiva ma non risolve il mio problema.

I 2 algoritmi proposti (che avevo già studiato prima di aprire questo thread) non fanno al mio caso poichè quello di Dijkstra calcola il percorso minimo tra due nodi ma non prevede che si debba passare per tutti i nodi, mentre quello di Kruskal's prevede che si passi per tutti i nodi del grafo ma permettendo il passaggio per più volte dallo stesso nodo.

E' vero che nel mio primo esempio non l'ho specificato ma il peso degli archi è determinato/determinabile con il teorema di Pitagora tra un nodo e quelli nell'intorno.

Ad ogni modo apprezzo molto il tuo interesse e non voglio abusarne.

Anzi chiedo all'admin se ritiene opportuno spostare la discussione da PHP in qualche altro Forum OFF-Topic perchè la stessa si sta spostando da PHP a Ricerca Operativa e Analisi Matematica.

Grazie ancora a tutti!
Ste

guarda che nell'ultimo link ti ho scritto che c'è l'algoritmo che cerchi, l'ultimo esempio

e cmq se leggessi bene quello che ti si dice (ok, su Dijkstra mi son sbagliato), vedresti che Kruskal serve a :

Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex,

cmq ripeto, mi pare che l'algoritmo illustrato alla fine di questo articolo http://raffaelemarino.altervista.org...ui%20grafi.htm sia quello che cerchi nello specifico. Ovviamente, pure se leggi in giro, una soluzione ottima ed efficiente non è stata trovata, pseudo-ottime ed efficienti si (quell'algoritmo va a O(v^2) che non è male per valori di v non troppo grandi)

cmq si, con php c'entra poco

[buonste]

Ciao Santino,
grazie ancora.

Lungi da me pretendere di aver ragione ma l'algoritmo di Kruskal si comporta come descritto permettendo di raggiungere 2 nodi distinti partendo dallo stesso e quindi di toccare un nodo singolo 2 volte:

In questo esempio è evidente che i nodi C e G sono collegati allo stesso nodo E mentre io devo riuscire a raggiungere tutti i nodi naturalmente con un path che escluda quelli già visitati.

In merito all'algoritmo descritto nell'articolo che m'hai segnalato, non fa al mio caso poichè presuppone che il nodo n+1 possa esser solo in assoluto il più vicino al nodo n mentre nel mio caso il nodo n+1 potrebbe essere il "secondo più vicino" al precedente.

Con questo presupposto l'algoritmo è valido per i primi nodi processati ed aggiunti alla lista "visitati" ma fallisce quando ne mancano pochi poichè inesorabilmente e presumibilmente gli ultimi "x" (x >= 2) nodi potrebbero non esser adiacenti. Ed io questo vorrei evitarlo.

Ad ogni modo continuo le mie delucubrazioni, se vengo a capo di qualcosa sarà mia cura aggiornarvi (sempre che interessi a qualcuno, naturalmente).

Ciao,
Stefano

[Fractals87]

So di non essere di aiuto ma sto seguendo la discussione, se infine posti una soluzione te ne sono grato

[Santino83_02]

allora facciamo un passo indietro

http://wikiricop.diiga.univpm.it/med...blemi_notevoli

concetto di nodi adiacenti:

1) Nodi adiacenti: Due nodi si dicono adiacenti se sono collegati da uno stesso arco.

nel tuo caso:

1) l'insieme dei dati può essere espresso come un grafo?

2) dato un punto V(x,y), per trovare il più vicino tra i punti collegati ad esso puoi fare due cose: considerare il peso dell'arco o, ad esempio, la distanza dal punto V al punto Vi usando per esempio http://en.wikipedia.org/wiki/Euclidean_distance

ora, l'algoritmo dell'italiano fa i seguenti passi:

- parte da un punto dato
- per oguno dei punti adiacenti ad esso e non ancora visitati, calcola la distanza dal punto e sceglie quello più vicino
- lo aggiunge allo spanning tree, si sposta sul nodo selezionato e continua

come avrai letto dal tizio

Applicazione di Nearest-Neighbor Heuristic (del confinante più vicino)
La Figura 16.6 illustra una soluzione al problema del commesso viaggiatore che usa il confinante più vicino di casa. Normalmente quando un grafo è disegnato per il problema del commesso viaggiatore, gli archi che connettono ogni vertice ad un altro non si mostrano esplicitamente fino a quando gli archi non sono quelli che cerchiamo. Nella figura, ogni vertice è esposto insieme alle coordinate del punto che rappresenta. Le linee cancellate in ogni configurazione sono le linee le cui distanze sono state confrontate. La linea più scura è l'arco aggiunto al ciclo. Il ciclo ottenuto usando il confinante più vicino ha una lunghezza di 15,95. Il giro ottimale ha una lunghezza di 14,71 che sono approssimativamente più brevi dell' 8%.

quindi probabilmente non ho capito una sfumatura del tuo prolema, perchè a me pare che sia esattamente la soluzione al tuo problema

ovviamente, come viene detto anche nell'articolo, non esiste la soluzione ottima perchè ancora non è stato trovato un algoritmo capace di questo, ma appunto la soluzione è OTTIMALE (sostanzialmente è una soluzione dell'insieme delle soluzioni ottime, tra le quali è presente anche la soluzione OTTIMA)

quindi ti prego spiegami qual'è la differenza tra la situazione esposta nell'esempio dell'articolo e la tua, che la cosa mi stà cominciando ad appassionare