Bài viết chưa trả lời | Chủ đề sôi nổi Hôm nay, 26 Tháng 7 2017 15:33



Gửi bài trả lời  [ 1 bài viết ] 
 Giải thuật backtracking cho bài toán người du lịch – TSP 
Người gửi Nội dung
Nhập môn
Nhập môn
Hình đại diện của thành viên

Ngày tham gia: 08 Tháng 4 2017 00:38
Bài viết: 6
Has thanked: 0 time
Been thanked: 0 time

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:

Ban đầu đưa đỉnh 1 và 0 vào stack, Sum=0;
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.
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 tại: http://nikengroup.com/giai-thuat-backtr ... h-tsp.html








30 Tháng 4 2017 12:03
Xem thông tin cá nhân
Hiển thị những bài viết cách đây:  Sắp xếp theo  
Gửi bài trả lời   [ 1 bài viết ] 

Ai đang trực tuyến?

Đang xem chuyên mục này: Không có thành viên nào đang trực tuyến3 khách


Bạn không thể tạo chủ đề mới trong chuyên mục này.
Bạn không thể trả lời bài viết trong chuyên mục này.
Bạn không thể sửa những bài viết của mình trong chuyên mục này.
Bạn không thể xoá những bài viết của mình trong chuyên mục này.
Bạn không thể gửi tập tin đính kèm trong chuyên mục này.

Tìm kiếm với từ khoá:
Chuyển đến:  
Powered by phpBB® Forum Software © phpBB Group
Designed by thanh_khe and ST Software.
Vietnamese language pack for phpBB 3.0.x download and support.