java - 最近邻算法

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

为什么这部分很重要以及它的作用..我的意思是既然我们进入了值(value)观手册，为什么他要检查0和1的替代位置..这让我很困惑感谢我可能得到的任何帮助...:)

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以获得更好的例子;)