近鄰法

Question

根據頁面

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

這是他java實現

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(); 

    } 

} 

我的問題是關於這一部分

 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; 
       } 
      } 
     } 

爲什麼這部分重要的是什麼它確實..我的意思是，因爲我們輸入值手冊爲什麼他檢查0和1s的候補地點..它總讓我困惑 感謝anyhelp我可能會得到...... :)

Answer 1

看起來像這個算法的基礎上的圖，只解決了無方向圖的問題。

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 
      } 

看到：https://en.wikipedia.org/wiki/Adjacency_matrix更好的例子;）