Problème du Voyageur de Commerce : méthode du plus proche voisin

**williamdunord** · 09/04/2007, 21h09

salut à tous,
j'ai besoin pour mes cours de créer en pascal un programme de résolution du Problème du Voyageur de Commerce... je souhaite réaliser un programme simple utilisant la méthode du plus proche voisin...
je pensais réaliser le programme à l'aide de 4 procédures : une pour entrer les distances entre les villes, une qui partant du point i chercher le plus proche voisin, une qui calcule la distance totale du parcours en enfin une qui m'affiche les villes par lesquelles passer dans l'ordre (je ne recherche pas à faire un graphe, seulement à sortir à la fin les villes dans l'ordre et la distance totale parcourue)...
voici ce que j'ai commencé à écrire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
program PVC;
const n=5;   {nombre de villes}
type matrice=array[1..n,1..n] of integer;
     tablo=array[1..n] of integer;
 
procedure dist(var a : matrice);  {entr‚e des distances}
var i,j,x:integer;
begin
  for i:=1 to n do
  for j:=1 to n do begin    {ici, petit souci : le programme va
  demander a[i,j] et a[j,i] alors que a[i,j]=a[j,i]... comment y rem‚dier ?
  de plus le programme demande aussi a[i,j] pour i=j alors que dans ce cas
  la valeur est 0... peut-on faire une boucle avec j<>i ??}
  write('a[',i,',',j,']= '); readln(x);
  a[i,j]:=x; end;
end;
 
procedure mini(var min, pass :tablo; a:matrice);
var s,i,j,p,k,jmin:integer;
begin
  s:=0;              {s contiendra la longueur du parcours}
  for p:=1 to n-1 do
  begin
      j:=1; while a[i,j]=0 do j:=j+1;
      min[p]:=a[i,j]; jmin:=j;
      for k:=j+1 to n do   {n ou n-1 ?!}
          if (a[i,k]<>0) and (a[i,k]<min[i]) then
          begin
            min[p]:=a[i,k];
            jmin:=k;
          end;
      pass[p]:=jmin;
      a[i,jmin]:=0; a[jmin,i]:=0;
      i:=jmin;
      writeln(pass[p]);    {affichage de la solution}
      s:=s+min[p];         {affichage de la longueur du parcours}
  end;
end;
 
 
 
var a:matrice;
    min,pass:tablo;
begin
  dist(a);
  mini(min,pass,a);
  readln;
end.

j'ai testé le programme mais il ne m'affiche pas la solution

au vu de mes différents commentaires entre {}, quelqu'un pourrait-il m'aider svp ?

merci !

**amtdev** · 11/04/2007, 20h28

Bonjour,
Sans utiliser de procédures, je vous propose ma version qui peut, bien sûr, être améliorée. Mais je pense qu'elle répond à vos attentes. J'ai insérer des commentaires pour être claire et je reste à votre disposition pour plus d'explications. Bonne continuation.