Nächster-Nachbar-Algorithmus

Question

nach der Seite .. http://www.sanfoundry.com/java-program-implement-traveling-salesman-problem-using-nearest-neighbour-algorithm/

das ist seine Java-Implementierung

import java.util.InputMismatchException; 

import java.util.Scanner; 

import java.util.Stack; 



public class TSPNearestNeighbour 

{ 

    private int numberOfNodes; 

    private Stack<Integer> stack; 



    public TSPNearestNeighbour() 

    { 

     stack = new Stack<Integer>(); 

    } 



    public void tsp(int adjacencyMatrix[][]) 

    { 

     numberOfNodes = adjacencyMatrix[1].length - 1; 

     int[] visited = new int[numberOfNodes + 1]; 

     visited[1] = 1; 

     stack.push(1); 

     int element, dst = 0, i; 

     int min = Integer.MAX_VALUE; 

     boolean minFlag = false; 

     System.out.print(1 + "\t"); 



     while (!stack.isEmpty()) 

     { 

      element = stack.peek(); 

      i = 1; 

      min = Integer.MAX_VALUE; 

      while (i <= numberOfNodes) 

      { 

       if (adjacencyMatrix[element][i] > 1 && visited[i] == 0) 

       { 

        if (min > adjacencyMatrix[element][i]) 

        { 

         min = adjacencyMatrix[element][i]; 

         dst = i; 

         minFlag = true; 

        } 

       } 

       i++; 

      } 

      if (minFlag) 

      { 

       visited[dst] = 1; 

       stack.push(dst); 

       System.out.print(dst + "\t"); 

       minFlag = false; 

       continue; 

      } 

      stack.pop(); 

     } 

    } 



    public static void main(String... arg) 

    { 

     int number_of_nodes; 

     Scanner scanner = null; 

     try 

     { 

      System.out.println("Enter the number of nodes in the graph"); 

      scanner = new Scanner(System.in); 

      number_of_nodes = scanner.nextInt(); 

      int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1]; 

      System.out.println("Enter the adjacency matrix"); 

      for (int i = 1; i <= number_of_nodes; i++) 

      { 

       for (int j = 1; j <= number_of_nodes; j++) 

       { 

        adjacency_matrix[i][j] = scanner.nextInt(); 

       } 

      } 

      for (int i = 1; i <= number_of_nodes; i++) 

      { 

       for (int j = 1; j <= number_of_nodes; j++) 

       { 

        if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0) 

        { 

         adjacency_matrix[j][i] = 1; 

        } 

       } 

      } 

      System.out.println("the citys are visited as follows"); 

      TSPNearestNeighbour tspNearestNeighbour = new TSPNearestNeighbour(); 

      tspNearestNeighbour.tsp(adjacency_matrix); 

     } catch (InputMismatchException inputMismatch) 

     { 

      System.out.println("Wrong Input format"); 

     } 

     scanner.close(); 

    } 

} 

meine Frage ist, diesen Teil

 for (int i = 1; i <= number_of_nodes; i++) 

     { 

      for (int j = 1; j <= number_of_nodes; j++) 

      { 
       if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0) 

       { 
        adjacency_matrix[j][i] = 1; 
       } 
      } 
     } 

warum tut dies Teil wichtig ist und was es tut .. ich meine, da wir die Werte manuell eingeben, warum er die alternativen Plätze für 0s und 1s überprüft .. es ist total verwirrend zu mir danke für anyhelp ich könnte bekommen ... :)

Answer 1

Es scheint wie das Diagramm, auf dem dieser Algorithmus basiert, löst das Problem nur für ungerichtete Graphen.

if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0) 
      // For Example: 
      //   Boston Washington 
      //Boston  1  0 
      //Washington 1  1 
      // Meaning you can Travel from Washington to Boton but not vice 
      // versa 
      { 
       //THEN DO 
       adjacency_matrix[j][i] = 1; 
      //   Boston Washington 
      //Boston  1  1<--- 
      //Washington 1  1 
      } 

siehe: https://en.wikipedia.org/wiki/Adjacency_matrix für bessere Beispiele;)