[TSP] aiuto con algoritmo

[giacomo.bezzi]

Salve a tutti,

ho provato ad abbozzare un algoritmo per il TSP euclideo. Dovrei però provarne la validità in termini di precisione (quanto la soluzione si discosta dall'ottimo) e di complessità dell'algoritmo.

Ho sfruttato il metodo "Graham scan" per ottenere l'inviluppo convesso dell'insieme dei nodi (che chiamo percorso iniziale). Ora scelgo il nodo più vicino ad un arco e lo faccio entrare nel percorso, ripeto questa operazione finché il percorso non tocca tutti i nodi.

Ho provato l'algoritmo (a mano, con carta e matita) su diversi insiemi di punti (dai 10 ai 20 punti) e ho sempre trovato il percorso ottimo. Ma come posso davvero valutarne la precisione?

So che il primo passo (Graham scan) ha costo $ O(nlog(n)) $ , il passo successivo devo calcolare per ogni nodo la distanza da ogni arco, quindi qual'è la complessità complessiva?

Spero di essere riuscito a spiegarmi...

Vi ringrazio in anticipo per ogni suggerimento

ps: non so se questo algoritmo è uguale ad altri già esistenti, io ho cercato un po' sul web ma non ho trovato niente (ho trovato moltissimi algoritmi per il TSP, ma non questo).

[Rggb1]

Strano, però... suggerisco due workaround:
- nella printRimanenti togli l'assegnazione alla dichiarazione:

struct point *curPoint;
curPoint=firstRimanente;

- se ancora non va, prova a vedere se nella funzione di stampa funziona con il primo e basta, ovvero commenta tutto e stampa solo i valori x,y di firstRimanente.

[giacomo.bezzi]

Grazie davvero, ora funziona tutto!

Adesso posso andare avanti con il resto dell'algoritmo

[Rggb1]

Benissimo, se e quando poi fai anche delle prove per la valutazione posta pure i risultati, che interessa

[giacomo.bezzi]

Salve a tutti,
scusate se riesumo questo vecchio thread, ma nell'ultimo anno ho avuto poco tempo da dedicare a questo problema. Per fortuna con l'arrivo delle vacanze ho ritrovato un po' di tempo e mi sono rimesso su questo algoritmo.
Ho rifatto praticamente tutto, ho scritto il sorgente in R e C per sfruttare la velocità del C e la comodità di R e (miracolosamente) sono riuscito a far funzionare tutto.

Ho usato una variante leggermente più semplice dell'algoritmo descritto l'anno scorso:
1) Calcolo l'inviluppo convesso
2) Inserisco nel percorso il nodo che "allunga meno" il percorso
3) Ripeto 2 fino a quando ho inserito tutti i nodi nel percorso

Oggi ho fatto un po' di test per valutare velocità e precisione.
Ho preso i dati da http://www.tsp.gatech.edu/ ed ho nei percorsi con pochi nodi (<100) uno scostamento del 5% dall'ottimo, mentre il peggiore ha uno scostamento di quasi il 20% (Tanzania - 6117 nodi).
Riguardo la velocità penso (magari qualcuno mi può aiutare a essere più preciso) che la complessità computazionale sia $O(n^3)$. Se può essere d'aiuto aggiungo che l'algoritmo ha impiegato circa 9 secondi per un'istanza con 650 nodi e circa 2 ore per i 6117.

Adesso che ho sono riuscito a implementare l'algoritmo e fare qualche test mi piacerebbe cercare di migliorare l'algoritmo, sopratutto in termini di precisione. Al momento ho due idee in testa:
Creare una procedura per individuare e correggere gli incroci sul percorso;
Riconoscere gruppi di nodi (magari poteri usare una cluster analysis) e calcolare localmente il percorso che poi va opportunamente inserito.

Grazie in anticipo per qualsiasi suggerimento e consiglio!

[Deckard1]

Sulla complessità del tuo algoritmo si può dire poco: dovresti spiegarci come implementi le varie operazioni.
Utilizzando tecniche non banali sono sicuro che si possa scendere ad almeno $O(n^2 log n )$: dato un insieme $P$ di punti nel piano e un segmento $s$ è possibile calcolare il punto $x in P$ più vicino ad $s$ in tempo logaritmico (utilizzando i diagrammi di Voronoi). Ho fatto una breve ricerca e non sono riuscito a trovare algoritmi efficienti che, dati in input $P$ e questa volta anche un insieme $S$ di segmenti, calcolino il segmento $s in S$ e il punto $p in P$ a distanza minore. Sembra che questa variante della neighbour search non sia studiata in letturatura.
Sulla precisione non credo si possa dire granché a livello teorico. Un errore massimo del 20% comunque credo sia piuttosto buono, anche se credo esistano istanze per le quali il tuo algoritmo si possa comportare decisamente peggio.
Il problema principale di questo algoritmo è che secondo me per essere un'euristica è troppo complesso: calcolare ogni volta il punto 2 è computazionalmente oneroso, anche se forse a livello teorico non eccessivamente perchè credo ci sia un discreto margine di miglioramento.

[giacomo.bezzi]

"Deckard":Sulla complessità del tuo algoritmo si può dire poco: dovresti spiegarci come implementi le varie operazioni.

Posto uno pseudocodice della parte centrale dell'algoritmo, ovvero quando ha già calcolato l'inviluppo convesso e deve inserire nel percorso i punti che sono rimasti fuori:

WHILE (listOUT->next NOT NULL)
  currentIN  = listIN
  currentOUT = listOUT

  WHILE (currentOUT->next NOT NULL)
    WHILE (currentIN->next NOT NULL)

      # Calcola di quanto si allunga il percorso e scelgo il minimo
      IF (delta(currentIN->item, currentIN->next->item, currentOUT->item)  < deltaMIN)
        deltaMIN = delta
        position = currentIN->item
        new      = currentOUT->item

  # Insericso new in posizione position e elimino new da listOUT
  add(new, position)
  out(new)

Le funzioni add e out semplicemente inseriscono e rimuovono gli elementi dalla lista, delta invece calcola quanto si allunga il percorso:

function delta(int positionA int positionB, int positionC)

  a = coordinates[positionA]
  b = coordinates[positionB]
  c = coordinates[positionC]
  
  return sqrt[(a.x^2 - c.x^2)+(a.y^2 - c.y^2)] + sqrt[(c.x^2 - b.c^2)+(c.y^2 - b.y^2)] - sqrt[(a.x^2 - b.x^2)+(a.y^2 - b.y^2)]

Faccio notare che in questa versione non ho usato come regola di inserire il punto più vicino, ma bensì di inserire il punto che allunga meno il percorso. Questo perché avevo dei problemi a definire correttamente la distanza di un punto da un segmento (trovavo infatti la distanza di un punto dalla retta contenente il segmento, che naturalmente non funzionava).
Il suggerimento di usare i diagrammi di Voronoi sembra una buona soluzione, quindi intanto ringrazio Deckard e vedrò cose riesco a combinare.

Per il resto hai ragione, l'algoritmo così è piuttosto lento e non molto preciso, ma guardando il plot del percorso ho l'impressione che ci siano margini di miglioramento; andrebbe già molto meglio se riuscissi a evitare o correggere in un passaggio successivo gli incroci (penso esistano tecniche per farlo).
Per quanto riguarda la complessità mi viene in mente che si potrebbe limitare il campo di ricerca dei punti ad esempio con tecniche di clustering, ma sono solo idee buttate lì.

Comunque grazie ancora e qualsiasi suggerimento è ovviamente benvenuto!