C: Përdorimi i matricave për problemën Travelling Salesman

[pikachu]

Pershendetje,

Kam per te bere nje projekt ne C per problemën Travelling Saleman dhe me duhet te perdor nje matrice per te kryer nje rruge midis dy qyteteve. Problemi eshte se e kam bere projektin, duke perdorur nje algoritem te thjeshte, po nuk shikoj si mund te perdor nje matrice.
Do te doja nje shpjegim, nqse dikush di dicka mbi kete problem.

Pika

[Dr Rieux]

Me poshte ke nje pseudokod per problemin ne fjale

______________________________________________

main algorithm 
-------------------------
inputs: int[n][n] cityDistances // distancat mes qyteteve te ndryshme
output: int[n] path             // renditja optimale e qyteteve

pathCount  = factorial(n-1);
minDist    = -1;
minPathInx = -1;

// generate all possible paths 
for (int i=0; i

Disa sqarime:
1) matrica cityDistances eshte e dhena e problemit. per cdo dy qytete m dhe n, hyrja cityDistances[m,n] ne matrice ruan distancen mes tyre. Nenkuptohet qe qyteti fillestar i korrespondon indeksit 0 ne kete matrice.
2) Zgjidhja me e thjeshte por me pak eficente e problemit eshte qe te provosh te gjitha rruget e ndryshme me rradhe, dhe te ruash rrugen me kosto/distance me te shkurter. Normalisht per n qytete jane (n-1)! rruge te ndryshme. Supozohet qe cdo dy qytete jane te lidhura me nje rruge. Variante me te ngaterruar te problemit ekzistojne kur per dy qytete specifike mund te mos kete rruge mes tyre. Ne kete rast distance mes tyre ne grafik shenohet si infinit dhe ne matrice mund te paraqitet si -1, cka duhet marre marasysh me pas ne funksionin qe llogarit distancen.
3) Qarku (loop) i algoritmes rrotullohet (n-1)! here qe te provoje cdo rruge te mundshme, ku cdo rruge ne fakt i korrespondon nje permutacioni te numrave nga 0,1,2,... n-1. Procedura decodePath duhet te ktheje rrugen/permutacionin e rradhes, mbase sipas rendit leksikografik, qe nenkuptohet qe duhet te filloje me 0 (qyteti fillestar). Psh per 4 qytete (pra te shenuara si 0,1,2,3) do kishim gjithsej 3! rruge te ndryshme: 0 - 0123, 1 - 0132, 2 - 0213, 3 - 0231, 4 - 0312, 5 - 0321. Metoda ne fjale duhet te ktheje rrugen 0231 per indeksin 3 e keshtu me rradhe. Mund te perdoren rradhitje te tjera apo qarqa (loop) te tjera, e rendesishme eshte qe ti shterroje te gjithe rruget e mundshme
4) Problemi ne fjale ben pjese tek klasa e problemeve zgjidhja e te cilave behet gjithmone e me e gjate (ne fakt ne rend eksponencial) per vlera relativisht mesatare te problemit dhe per te cilat dyshohet qe nje zgjidhje polinomale nuk ekziston. Psh per 100 qytete duhet te kontrollohen 100! ~ 10 ne fuqi te 158 rruge te ndryshme.

[pikachu]

Dr Rieux faleminderit per pergjigjen