Tags:
java
Hej! er der nogen der ved hvordan denne her algoritme fungere!
Bare en lille forklaring med ord!
(det lille e mellem v og V er tilhør)
enum(A: Seq of By, V: Set of By)
begin
**if V = Ø then
*****print(A)
**else
****for v e V
*******enum(A -> [v] , V\\{v})
****end-for
**end-if
end
1 svar postet i denne tråd vises herunder
1 indlæg har modtaget i alt 4 karma
Det ligner mere pseudo-kode end java.
Det er en rekursiv algoritme der finder samtlige ruter gennem byerne angivet i V.
A indeholder den foreløbige rute og V indeholder de byer der endnu ikke er besøgt. Der er et rekursivt kald for hver by i V, hvor byen sættes i enden af A. Når V er tom, indeholder A en hel rute og printes.
Eftersom turen 1-3-6-5-4-2 er den samme som 6-5-4-2-1-3 kan man uden tab af generalitet antage at by 1 er start byen. Så den kan man smide over i A inden kaldet til enum.
Algoritmen tager så tid O((n-1)!) og optager plads der er O(n).