Trong các giải thuật để giái chính xác cho bài toán người đi du lịch, đầu tiên phải kể đến thuật toán vét cạn. Vét cạn theo nghĩa thông thường là xét hết các trường hợp. Trong lập trình để giải quyết các bài toán tối ưu, vét cạn được sử dụng khi không còn phương pháp nào hiệu quả hơn để sử dụng được.Phương pháp vét cạn được mô tả để giải quyết bài toán người đi du lịch như sau duyệt tất cả các thành phố được nối với một thành phố đã được đánh dấu, tìm các tất cả các hành trình và chi phi tương ứng cho các hành trình, sau đó đánh giá các hành trình và tìm gia hành trình có chi phí thấp nhất làm kết quả cho bài toàn.Thuật toán vét cạn để giải quyết bài toán người đi du lịch sau khi xây dựng được ma trận chi phí sẽ giống như bài toán tìm tất cả các chu trình Hamilton trong đồ thị, sau đó so sánh các chu trình Hamilton và chọn một chu trình nhỏ nhất làm đáp án. Việc tìm chu trình Hamilton được thực hiện theo phương pháp duyệt theo chiều sâu và có kết hợp quay lui. Do quá trình duyệt có thể là rất sâu nên ta không sử dụng đệ quy mà dung stack để khử đệ quy. Sử dụng một biến Min để lưu thông tin lại tổng trọng số của chu trình Hamilton nhỏ nhất. ban đầu min=∞ hoặc min=m*trọng số của cạnh lớn nhất.(m là tổng số tất cả các đường đi đến các thành phố)Chu trình Hamiltoon là chu trình đi qua hết tất cả các đỉnh và sau đó quay về đỉnh xuất phát, do đó, chúng ta dung một danh sách Chuaxet[] để lưu lại các đỉnh chưa xét, một biến Sum để lưu lại trọng số của chu trình hiện thời, do chu trình Hamilton không quan trọng định xuất phát, ta chọn đỉnh xuất phát là đỉnh có chỉ số nhỏ nhất là 1.Quy trình duyệt như sau:
  1. Ban đầu đưa đỉnh 1 và 0 vào stack, Sum=0;
  2. Lặp lại quá trình sau: Lấy (Top) đỉnh từ stack ra và đỉnh I và trọng số ts, gán Chuaduyet[i] là false và Sum+=ts, nạp 0 0 vào stack sau đó nạp các đỉnh kề j và trọng số tương ứng với đỉnh đang xét mà Chuaduyet[i]=true, nếu i không có đỉnh liền kề thỏa mãn yêu cầu, tức là duyệt hết tất cả các đỉnh(do đồ thị đang xét là đồ thị đủ). Ta cộng trọng số của cạnh i ->1 vào Sum và gán min bằng Min(sum, min). Sum-=canh i->1.
  3. Lặp lại quá trình sau: Lấy đỉnh từ stack ra, nếu đỉnh này không còn đỉnh kề thỏa mãn yêu cầu thì Pop đỉnh và trọng số này ra, nếu có đỉnh thỏa mãn thì thoát vòng lặp và duyệt tiếp từ đỉnh này, trường hợp lấy đỉnh từ stack ra là 0 thì Pop 2 lần để lấy 2 đỉnh liên tục trong stack ra sau đó tiếp tục vòng lặp.


Ví dụ về việc sử dụng thuật toán vét cạn đề giải quyết bài toán:
Xem thêm tại: http://nikengroup.com/giai-thuat-bac...-lich-tsp.html