Cài đặt code bài toán người du lịch bằng C++ và Java

Bạn đã bao giờ ngẫm nghĩ về việc xếp lịch trình du lịch để tham quan nhiều thành phố một cách hiệu quả nhất chưa? Bài toán người du lịch sẽ giúp bạn tìm ra hành trình ngắn nhất để đi qua tất cả các thành phố mà chỉ đi qua mỗi thành phố duy nhất một lần.

Bài toán người du lịch

Một người du lịch muốn đi tham quan n thành phố T1, T2,…, Tn. Người du lịch xuất phát từ một thành phố nào đó và muốn đi qua tất cả các thành phố còn lại, mỗi thành phố chỉ được đi qua duy nhất 1 lần và quay lại thành phố xuất phát. Bài toán đặt ra là tìm một hành trình sao cho tổng chi phí là nhỏ nhất.

Code bài toán người du lịch

Chúng ta sẽ sử dụng một ma trận để lưu trữ chi phí đi từ thành phố Ti đến Tj, gọi là Cij. Giá trị của Cij là cost để đi từ thành phố Ti đến thành phố Tj. Đường chéo của ma trận sẽ có giá trị 0 vì không có chi phí để đi từ một thành phố đến chính nó. Dưới đây là một ví dụ về ma trận chi phí:

int graph[4][4] = {
  {0, 10, 15, 20},
  {10, 0, 35, 25},
  {15, 35, 0, 30},
  {20, 25, 30, 0}
};

Giả sử chúng ta có 4 thành phố: T0, T1, T2, T3. Hàng đầu tiên của ma trận sẽ biểu thị chi phí đi từ T0 đến T0, T1, T2, T3 lần lượt là 0, 10, 15, 20. Tương tự cho các hàng phía sau.

Hãy xem code mẫu sau để giải quyết bài toán người du lịch bằng C++:

#include <iostream>
using namespace std;

int cost = 999999;
int graph[4][4] = {
  {0, 10, 15, 20},
  {10, 0, 35, 25},
  {15, 35, 0, 30},
  {20, 25, 30, 0}
};

void swap(int *x, int *y) {
  int temp;
  temp = *x;
  *x = *y;
  *y = temp;
}

void copy_array(int *a, int n) {
  int i, sum = 0;
  for(i = 0; i <= n; i++) {
    sum += graph[a[i % 4]][a[(i + 1) % 4]];
  }
  if (cost > sum) {
    cost = sum;
  }
}

void permute(int *a, int i, int n) {
  int j, k;
  if (i == n) {
    copy_array(a, n);
  } else {
    for (j = i; j <= n; j++) {
      swap((a + i), (a + j));
      permute(a, i + 1, n);
      swap((a + i), (a + j));
    }
  }
}

int main() {
  int a[] = {0, 1, 2, 3};
  permute(a, 0, 3);
  cout << "Chi phí nhỏ nhất: " << cost << endl;
  return 0;
}

Lời giải tham khảo được lấy từ sanfoundry.com.

Đối với mã nguồn Java, bạn có thể sử dụng code sau để giải quyết bài toán người du lịch:

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 + " ");

    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 + " ");
        minFlag = false;
        continue;
      }
      stack.pop();
    }
  }

  public static void main(String... arg) {
    int number_of_nodes;
    Scanner scanner = null;

    try {
      System.out.println("Nhập số lượng thành phố trong đồ thị");
      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("Nhập ma trận kề");
      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("Các thành phố được đi qua theo thứ tự như sau:");
      TSPNearestNeighbour tspNearestNeighbour = new TSPNearestNeighbour();
      tspNearestNeighbour.tsp(adjacency_matrix);
    } catch (InputMismatchException inputMismatch) {
      System.out.println("Sai định dạng đầu vào");
    }

    scanner.close();
  }
}

Lời giải tham khảo được lấy từ sanfoundry.com.

Hãy thử áp dụng code này để tìm ra hành trình ngắn nhất cho chuyến đi của bạn!