我正在实施旅行商优化问题，并且使用Java和C程序进行了编程。该程序将矩阵作为输入并显示最佳路径。
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(); } }
#include<stdio.h> #include<conio.h> int a[10][10],visited[10],n,cost=0; void get() { int i,j; printf("Enter No. of Cities: "); scanf("%d",&n); printf("\nEnter Cost Matrix\n"); for(i=0;i < n;i++) { printf("\nEnter Elements of Row # : %d\n",i+1); for( j=0;j < n;j++) scanf("%d",&a[i][j]); visited[i]=0; } printf("\n\nThe cost list is:\n\n"); for( i=0;i < n;i++) { printf("\n\n"); for(j=0;j < n;j++) printf("\t%d",a[i][j]); } } void mincost(int city) { int i,ncity; visited[city]=1; printf("%d -->",city+1); ncity=least(city); if(ncity==999) { ncity=0; printf("%d",ncity+1); cost+=a[city][ncity]; return; } mincost(ncity); } int least(int c) { int i,nc=999; int min=999,kmin; for(i=0;i < n;i++) { if((a[c][i]!=0)&&(visited[i]==0)) if(a[c][i] < min) { min=a[i][c]+a[c][i]; kmin=a[c][i]; nc=i; } } if(min!=999) cost+=kmin; return nc; } void put() { printf("\n\nMinimum cost:"); printf("%d",cost); } void main() { clrscr(); get(); printf("\n\nThe Path is:\n\n"); mincost(0); put(); getch(); }
这两个程序也运行良好。但是我想为此进行案例研究，我需要从网页上为这些矩阵输入信息。那么有没有办法做到这一点？对于Java或c，两者之一都可以。我也知道JSP和Web编程。我只想了解如何获取这些矩阵的输入并将其发送到服务器端。
对于Java，我使用了Jsp和Servlet。
Index.jsp
<body> <form action="sample" method="post"> <h1>Travelling Salesman Problem</h1> <input placeholder="Number of Cities" type="text" name="cities" required=""> <input placeholder="Matrix" type="text" name="matrix" required=""> <button>Submit</button> </form> </body>
Servlet Sample.java
import javax.servlet.ServletException; import javax.servlet.http.HttpServlet; import javax.servlet.http.HttpServletRequest; import javax.servlet.http.HttpServletResponse; import java.io.IOException; import java.io.PrintWriter; import java.util.InputMismatchException; import java.util.Scanner; import java.util.Stack; import static java.lang.System.out; public class sample extends HttpServlet { protected void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException { String city = request.getParameter("cities"); String numbers = request.getParameter("matrix"); int[] abc=new int[100]; String[] args = new String[2]; args[0] = city; args[1] = numbers; abc = TSPNearestNeighbour.main(args); //passing the two arguments to my java class PrintWriter out = response.getWriter(); for (int i=0;i<=abc.length;i++) { out.println(abc[i]); } } }
TSPNearestNeighbour.Java（Java类）
import java.util.InputMismatchException; import java.util.Stack; public class TSPNearestNeighbour { private int numberOfNodes; private Stack<Integer> stack; public TSPNearestNeighbour() { stack = new Stack<Integer>(); } public int[] tsp(int[][] adjacencyMatrix) { int[] arr= new int[100]; 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(); } return arr;// ignore this line,it's regarding my logic } public static int[] main (String[] args) { if (args.length < 2) { System.out.println("Two arguments required <city> <numbers>"); System.exit(-1); } int number_of_nodes; number_of_nodes = Integer.parseInt(args[0]); String[] splitText = args[1].split(" +"); int[] mat = new int[splitText.length]; for (int i = 0; i < splitText.length; i++) { mat[i] = Integer.parseInt(splitText[i]); // since we are passing the parameters to matrix,we convert every value from string type to integer } int[] abc = new int[100]; try { int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1]; int count = 0; for (int i = 1; i <= number_of_nodes; i++) { for (int j = 1; j <= number_of_nodes; j++) { if (count == mat.length) break; adjacency_matrix[i][j] = mat[(i - 1) * number_of_nodes + (j - 1)];//matrix input count++; } } 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(); abc = tspNearestNeighbour.tsp(adjacency_matrix); } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input format"); } return abc; } }
