Prezentare La

Informatica

Problema

Comis Voiajorului

Kukta Robertcl. a XI-a B

Enuntul Problemei

Un comis voiajor trebuie sa viziteze un numar n de orase. Initial se afla intr-una din ele. Acel oras este notat cu 1. Comis voiajorul doreste sa nu treaca de doua ori prin acelasi oras, iar la intoarcere sa revina in orasul 1. Cunoscand legaturile se cere sa se tipareasca toate

drumurile posibile pe care le poate efectua comisul voiajor

Algoritmul de rezolvare

- problema se rezorva prin metoda BACKTRACKING - pentru rezolvare se utilizeaza o stiva notata cu st - la nivelul 1 se gaseste numarul 1 Algoritmul continua pana cand se ajunge din nou la nivelul 1 caz in care algoritmul se incheie.

Observatii

Un succesor intre 2 si n aflat pe nivelul k este considerat valid daca:- Nu s-a mai trecut prin orasul simbolizat, deci nu se gaseste in stiva;

- Exista drum intre orasul aflat pe nivelul k-1 si orasul aflat pe nivelul k;- Cand stiva ajunge la nivelul k=n si sa existe drum de la orasul acesta la orasul 1

Exemplu Pentru n=6 Ai,j va fi: - 1 daca intre i si j se afla drum - 0 daca intre i si j nu se afla drum Si se va afisa in program:

1.2 Drumurile posibile sunt 2.3 12345612.5 12543612.6 16543212.1 16345213.43.53.63.24.54.35.65.25.35.4

program comis_voiajor;type stiva=array[1..100] of integer;

type mat= array[1..100,1..100] of integer;var st:stiva; a:mat;

as,ev:Boolean; n,k,i:integer;

Procedure init (k:integer;var st:stiva);Begin

St[k]:=1;End;

Procedure successor (var as:Boolean; var st:stiva;k:integer);Begin If st[k]<n then begin

As:=true;St[k]:=st[k]+1;

End Else as:=false;

End;Procedure valid(var ev:Boolean; st:stiva; k:integer);

Var i:integer;Begin

Ev := true;For i:=1 to k-1 do

If a[st[k-1],st[k]]=0 then ev:=false Else

For i:=1 to k-1 do If st[i]=st[k] then ev := false

Else If (k=n) and (a[1,st[k]]=0) then ev := false;

End;function solutie (k:integer):Boolean;

beginsolutie:=(k=n);

end;procedure tipar;

var i:integer;begin

for i:=1 to n do write( st[i]);end;

BEGINwrite(‘n=’);readln(n);for i:=1 to n do

for j:=1 to i-1 do begin write (‘a[‘,I,’,’,j,’]=’);readln(a[I,j]);

a[j,i]:=a[I,j];end;

st[1]:=1;k:=2;init(k,st);while k>1 do begin

repeatsuccessor (as,st,k);

if as then valid(ev,st,k);Until (not as) OR (as AND ev);If as then

If solutie(k) then tiparElse begin

K:=k+1;Init(k,st);End

Else k:=k+1;End;END.