Algoritmi in podatkovne strukture 1

Problem: 

Denimo, da je n mest povezanih med seboj s poleti po principu vsak z vsakim. Iz prvega mesta želimo obiskati vsa ostala mesta tako, da nobenega mesta ne obiščemo več kot enkrat (pri tem je vseeno, v katerem mestu končamo). Dolžine poletov med posameznimi mesti so znane, iščemo pa najkrajšo pot (skupno dolžino poletov) iz prvega mesta, ki obišče vsa ostala mesta.

a) Definirajte konkretno nalogo velikosti 5 in jo ustrezno predstavite z modelom.

b) Napišite prevdokodo za nek algritem, ki rešuje ta problem. Zamislite si svoj, lahko tudi zelo neoptimalen algoritem. Bistvena je primerna predstavitev algoritma s psevdokodo.

c) Napišite sled uporabe vašega algoritma za reševanje naloge a). Ker je popolna predstavitev sledi za to nalogo veliko preobsežna, predstavite le nekaj ponovitev izvedbe in nakažite izbiro ustreznega končnega rezultata!