Đề Tài Thuật Toán Nhánh Cận - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (10 trang)

Trang chủ

Luận Văn - Báo Cáo

Công nghệ thông tin

Đề Tài Thuật toán nhánh cận

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (115.89 KB, 10 trang )

Tiểu luậnĐề Tài: Thuật toán nhánh cận Phần 1: Tổng Quan Về Thuật Toán Nhánh Cận Thuật toán nhánh cận là phương pháp chủ yếu để giải các bài toán tối ưu tổ hợp. Ta sẽ thực hiện việc đánh giá theo từng bước, nếu không có khả năng tìm thấy kết quả tốt hơn thì sẽ cắt nhánh đó, không thực hiện tìm tiếp mà chuyển ngay sang nhánh khác. Khi đó, chỉ ghi nhận các kết quả tốt hơn lúc ban đầu. Nghiệm của bài toán sẽ tốt dần lên do khi tìm ra kết quả tốt hơn ta sẽ cập nhật lại giá trị hiện thời của bài toán.1.Đặt vấn đề: Một trong những bài toán đặt ra trong thực tế là tìm một nghiệm thỏa mãnmột số điều kiện nào đó và nghiệm đó là tốt nhất theo một tiêu chí cụ thể.Ví dụ: bài toán người du lịch không gian trạng thái là N!Bài toán K-median không gian trạng thái là C Khi đó, không gian tìm kiếm của bài toán là rất lớn trong khi nhiều trường hợp có thể loại bỏ được ngay.Điều này gây nên tình trạng lãng phí bộ nhớ và mất rất nhiều thời gian.Vấn đề đặt ra trong quá trình liệt kê lời giải cần tận dụng những thông tin đã có để loại bỏ sớm những phương án chắc chắn không tối ưu.Thuật toán nhánh cận được sử dụng để khắc phục những vấn đề trên2. Tư tưởng của thuật toán: Tư tưởng của thuật toán là trong quá trình tìm kiếm lời giải, ta sẽ phân hoạch tập các phương án của bài toán thành hai hay nhiều tập con biểu diễn như một nút của cây tìm kiếm và cố gắng bằng phép đánh giá cận các nút, tìm cách loại bỏ các nhánh cây(những tập con các phương án của bài toán) mà ta biết chắc chắn không phải là phương án tối ưu. Mặc dù trong trường hợp tồi nhất thuật toán sẽ trở thành duyệt toàn bộ, nhưng những trường hợp cụ thể nó rút ngắn đáng kể thời gian tìm kiếm Phần 2: Một số ví dụ minh họa1. Bài toán người giao hàng:1.1 Mô tả bài toán:-Một người cần phải giao hàng tại N thành phố T1,T2,….Tn -Cij : chi phí đi từ thành phố Ti đến thành phố Tj(i=1,2,….n; j = 1,2,…,n)-Yêu cầu: xác định hành trình thỏa mãn Đi qua tất cả các thành phố, mỗi thành phố qua đúng 1 lần, rồi quay trở lại thành phố xuất phát  Chi phí nhỏ nhất -Ta có các phương án giải quyết bài toán: Phương pháp vét cạn Phương pháp vét cạn quay lui Một số phương pháp khác- Nhược điểm: Phải xét những phương án không khả thi (gây bùng nổ dữ liệu khi đầu vào n lớn)- Ý tưởng của thuật toán: Giữ lại một phương án mẫu Tính chi phí của các phương án khác ngay trong quá trình xây dựng  Tốt hơn : Cập nhật lại phương án mẫu và đi tiếp Không tốt hơn : Quay lại bước trên xét phương án khác 1.2 Thuật giải: - Bài toán tối ưu: Tìm min{ f(x) : x Є D} Với X = {a = (a1, a2…., an) Є ПAi (i=1,2,….n) : P(x)}|Ai<∞ | với mọi i= 1,2,….,n với P là một tính chất trên tập Ai_- Nghiệm của bài toán có dạng x=(x1, x2,….,xn)- Bước 1: xuất phát từ x1, xây dựng một phương án mẫu f*- Bước i : Đã xây dựng được nghiệm thành phần (x1, x2,… ,xi-1)Đánh giá cận: tìm g xác định trên Xi g(x1,… xi) < Min {f(a): a=(a1,….,an) thuộc X , xi=ai, i=1,2,…,n} Giả sử x* là lời giải tốt nhất tại thời điểm đó, f* là giá trị tốt nhất f*= f(x*)  Nếu f*<g có thể bỏ đi không cần phát triển lời giải bộ phận (x1,…… ,xi) Ngược lại: tiến hành bước i+1 để các đinh xi + 11.3 Cài đặt: Try(i) { For (j=1->n) If (chấp nhận được ) { Xác định xi theo j; Ghi nhận trạng thái mới; If (i=n) Cập nhật lời giải tối ưu; Else{ Xác định cận g(x1,… ,xi); If (g(x1, ,xi) < f*) Try(i+1) } }}1.4 Đánh giá:- Ưu điểm: Giảm được chi phí do loại bỏ được những bước đi không cần thiết ( nhờ đánh giá cận)- Nhược điểm : Việc xây dựng hàm g phụ thuộc vào từng bài toán tối ưu tổ hợp cụ thể. Hàm g phải đảm bảo điều kiện:Việc tính giá trị hàm g phải đơn giản hơn việc giải bài toán tổ hợp tìm min = min {f(a): a=(a1,….,an) thuộc X , xi=ai, i=1,2,…,n}Giá trị của g (a1,a2,…,ak) phải sát với các giá trị của min2. Bài toán người đưa hàng:2.1 Ý tưởng:Gọi p là một hoán vị của (1,…,n) ta được hành trình Tp(1) -> Tp(2) -> …Tp(n) Có n! hành trình Nếu cố định đỉnh xuất phát là đỉnh 1 thì có (n-1)! Hành trình, bài toán trở thành  Tìm Min {f(a2,….an): (a2,… ,an )} là hoán vị của {2, ,n}} với f(a1,……,an) = C1,a2 + Ca2,a3 +…….+ Can-1,an + Can,1 Ta sẽ kết hợp đánh giá nhánh cận trong quá trình liệt kê phương án của thuật toán quay lui2.2 Thuật giải: Cố định xuất phát là đỉnh 1, duyệt vòng lặp từ j= 2 Tại bước i : Đánh giá cận  Đặt Cmin= Min {Cij : i,j = (1,…,n)} Giả sử đã đi đoạn đường T1 ->T2… >Ti với chi phí Si = C1,x2 + Cx2,x3 +…….+ Cxi-1,xi  Hàm cận g(1,…,xi) = Si +(n-i+1)Cmin Lưu dấu bằng mảng logic Daxet[]: Daxet[j] = 1 nếu T[j] đã qua 0 nếu T[j] chưa qua  Xác định xi = j cập nhật Daxet[j]= 1 và S= S+ Cxi-1,xi Nếu i=n , Tong = S + Cxn,1; Nếu (Tong<f*) thì lời giải tối ưu = x; f* = Tong; Nếu Daxet[j]= 0 thì S=S- Cxi-1,xi 2.3 Cài đặt: Try(i) for (j= 2 -> n) if(! Daxet[j]) { x[i] = j; Daxet[j]= 1; S= S + C[x[i-1]][x[i]]; If (i==n) // cap nhat toi uu { tong = S + C[x[n]][x[1]]; if (tong < f*) { Lgtu=x; // loi giai toi uu f* = tong; } } Else{ g= S + (n-i+1)* Cmin; // danh gia can if(g<f*) Try (i+1); } S= S- C[x[i-1]][x[i]]; Daxet[j]=0; }2.4 Minh họa Giải bài toán người đưa hàng với ma trận chi phí như sau: Ta có Cmin = 2. Quá trình thực hiện thuật toán được mô tả bởi cây tìm kiếm lời giải được thể hiện trong hình vẽ dưới đây Thông tin về một phương án bộ phận trên cây được ghi trong các ô trên hình vẽ tương ứng theo thứ tự sau:- Đầu tiên là các thành phần của phương án - Tiếp đến ∂ là chi phí theo hành trình bộ phận- g là cận dưới Kết thúc phương án ta thu được phương án tối ưu (1, 2, 3, 5, 4, 1) tương ứng với phương án tối ưu với hành trình: T1 -> T2 -> T3 -> T5 -> T4 -> T1 và chi phí nhỏ nhất là 22. Cây tìm kiếm giải quyết bài toán người đưa hàng (2,4) =25 ; g=34(2,5) =23; g=32(2,3,5) =11; g=17(2,3,5,4) =16 ; g=19Các nhánh này bị loại vì có cận dưới g > =22fur= +∞(2) ∂=3 ; g=15 (3)∂=14 ; g=26 (4) ∂=18 ; g=30 (5) ∂=15 ; g=27(2,3) ∂=7 ; g=16(2,3,4) ∂=23 ; g=29(2,3,4,5) ∂=41; g=44Hành trình (1, 2, 3,4, 5,1) chi phí 53. Đặtfur =53Hành trình (1, 2, 3, 5,4, 1) chi phí 25 (Kỷ lục mới). Đặt fur =22Phần 3: Thuật Toán Giải Quyết Bài Toán Người Đi Du Lịch# include <stdio.h># include <stdio.h># include<conio.h># include<io.h># define MAX 20Int n, P[MAX], B[MAX], C[20][20], count = 0; int A[MAX],XOPT[MAX];int Can, Cmin, fopt;void Read_Data(void){ int i, j; FILE *fp; fp = fopen (“dulich.in”, “r”); fscanf(fp, “%d”, &n); printf(“\n So thanh pho: %d”, n); printf(“\n Ma tran chi phi:”); for (i=1; i< = n; i++){ printf(“\n”); for(j = 1; j< = n; j++){ fscanf(fp, “%d”, &C[i][j]); printf(‘%5d”, C[i][j]); } } } int Min_Matrix(void){ int min = 1000, i, j; for (i=1; i<=n;i++){ for(j=1; j<=n, j++){ if (i!=j && min > C[i][j]) min = C[i][j]; } } Return(min); } Void Init(void){ int i; Cmin = Min_Matrix();fopt = 32000; can = 0; A[1] = 1; for (i = 1; i< = n;i++) B[i] = 1; }Void Result(void){ int i; printf(“\n Hanh trinh toi uu %d:”, fopt); printf(“\n Hanh trinh:”); for(i=1; i<=n;i++) printf(“%3d->”, XOPT[i]); printf(“%d,1”); } Void Swap(void){ int i; for(i=1;i<=n;i++) XOPT[i] = A[i]; } Void Update_Kyluc(void){ int sum; sum= can + C[A[n]][A[1]]; if(sum < fopt){ Swap(); Fopt= sum; } } Void try(int i){ int j; for (j=2; j<=n;j++){ if (B[j]){ A[i]=j; B[j]=0; can = can + C[A[i-1]][A[i]]; if (i= = n) update_Kyluc() else if(can + (n-i+1)* Cmin < fopt){ count ++; try(i+1); } B[j] = 1; can = can – C[A[i-1]][A[i]]; } } } } void main(void){ clrscr(); Read_Data(); Init(); Try(2); Result(); getch(); }

Tài liệu liên quan

Thuật toán nhánh cận trên môi trường song song
- 33
- 704
- 2
GIỚI THIỆU ĐỀ TÀI Phân tích tình hình huy động vốn và cho vay tại ACB chi nhánh Cần Thơ1
- 4
- 501
- 0
Đề tài ĐƯỜNG đi HAMILTON, THUẬT TOÁN NHÁNH cận và bài TOÁN NGƯỜI DU LỊCH
- 30
- 2
- 15
Tài liệu Đề tài "Hoàn thiện bảng cân đối kế toán Việt nam" ppt
- 30
- 425
- 0
Tài liệu Đề tài: Kế toán tập hợp chi phí và tính giá thành sản phẩm”, và “kế toán tiền lương và các khoản trích theo lương” tại Chi nhánh Công ty cổ phần xây lắp và sản xuất công nghiệp - Xí nghiệp xây lắp 3 pdf
- 80
- 388
- 0
Tài liệu Thuật toán nhanh để tìm thời gian biểu với số lượng tùy ý các công việc đúng hạn và thời gian xử lý ít nhất. ppt
- 10
- 571
- 0
.ĐỀ TÀI: THUẬT TOÁN NHÁNH VÀ CÂN CÀI ĐẶT TRÊN CÂY NHỊ PHÂN. potx
- 6
- 901
- 7
Đề tài: Kế toán thanh toán qua ngân hàng, liên hệ thực tế tại Ngân hàng Thương mại Cổ phần Công thương Việt Nam – Chi nhánh Lưu Xá docx
- 86
- 584
- 0
luận văn tốt nghiệp đề tài “một cách tiếp cận bài toán về hàm số ”
- 23
- 819
- 0
Đề tài Kiện toàn mô hình tổ chức và đội ngũ cán bộ thi hành án để thực hiện có hiệu quả luật thi hành án dân sự năm 2008
- 391
- 749
- 2