蠻力算法解決Delphi中的TSP問題

Question

我正在爲一個擴展項目編寫一個程序來模擬旅行商問題。到目前爲止，我已經寫了它來允許用戶輸入路線，以及使用最近鄰居算法來「解決」路線。我現在正在試圖編寫一個蠻力算法來解決從3個城市到13/14左右的城市選擇問題。該計劃旨在說明城市數量的增加如何導致計算最短路線所需時間的指數/因子增加。我試圖寫一個遞歸函數，但無法讓我的頭瞭解它的工作原理。我迫切需要一些關於如何做到這一點的指導。任何幫助，將不勝感激。

Answer 1

由於Delphi版本沒有標籤，因此任何版本都適合使用TopicStarter。那麼我會基於XE2版本草稿。我也會假設每個城鎮只訪問過一次。我假設有一個道路網絡，而不是一架私人飛機，即在任何選定的城市A和B之間可能有直接路徑，或者可能不是（僅通過其他城市連接）。

type TCity = class 
    public 
     Name : string; 
     Routes : TList<TCity>; // available roads to/from this place 
     LeftFor : integer; // where did the merchant went next; -1 if did not arrived or left, used to iterate all the paths 

     CameFrom: TCity; // nil initially 
..... 
End; // writing this draft from phone (testing official StackOverflow Android app) would not write boilerplate with creating/free in internal objects - do it yourself 

Type TPath = TArray<TCity>; // for your app you would add segments and total cost and whatever 
Var World: TArray<TCity >; // fill cities and links yourself 
     AllPaths: TList<TPath>; // create yourself 
     Current: TList<TCity >; // create yourself 

    Procedure SaveResult; 
    Begin AllPaths.Add(Current.ToArray) end; 

    Function TryNextCity: boolean; 
    Var c1,c2: TCity; I : integer; 
    Begin 
     c1 := Current.Last; // where we are 
     While true do begin 
      Inc(c1.LeftFor) ; 
      If c1.LeftFor >= c1.Routes.Count // tried all ways? 
      Then Exit(false); 

      c2 := c1.Routes (. c1.LeftFor .); 
      if c2 = c1.CameFrom then continue; 
      if c2.LeftFor >= 0 then continue; // already were there 

      AddCity(c2); 
      Exit(True) ; 
     End; 
    End; 

    Procedure AddCity(const City: TCity) ; 
    Begin 
     Assert (not Current.Contains(City)) ; 
     If Current.Count = 0 
      then City.CameFrom := nil //starting point 
      else City.CameFrom := Current.Last; 
     City.LeftFor := -1; 
     Current.Add(City) ; 
End; 

    Procedure Withdraw; 
    Begin 
     Assert (Current.Count > 0); 
     With Current.Last do begin 
      CameFrom := nil; 
       LeftFor := -1; 
     End; 
     Current.Delete(Current.Count - 1) ; 
    End; 

    Procedure Recurs; 
    Var DeadEnd : boolean; 
    Begin 
      DeadEnd := true; 
      while TryNextCity() do begin 
       DeadEnd := false; 
       Recurs(); 
      end; 
      if DeadEnd then SaveResult(); 
      Withdraw(); 
     End; 

     Procedure RunBruteForce; 
     Var c: TCity ; 
     Begin 
      AllPaths.Clear; 
      For c in world do begin 
       Current.Clear; 
       AddCity(c); 
       Recurs(); 
      End; 
      End; 

PS。 @MartynA看起來像我現在無法在Android中評論我的答案。所以我的回答是：現在這個問題陷入了「做我的家庭作業」，「寫一本教科書或至少一篇散文」和「拋出一堆模糊的好主意，本身是正確的，但沒有一個會被詳細和完整地稱爲答案「。 我只開始嘗試新的SO應用程序的答案，只有繼續，因爲它沒有選項來刪除答案。