Problem metrycznego komiwojażera z algorytmem Floyda

Dla specjalistów Programowanie
#1

Witam!

Mam ogromny problem z rozwiązaniem zadania. Muszę zaimplementować algorytm rozwiązujący problem komiwojażera algorytmem Floyda. Napisałem programik, który liczy najkrótsze ścieżki w grafie, ale nie mam pojęcia co dalej. Z góry dziękuje za pomoc.

#include 

#include 

#include 


using namespace std;



const int n=5;

int G[n][n];

int R[n][n];


void floyd (int g[n][n])

{	

	for (int k=0; k
		for (int i=0; i
			for (int j=0; j
				if(g[i][k]+g[k][j]
				{

					g[i][j]=g[i][k]+g[k][j];

					R[i][j]=k;

				}

}


void droga (int i, int j)

{

	int k = R[i][j];

	if (k!=0)

	{

		droga(i,k);

		cout << k << " ";

		droga (k,j);

	}

}


int main()

{

	for (int i=0; i
		for (int j=0; j
		{

			G[i][j]=10000;

			R[i][j]=0;

		}



	G[0][1]=4;

	G[0][2]=45;

	G[0][3]=39;

	G[0][4]=28;

	G[0][5]=3;

	G[1][0]=3;

	G[1][2]=17;

	G[1][3]=90;

	G[1][4]=46;

	G[1][5]=88;

	G[2][0]=93;

	G[2][1]=77;

	G[2][3]=80;

	G[2][4]=88;

	G[2][5]=18;

	G[3][0]=13;

	G[3][1]=42;

	G[3][2]=36;

	G[3][4]=33;

	G[3][5]=46;

	G[4][0]=33;

	G[4][1]=21;

	G[4][2]=16;

	G[4][3]=56;

	G[4][5]=92;

	G[5][0]=9;

	G[5][1]=16;

	G[5][2]=28;

	G[5][3]=7;

	G[5][4]=25;




	floyd(G);


	for (int i=0; i
		for (int j=0; j
		{

			if(G[i][j]==10000)

				cout << i << " --> " << j << "[drogi nie ma]\n";

			else

				if(i!=j)

				{

					cout << i << " --> " << j << "=" << G[i][j] << ",droga przez:";

					droga(i,j);

					cout << endl;

				}


		}

}
#2

Wpisać w google “algorytm floyda”, przejrzeć pierwsze 3-4 odnośniki i zaadaptować pseudokod.

http://www.algorytm.org/algorytmy-grafo … loyda.html

#3

Ale ja już mam zaimplementowany Algorytm Floyda, problem mam natomiast z tym, jak go wdrożyć by rozwiązywał problem komiwojażera

– Dodane 01.06.2012 (Pt) 13:57 –

Znalazłem taki pseudokod, ale nie wiem jak zaimplementować

algorytm TSP_Flood;

// inicjalizacja

V[T] ={s};

E[T] = {(s, s)};

w[ss] = 0;

koszt = 0;

for (u należy V \ {s}) dist[u] = w[su];

// iteracja

while (|V[T]|< n)

{

f = „wierzchołek ze zbioru V \ V[T] o największej wartości dist”;


for ((i, j) należy E[T]) c[ij] = w[if] + w[fj] - w[ij];

(t, h) = „ łuk z E[T] o najmniejszym koszcie c[th]”;

E[T] = E[T] suma {(t, f ),( f , h)}- {(t,h)};

V[T] = V[T] suma {f };

koszt = koszt + c[th];

for (x należy V \ V[T]) do dist[x]=min{dist[x], w[fx]};

}


Wierzchołki V[T] i łuki E[T], tworzące bieżący cykl, są reprezentowane w tablicy cycle, w której element cycle[i] przyjmuje wartość j, gdy

krawędź (i, j) należy do bieżącego cyklu i 0 w przeciwnym przypadku.
#4

Wiesz mam podobny problem: mam w domu młotek i się zastanawiam jak go zastosować do pieczenia ciastek.

#5

…a to proste, zamist ciasto ugniatać wałkiem, rozbijasz go młotkiem :slight_smile:

#6

Mogę coś zasugerować, rozumiem, że chcesz szukać cykli w celu wykonania algorytmu dwu aproksymacyjnego, bo jak masz pomysł na rozwiązanie w czasie rozsądnym problemu komiwojażera, to myślę, że mogę pomóc ci nad dowodem jak mi przedstawisz swój pomysł na algorytm, a milion dzielimy 50:50.

Jeśli tylko chcesz aproksymować, tu jest to całkiem przystępnie wytłumaczone, jak przy użyciu drzewa rozpinającego wyznaczyć cykl, który nie będzie w żadnym wypadku gorszy dwu krotnie. http://smurf.mimuw.edu.pl/drupal6/node/1142