Voyages Code vendeur ne fonctionne pas (Java)

Question

Voyages code vendeur en java ci-dessous (donne un résultat erroné)

http://www.sanfoundry.com/java-program-solve-travelling-salesman-problem-unweighted-graph/

package com.hinguapps.graph; 

import java.util.InputMismatchException; 
import java.util.Scanner; 

public class TSP { 
    private int numberOfNodes; 
    private Stack <Integer> stack; 

    public TSP() { 
     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 cities are visited as follows: "); 
      TSP tspNearestNeighbour = new TSP(); 
      tspNearestNeighbour.tsp(adjacency_matrix); 
     } catch (InputMismatchException inputMismatch) { 
      System.out.println("Wrong Input format"); 
     } 
     scanner.close(); 
    } 
} 

Matrice devrait être:

0 10 5 40 
2 0 5 1 
6 13 0 12 
1 8 9 0 

Résultat attendu: 1 3 2 4 1
Résultat du code: 1 3 4 2 1

Answer 1

Cette implémentation est erronée. C'est un problème difficile, car vous devez soit toucher chaque chemin, soit au moins CONSIDERER chaque chemin. Cette implémentation se résume essentiellement à "Chaque étape, déplacez-vous au nœud le plus proche que je n'ai pas visité". Puisque la pile ne garde pas la mémoire de l'endroit où vous avez été, elle ne revient pas en arrière pour considérer qu'un meilleur chemin a pu exister sur l'une des routes les plus longues.

Pour résoudre ce problème, l'algorithme doit conserver le chemin en mémoire et ne pas commencer à imprimer la solution tant que la meilleure solution n'a pas été trouvée. (Peut utiliser la récursivité, une pile qui contient tout le chemin, ou une autre méthode.)