TS. Traveling Salesman - JulTob/Mathematics GitHub Wiki

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure Traveling_Salesman is

   -- 1. Define the Set of Cities
   type City is (Madrid, Paris, Berlin, London, Rome, Athens);
   subtype City_Index is City;

   -- 2. Define "Infinity" for Unreachable Paths
   Infinity : constant Integer := 10_000;
      -- A large number representing "unreachable"


   -- 3. Define the Distance Matrix (Graph Representation)
   type Distance_Matrix_Type is array (City_Index, City_Index) of Integer;
   Distance_Matrix : Distance_Matrix_Type :=
     ((  Infinity, 120, Infinity, 150, 150, Infinity),  -- Madrid
      (120,   Infinity,  90,  75, 120, Infinity),      -- Paris
      (Infinity,  90,  Infinity,  90, 120, 150),      -- Berlin
      (150,  75,  90,   Infinity, 150, Infinity),      -- London
      (150, 120, 120, 150,   Infinity, 120),           -- Rome
      (Infinity, Infinity, 150, Infinity, 120,  Infinity)); -- Athens

   -- 4. Define a Structure to Track a Path and Its Cost
   type Path_Array is array (1 .. City'Pos(Athens) + 1) of City;
   type Tour is record
      Current_City : City;
      Cost_So_Far : Integer;
      Path : Path_Array;
      Depth : Integer;  -- Number of cities visited
   end record;

   -- 5. Store the Best Tour Found
   Best_Cost : Integer := Infinity;
   Best_Path : Path_Array;

   -- 6. Procedure to Print a Matrix (for visualization)
   procedure Print_Matrix(Matrix : Distance_Matrix_Type; Title : String) is
   begin
      Put_Line(Title);
      for C in City loop
         for D in City loop
            if Matrix(C, D) = Infinity then
               Put(" INF "); -- No direct path
            else
               Put(Integer'Image(Matrix(C, D)) & " ");
            end if;
         end loop;
         New_Line;
      end loop;
      New_Line;
   end Print_Matrix;

   -- 7. Function to Find the Shortest Hamiltonian Cycle (Recursive Search)
   type Visited_Set is array (City) of Boolean;

   procedure Find_Shortest_Cycle(Current_Tour : in Tour; Visited : in out Visited_Set) is
   begin
      -- If all cities have been visited, return to Madrid
      if Current_Tour.Depth = City'Pos(Athens) then
         declare
            Final_Cost : Integer := Current_Tour.Cost_So_Far + Distance_Matrix(Current_Tour.Current_City, Madrid);
         begin
            if Final_Cost < Best_Cost then
               Best_Cost := Final_Cost;
               Best_Path := Current_Tour.Path;
               Best_Path(Current_Tour.Depth + 1) := Madrid; -- Completing the cycle
            end if;
         end;
         return;
      end if;

      -- If the current cost exceeds the best known solution, prune this path
      if Current_Tour.Cost_So_Far >= Best_Cost then
         return;
      end if;

      -- Try visiting each unvisited city
      for Next in City loop
         if not Visited(Next) and then Distance_Matrix(Current_Tour.Current_City, Next) < Infinity then
            declare
               Next_Tour : Tour;
            begin
               -- Move to the next city
               Next_Tour.Current_City := Next;
               Next_Tour.Cost_So_Far := Current_Tour.Cost_So_Far + Distance_Matrix(Current_Tour.Current_City, Next);
               Next_Tour.Path := Current_Tour.Path;
               Next_Tour.Path(Current_Tour.Depth + 1) := Next;
               Next_Tour.Depth := Current_Tour.Depth + 1;

               -- Mark as visited
               Visited(Next) := True;
               Find_Shortest_Cycle(Next_Tour, Visited);
               Visited(Next) := False; -- Unmark for other possibilities
            end;
         end if;
      end loop;
   end Find_Shortest_Cycle;

   -- 8. Main Execution: Solve the TSP Problem
begin
   -- Step 1: Print Initial Distance Matrix
   Print_Matrix(Distance_Matrix, "Initial Distance Matrix (Direct Flights Only):");

   -- Step 2: Apply Floyd-Warshall Algorithm to Compute Shortest Paths Between Cities
   for Via in City loop
      for From in City loop
         for To in City loop
            if (Distance_Matrix(From, Via) /= Infinity and Distance_Matrix(Via, To) /= Infinity) then
               if Distance_Matrix(From, Via) + Distance_Matrix(Via, To) < Distance_Matrix(From, To) then
                  Distance_Matrix(From, To) := Distance_Matrix(From, Via) + Distance_Matrix(Via, To);
               end if;
            end if;
         end loop;
      end loop;
   end loop;

   -- Step 3: Print Final Distance Matrix After Shortest Path Computation
   Print_Matrix(Distance_Matrix, "Final Distance Matrix (All-Pairs Shortest Paths):");

   -- Step 4: Solve TSP from Madrid Using Recursive Pruning
   declare
      Start_Tour : Tour;
      Visited : Visited_Set := (others => False);
   begin
      Start_Tour.Current_City := Madrid;
      Start_Tour.Cost_So_Far := 0;
      Start_Tour.Path := (others => Madrid);  -- Initialize path
      Start_Tour.Path(1) := Madrid;
      Start_Tour.Depth := 1;
      Visited(Madrid) := True;

      Find_Shortest_Cycle(Start_Tour, Visited);
   end;

   -- Step 5: Output the Result in Hours and Minutes
   Put_Line("Minimum travel time for the optimal round-trip: " &
            Integer'Image(Best_Cost / 60) & " hours " &
            Integer'Image(Best_Cost mod 60) & " minutes");

   -- Step 6: Print the Optimal Path Taken
   Put_Line("Optimal route: ");
   for I in 1 .. City'Pos(Athens) + 1 loop
      Put(City'Image(Best_Path(I)) & " → ");
   end loop;
   Put_Line("");
end Traveling_Salesman;