Code thuật toán nhánh cận người du lịch năm 2024
|
Bài toán người du lịch: Một nguời du lịch muốn đi tham quan n thành phố T1,T2…, Tn . Xuất phát từ một thành phố nào đó, người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua duy nhất 1 lần rối quay trở trở lại thành phố xuất phát. Gọi Cij là chi phí đi từ thành phố Ti đến Tj . Hãy tìm một hành trình thỏa yêu cầu bài toán sao cho chi phí là nhỏ nhất. Hãy cùng Lập trình không khó đi giải quyết bài toán này nhé các bạn Code bài toán người du lịchChúng ta sẽ lưu ma trận chi phí đi từ Ti đến Tj là int graph[4][4] \= { {0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0} }; Chúng ta giả sử có 4 thành phố: T0, T1, T2, T3. Như vậy thì hàng đầu tiên là chi phí đi từ T0 đến T0, T1, T2, T3 lần lượt là 0, 10, 15, 20. Tương tự với các hàng phía sau. Hỗ trợ thanh toán qua INTERNET BANKING tất cả các ngân hàng: VietcomBank, BIDV, VietinBank, SacomBank, TechcomBank, Á Châu, TPbank, MBbank, AgriBank, VPbank, SHB, MaritimeBank, DongAbank, VIB, EximBank, HDbank, NCB, Việt Á, OceanBank, PGbank, BacAbank... Bạn cần đăng nhập để tải code qua chức năng này! ĐĂNG NHẬP NGAY Hỗ trợ CHUYỂN KHOẢN TRỰC TIẾP qua các số tài khoản ngân hàng: VietcomBank, BIDV, VietinBank, SacomBank, TechcomBank, Á Châu, TPbank, MBbank, AgriBank, VPbank, SHB, MaritimeBank Bạn cần đăng nhập để tải code qua chức năng này! ĐĂNG NHẬP NGAY
→ Số nghiệm là : K 134 = C 13 (4+13-1) = C 1316 Vậy q = C 13 16 Lý luận tương tự, ta có : r = K 94 = C 9 (4+9-1) = C 912 → p = q - r = C 1316 - C 912 = 560 - 220 = 340 Vậy số nghiệm nguyên không âm của phương trình (1) thỏa điều kiện () là 340. Câu 4: Áp dụng thuật toán nhánh cận giải bài toán người du lịch với ma trận chi phí như sau: ∞ 08 05 22 04 ∞ 09 17 15 07 ∞ 12 05 27 17 ∞ BÀI LÀM
(3,h) (3,k) (2,k)* (6,h) (∞,-) (8,h) - - (3,h)* (3,k) - (4,c) (∞,-) (5,c) - -
Từ k đến h : k→h ; Độ dài : 1 ; S = {k,h}. Từ k đến g : k→c→g ; Độ dài : 5 ; S = { k,c,g}. Từ k đến e : k→c→g→e ; Độ dài : 10 ; S = {k,c,g,e}. Từ k đến d : k→c→d ; Độ dài : 4 ; S = {k,c,d}. Từ k đến c : k→c ; Độ dài : 2 ; S = {k,c}. Từ k đến b : k→b ; Độ dài : 3 ; S = {k,b}. Từ k đến a : k→h→a ; Độ dài : 3 ; S = {k,h,a}. c) Khởi tạo [∞,k] [3,k] [2,k] [∞,k] [∞,k] [∞,k] [1,k]* [0,k] k 1 [2,h]* [3,k] [2,k] [5,h] [∞,k] [7,h] - - k,h 2 - [3,k] [2,k]* [5,h] [∞,k] [7,h] - - k,h,a 3 - [3,k] - [2,c]* [∞,k] [3,c] - - k,h,a,c 4 - [3,k]* - - [7,d] [3,c] - - k,h,a,c,d 5 - - - - [7,d] [3,c]* - - k,h,a,c,d,b 6 - - - - [5,g]* - - - k,h,a,c,d,b,g 7 - - - - - - - - k,h,a,c,d,b,g,e → Độ dài cây khung nhỏ nhất là: 1+2+2+2+3+3+5 = 18. Cây khung nhỏ nhất của đồ thị : II. LẬP TRÌNH :
2. Ý tưởng giải thuật:...............................................................................................Ta đánh giá được một giới hạn (cận) chung cho những giá trị này (đối với bài toán tìm min là cận dưới, đối với bài toán tìm max là cận trên). Nếu cận tính được không tốt hơn kỷ lục hiện có (đối với bài toán tìm min là không nhỏ hơn, đối với bài toán tìm max là không lớn hơn) thì có nghĩa là hướng phát triển của nhánh tìm kiếm này là vô ích, có thể bỏ qua để xét giá trị khác cho xi. Việc không xét những giá trị tiếp theo của xi giúp cho loại bỏ được một loạt các nhánh trên cây tìm kiếm. Vì thế kỹ thuật đánh giá này có tên gọi là đánh giá nhánh cận (tìm cận tại mỗi nhánh tìm kiếm). Để đánh giá được nhánh cận, cần có sự xem xét kỹ tính chất của hàm mục tiêu và điều này không đơn giản. Thông thường, cận được đánh giá cố gắng đạt được hai tiêu chí :
int chuaxet[100]; int kq[100]; int MIN=0; int a=1; void Input() { cout<<"\nNhap so luong thanh pho: "; cin>>n; cout<<"Nhap chi phi cho cac cung duong \n"; for(int i=1; i<=n; i++) for(int j=1;j<=n;j++) { if(i!=j) { cout<<"c["< void Output() { cout<<"\nMa tran chi phi :\n"; for(int i=1; i<=n; i++) { cout<<"{" ; for(int j=1;j<=n;j++) { if(j!=n) cout< int main() { Input(); Output(); Try(2); Result(); getch(); } 4. Chạy chương trình : III. TÀI LIỆU THAM KHẢO : |
