Trumpiausias kelias grafe

Laboratorinio darbo Nr.4 ataskaita Diskrečiosios struktūros Trumpiausias kelias grafe Atliko: IF2 studentė Darbo tikslas: Susipažinti su sunkumais, iškylančiais sprendžiant pilno perrinkimo (pilnosios NP sudėtingumo klasės) uždavinius.  Darbo užduotis: Sudarykite programą, sprendžiančią kurį nors pilnosios NP sudėtingumo klasės uždavinį. Apskaičiuoti pasirinktojo algoritmo vykdymo laiką. Pasirenkam Hamiltono ciklo uždavinį. Užduoties sprendimo rezultatai ir pastebėjimai: Kadangi mes pasirinkame Hamiltono ciklo uždavinį, mums reikia neorientuotame grafe rasti ciklą, kuris per visas viršūnes praeitų lygiai vieną kartą. Tokių atvejų pradiniai duomenys turi būti surašyti tekstiniame faile, gretutines matricos formatų. Iš pradžios nubraižykim pasirinkta grafą: Sudarome pradinių duomenų failą. Pastaba: Gretimumo matricoje, kuri sudaryta iš penkių stulpelių ir penkių eilučių(grafo penkios viršūnės), parodo kokios viršūnės yra gretimos viena kitai: tos viršūnės, ties kuriomis yra vienetukas, yra gretimos, o ties kuriomis yra nuliukas – ne.. Programos sudėtingumą galima įvertinti pagal uždavinio atlikimo laiką. Žinoma, kiekvienam kompiuteriui, turinčiam skirtingus resursus algoritmo atlikimo laikas skirsis. Žemiau pateiktas atliktas keliuose kompiuteriuose uždavinio sprendimo laikas: Šio metodo esmė yra labai paprasta: jei paieškos metu viršūnė u tampa išsemta, tai pamirštame, kad šioje viršūnėje buvome, t.y. viršūnė u tampa nauja. Tarkime, kad grafas G=(V,U) yra jungusis ir nusakytas masyvais L ir lst. Paiešką pradėsime iš 1-osios viršūnės(nors šio atvejų tai neturi jokios reikšmes, nuo kokios viršūnės prasidedame paieška, nes mes nagrinėjame ciklą). Paieškos metu aplankytas viršūnes talpinsime į masyvą X[1..n+1]. Kitaip tariant, masyvo X elementai apibrėš aplankytųjų viršūnių maršrutą. Jei paieškos metu masyve X yra n elementų, ir iš viršūnės Xn atėjome į 1-ąją viršūnę, tai reiškia, kad radome Hamiltono ciklą. Tokių atveju mes gauname tokius rezultatus: Programos tekstas: unit Paieska_grafuose; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ExtCtrls, jpeg; type TForm1 = class(TForm) Label2: TLabel; Memo1: TMemo; Button1: TButton; Image1: TImage; Button2: TButton; Button3: TButton; Edit1: TEdit; procedure FormCreate(Sender: TObject); procedure Button1Click(Sender: TObject); procedure Button2Click(Sender: TObject); procedure Button3Click(Sender: TObject); private public end; const c = 500; type mas = array[1..c] of integer; matr = array[1..c,1..c] of integer; var Form1: TForm1; x, fst, prec: mas; n,m:integer; L, lst : mas; alfa : boolean; implementation {$R *.dfm} procedure TForm1.FormCreate(Sender: TObject); begin Edit1.Clear; Memo1.Clear; Memo1.ScrollBars := ssVertical; Image1.Visible := false; Button3.Enabled:=false; end; //duomanu ivedimas procedure TForm1.Button1Click(Sender: TObject); var failas: string; F: TextFile; h, i, j, s : integer; gret : matr; begin failas := Edit1.Text; Image1.Visible := true; Button3.Enabled:=true; n := 1; AssignFile (F, Failas); //Atidarome faila Reset (F); //Paruosiame faila skaitymui //skaiciuojame eilutes while not Eof (F) do begin //Perkeliam zymekli faile i sekanti eilute readln (F); n := n + 1; end; n:=n-1; CloseFile (F); //uzdarom faila AssignFile (F, Failas); Reset (F); //ivedimas for i:=1 to n do begin for j:=1 to n do begin read (F, gret[i,j]); end; readln (F); end; CloseFile (F); h := 1;//eina per L s := 1;//eina per lst lst[s]:=0; s:=s+1; for i:=1 to n do begin for j:=1 to n do begin if gret[i][j]=1 then begin L[h]:=j; h:=h+1; end; end; lst[s]:=h-1;//adresas i L, kur prasideda kitos virsunes gretimos s:=s+1; end; end; //isejimas procedure TForm1.Button2Click(Sender: TObject); begin Halt; end; //hamiltono ciklo paieska procedure TForm1.Button3Click(Sender: TObject); var i, k, ciklas, aga, vot, u, v, j : integer; laikas, start, stop: TDateTime; Hour, Mi, Sec, MSec: Word; t,p, rastas : boolean; fst, prec : mas; paras_ema : string; begin //matojam laika start:=now(); //papildomas ciklas, programos vykdimo laiko pailginimui for aga:=0 to 10000 do for vot:=0 to 100000 do ciklas := ciklas * 2; rastas:=false; alfa:=false; v:=1; for i:=1 to n do begin fst[i]:= lst[i]+1; prec[i]:=0; end; k:=v; if fst[k]

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!