Kỹ thuật đệ quy và nhánh cận

1. Bài toán TAXI

Đề bài: Có n hành khách 1, 2, ..., n và một chiếc taxi. Hành khách i muốn di chuyển từ điểm i đến điểm i + n (i = 1, 2, .., n). Cho ma trận khoảng cách c[2n+1] [2n+1] với c(i, j) là khoảng cách từ điểm i đến điểm j (i, j = 0, 1, .., 2n). Hãy xác định độ dài đường đi ngắn nhất mà taxi đang đỗ ở điểm 0 sẽ phải đi để có thể phục vụ cả n hành khách này, rồi cuối cùng quay trở lại điểm xuất phát 0, sao cho tại bất kể thời điểm nào luôn chỉ có ≤ 1 hành khách trên taxi và không có điểm nào bị đi qua nhiều hơn 1 lần (ngoại trừ điểm 0 là điểm xuất phát ban đầu của taxi).

• Input:
  • Dòng 1 chứa n(1 ≤ n ≤ 11)
  • Dòng i + 1 (i = 1, ..., 2n, 2n+1) chứa dòng thứ i của ma trận c[2n+1][2n+1]
•  Output:
  • Độ dài đường đi ngắn nhất của taxi

 Example:

Input
2
0 8 5 1 10
5 0 9 3 5
6 6 0 8 2
2 6 3 0 7
2 5 3 4 0
Output
17

Bàn luận:

• Do có n hành khách mà hành khách thứ i (1 ≤ i ≤ n) đi từ i đến i + n và tại bất cứ thời điểm nào luôn chỉ có ≤ 1 hành khách trên taxi và không có điểm nào đi qua nhiều hơn 1 lần (trừ điểm 0) nên bài toán sẽ giống với bài toán STP (người du lịch).
• Cách đi là hoán vị của n hành khách từ 1 đến n. Quá trình đi được biểu diễn dưới dạng mảng x[n + 2] = 0, x1, x2, x3, ..., xn, 0 với xi = {1, 2, 3, ..., n} là cách chọn hành khách thứ i.
• Độ dài quãng đường phục vụ tới hành khách thứ k là:
  fk = (c[0][x1] + c[x1][x1 + n]) + (c[x1 + n][x2] + c[x2][x2 + n]) + ... + (c[x(k-1) + n][xk] + c[xk][xk + n])
• Cận dưới: gmin = f + (n - k + 1)*cmin với cmin là quảng đường ngắn nhất trong ma trận c .
• Xét thử với example ta thấy có 2 quá trình đi của taxi là: 
  • x = [0, 1, 2, 0], độ dài quãng đường là: f = (c[0][1] + c[1][3]) + (c[3][2] + c[2][4]) + c[4][0] = 8 + 3 + 3 + 2 + 2 = 18
  • x = [0, 2, 1, 0], độ dài quãng đường là: f = (c[0][2] + c[2][4]) + (c[4][1] + c[1][3]) + c[3][0] = 5 + 2 + 5 + 3 + 2 = 17

 Code:

#include<iostream>
using namespace std;

#define INFINITY 1e9

int n, cmin, f, fm, g;
int c[23][23], x[13];
bool visited[11];

void Try(int k) {
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			x[k] = i;
			f += c[x[k - 1] + n][i] + c[i][i + n];
			visited[i] = true;
			if (k == n) {
				if (f + c[i + n][0] < fm)
				{
					fm = f + c[i + n][0];
					/*for (int i = 0; i <= n + 1; i++)
						cout << x[i] << " ";
					cout << endl;*/
				}
			}
			else {
				g = f + (n - k + 1)*cmin;
				if (g < fm)
					Try(k + 1);
			}
			f -= c[x[k - 1] + n][i] + c[i][i + n];
			visited[i] = false;
		}
	}
}

void BranchAndBound() {
	x[0] = n * -1;
	f = 0, fm = INFINITY;
	Try(1);
	x[n + 1] = 0;

	cout << fm;
}

int main() {
	cin >> n;

	cmin = INFINITY;
	for (int i = 0; i < 2 * n + 1; i++)
		for (int j = 0; j < 2 * n + 1; j++)
		{
			cin >> c[i][j];
			if (i != j && c[i][j] < cmin)
				cmin = c[i][j];
		}

	BranchAndBound();

	return 0;
}

Đang cập nhật ...