トラベルセールスマンコードが動作しない（Java） - java、graph-algorithm

下記のjavaで巡回セールスマンコード（間違った結果を与える）

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

行列は以下のようになります。

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

予想される結果：1 3 2 4 1
コード結果：1 3 4 2 1

回答：

この実装は間違っています。 これは難しい問題です。なぜなら、すべてのパスに触れるか、少なくともすべてのパスを考慮する必要があるからです。この実装は基本的に「各ステップ、今までに訪れたことのない最も近いノードに移動する」ということになります。スタックは以前の場所のメモリを保持していないため、より良いパスが存在した可能性があります。長い道のり。

これを修正するために、アルゴリズムはパスを維持する必要があります。どういうわけかメモリに保存して、最良の解決策が実際に見つかるまで解決策の印刷を始めないでください。 （再帰、パス全体を保持するスタック、またはその他の方法を使用できます。）