[C++] Algorimo con grafi

[vegeta83ssj]

Salve a tutti,
devo realizzare un algoritmo euristico per il problema del commesso viaggiatore (ATSP).
I dati di partenza sono una matrice dei costi ("peso" di un arco), il numero di nodi e una rappresentazione a lista di adiacenza del grafo.
Un certo passo dell'algoritmo richiede che io estragga tutti i sottocicli, li memorizzi e di questi vada a selezionare quello col maggior numero di nodi.

Supponendo di avere come lista di adiacenza (già in notazione C, quindi col primo elem=0;)

lista[] = {4,2,3,1,5,6,0}

Abbiamo il ciclo 0->4->5->6->0 di 4 nodi ed il ciclo 1->2->3->1 di 3 nodi.

La mia domanda è:
c'è un qualche algoritmo noto o qualche suggerimento che mi permetta di:


Trovare il ciclo col maggior numero di nodi
Memorizzarlo
Contemporaneamente avere salvare anche gli altri cicli che utilizzerò in seguito insieme al loro numero di nodi


Nel nostro esempio vorrei avere ad esempio:
ciclo uno = {0,4,5,6} con 4 nodi
ciclo due = {1,2,3} con 3 nodi

:help: :help: :help: :help: :help: :help: :help: :help:

[socste]

Ciao!
Per cosa sta la "A" in ATSP? Il TSP è un problema NP-Completo, in uni avevo seguito un corso dove si proponeva l'uso di algoritmi genetici per avvicinarsi all'ottimo..
..se non ricordo male, il grafo nel TSP è completamente connesso, no?

ciao
s-

[vegeta83ssj]

A sta per Asimmetrico.
L'algoritmo che devo implementare per risolverlo è il PATCH:

ALGORITHM “PATCH” (Karp-Steele, 1985)

1) Solve the Assignment Problem (AP) corresponding to the cost matrix (cij).

2) If the current AP solution is a tour then STOP.

3) Consider the subtour S having the maximum number of vertices.
“Expand” S by combining (“patching”) it, through a 2 arc exchange, with a different subtour S’ so as to minimize the variation of the global cost of the two subtours S and S’.
Return to STEP 2.

Sono fermo proprio al passo 3.