Trong bài trước chúng ta đã tìm hiểu về thuật toán quay lui trong bài toán liệt kê. Nếu chúng ta thay đổi bài toán thành tìm ra một nghiệm thoả mãn một số điều kiện nào đó, và nghiệm đó là tốt nhất theo một tiêu chí cụ thể. Thì bài toán sẽ trở thành bài toán tối ưu.

Chúng ta có thể sử dụng thuật toán quay lui trong bài toán liệt kê để tìm ra lời giải bằng cách liệt kê ra tất cả các cấu hình có thể và đánh giá, tìm ra cấu hình tốt nhất. Nhưng nếu xét hết tất cả các cấu hình thì sẽ mất rất nhiều thời gian và có thể lãng phí. Nếu chúng ta có thể đánh giá tại mỗi bước của thuật toán quay lui, khi đi tiếp bước tiếp theo không mang lại kết quả tốt hơn so với cấu hình tốt nhất hiện tại. Chúng ta có thể loại bỏ sớm phương án đó. Kỹ thuật này gọi là kỹ thật đánh giá nhánh cận trong tiến trình quay lui. Mô hình của thuật toán nhánh cận có thể mô tả như sau:

<khởi tạo một cấu hình bất kỳ cho BESTCONFIG>
void function Attemp(i) {
    for <mọi giá trị V có thể gán cho x[i]> {
        <thử x[i] := V>;
        if <việc thử trên vẫn còn hi vọng tìm ra cấu hình tốt hơn BESTCONFIG> {
            if <x[i] là phần tử cuối cùng trong cấu hình> {
                <cập nhật BESTCONFIG>
            } else {
                <ghi nhận việc thử x[i] = V (nếu cần)>;
                Attemp(i + 1);
                <bỏ ghi nhận việc thử x[i] := V (nếu cần)>;
            }
        }
    }
}

Chúng ta cùng xem bài toán người du lịch Cho n thành phố đánh số từ 1 đến n và m tuyến đường giao thông hai chiều giữa chúng, mạng lưới giao thông này được cho bởi bảng C cấp nxn, ở đây C[i, j] = C[j, i] = Chi phí đi đoạn đường trực tiếp từ thành phố i đến thành phố j. Giả thiết rằng C[i, i] = 0 với ∀i, C[i, j] = +∞ nếu không có đường trực tiếp từ thành phố i đến thành phố j.

Một người du lịch xuất phát từ thành phố 1, muốn đi thăm tất cả các thành phố còn lại mỗi thành phố đúng 1 lần và cuối cùng quay lại thành phố 1. Hãy chỉ ra cho người đó hành trình với chi phí ít nhất. Bài toán đó gọi là bài toán người du lịch hay bài toán hành trình của một thương gia (Traveling Salesman).

Hãy cùng xem cách cài đặt thuật toán bằng C++ trong đoạn chương trình dưới đây.

#include <iostream>

using namespace std;

#define N 4
void initialize();
void attemp(int i);
void print();

int n = N;  // number of vertices
int m = 6;  // number of edges
int maxE = 1000;
int maxC = 100 * maxE;
int C[N][N] = {
    {0, 3, 2, 1},
    {3, 0, 1, 2},
    {2, 1, 0, 4},
    {1, 2, 4, 0}
};
int X[N];   // store all possible ways
int BestWay[N]; // store best way
int T[N];   // store cost from x[0] to X[i]
int Free[N];    // Free[i] = True if not visit i
int BestConfig = maxC;  // best cost

int main() {
    // starting from 0 for easily manipulate with arrays
    initialize();
    attemp(1);
    print();
}

void initialize() {
    for (int i = 0; i < n; i ++) {
        Free[i] = true;
        BestWay[i] = 0;
        X[i] = 0;
        T[i] = 0;
    }
    Free[0] = false;    // start from vertice 0
    BestConfig = maxC;
}

void attemp(int i) {
    for (int j = 1; j < n; j ++) {
        if (Free[j]) {
            X[i] = j;
            T[i] = T[i - 1] + C[X[i - 1]][j];
            if (T[i] < BestConfig) {
                if (i < n - 1) {
                    Free[j] = false;
                    attemp(i + 1);
                    Free[j] = true;
                } else {
                    if (T[i] + C[X[i]][0] < BestConfig) {
                        for (int k = 0; k < n; k ++) {
                            BestWay[k] = X[k];
                        }
                        BestConfig = T[i] + C[X[i]][0];
                    }
                }
            }
        }
    }
}

void print() {
    cout << "Path: ";
    for (int i = 0; i < n; i ++) {
        cout << BestWay[i] + 1 << " -> ";
    }
    cout << 1 << endl;
    cout << "Cost: " << BestConfig << endl;
}

Kết quả sau khi chạy chương trình.

Path: 1 -> 3 -> 2 -> 4 -> 1
Cost: 6