Thứ Ba, 6 Tháng 10, 2015 - Nhóm 1 : Bài Tập

Thứ Ba, 6 tháng 10, 2015

Bài Tập Môn Toán Rời Rạc Đề Bài: Thuật Toán Cái Túi Người thực hiện: Ngô Xuân Cường MSV: 1466704 Nguyễn Văn Bẩy MSV:1401295 Nguyễn Sỹ Giang MSV:1400207 Giảng Viên: Trần Xuân Thanh Mục Lục Giới thiệu: Chương I: Bài toán cái túi 1.1Giới thiệu 1.2Bài toán cái túi dạng 0-1 1.3Bài toán cái túi dạng phân số Chương II 2.1 Giải bài toán cái túi bằng phương pháp trực tiếp(Brute-force) Chương III Giải bài toán cái túi bằng thuật toán tham lam(Greedy) 3.1 Giải bài toán này bằng thuật toán tham lam Chương IV: Giải bài toán cái túi bằng thuật toán nhánh cận 4.1 Giới thiệu 4.2 Ứng dụng

Giới thiệu :

Báo cáo này sẽ trình bày về thuật toán giải quyết bài toán cái túi

Chương I : Bài toán cái túi

1.1GIỚI THIỆU.

Bài toán cái túi(hay còn gọi là bài toán xếp ba lô) là một bài toán tối ưu tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trong có thể nhét vừa vào một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Ví dụ về bài toán cái túi trong giới hạn một chiều: chọn các hộp nào để làm cho giá trị tiền là cực trại khi tổng trọng lượng không vượt quá 15kg? Bài toán đa chiều có thể xét đến khối lượng riêng và kích thước của hộp, đó là bài toán xếp vali điển hình(packing problem) Ta có n loại đồ vật, từ 1 tới n. Mỗi đồ vật thứ i có trọng lượng w[i] và giá trị v[i]. Trọng lượng tối đa mà túi có thể mang được là S.

1.2BÀI TOÁN CÁI TÚI DẠNG 0-1.

Hạn chế số đồ vật thuộc mỗi loại là 0 (không được chọn ) và 1 (được chọn). Bài toán cái túi bị chặnhạn chế số đồ vật huộc mỗi loại nào đó không được vượt quá một lượng nào đó. Bài cái túi không bị chặnkhông có một hạn chế nào về số lượng đồ vật mỗi loại. Một trường hợp đặc biệt của bài toán này nhận được nhiều quan tâm, đó là bài toán với các tính chất: ·là một bài toán quyết định ·là một bài toán 0/1 ·với mỗi đồ vật, chi phí bằng giá trị: C = V Trường hợp đặc biệt này được gọi là bài toán tổng các tập con (subset sum problem). Với một số lý do, trong ngành mật mã học, người ta thường dùng cụm từ "bài toán cái túi khi thực ra đang có ý nói về "bài toán tổng con". Bài toán cái túi thường được giải bằng quy hoạch động, tuy chưa có một thuật toán thời gian đa thức cho bài toán tổng quát. Cả bài cái túitổng quát và bài toán tổng con đều là các bài NP-khó, và điều này dẫn đến các cố gắng sử dụng tổng con làm cơ sở cho các hệ thống mật mã hóa khóa công khai, chẳng hạn Merkle-Hellman. Các cố gắng này thường dùng nhóm thay vì các số nguyên. Merkle-Hellman và một số thuật toán tương tự khác đã bị phá, do các bài toán tổng con cụ thể mà họ tạo ra thực ra lại giải được bằng các thuật toán thời gian đa thức. Phiên bản bài toán quyết định của bài toán cái túi được mô tả ở trên là NP-đầy đủ và trong thực tế là một trong 21 bài toán NP-đầy đủ của Karp.

1.3BÀI TOÁN CÁI TÚI DẠNG PHÂN SỐ

Với mỗi loại, có thể chọn một phần của nó (ví dụ: 1Kg bơ có thể được cắt ra thành nhiều phần để bỏ vào ba lô)

Chương 2: Giải bài toán cái túi bằng thuật toán trực tiếp (Brute-force)

Phương pháp này duyệt tất cả khả năng chất đồ vào túi, tìm cách chất có tổng giá trị lớn nhất trong số các cách chất co tổng trọng lượng các đồ vật không quá dung lượng của túi

Chương 3: Giải bài toán cái túi bằng thuật toán tham lam

3.1 Thực hiện bài toán này bằng thuật toán tham lam Các hàm được sử dụng : ·swap (x,y) được dùng để đổi chỗ biến x và y khi sắp xếp ·nhap() dùng để nhập dữ liệu từ bàn phím ·sapxep() được dùng để sắp xếp lại mảng theo thứ tự giảm dần của tỉ lệ v[i]/w[i] , tức là tỉ lệ giảm dần của giá trị trên khối lượng mỗi đồ vật ·thamlam() lần lượt trọn các đồ vật đã được sắp xếp theo thứ tự giảm dần của giá trị trên khối lượng, biến kỉ lục ghi nhận kết quả tốt nhất khi thực hiện Độ phức tạp: ·Nếu sử dụng sắp xếp đơn giản (chèn, nổi bọt…) thì độ phức tạp của cả bài toán là O(n2) ·Nếu sử dụng quick sort hoặc merge sort thì độ phức tạp là O(nlogn) tốt hơn so với giải trực tiếp ·giảm dần của giá trị trên khối lượng mỗi đồ vật ·thamlam() lần lượt trọn các đồ vật đã được sắp xếp theo thứ tự giảm dần của giá trị trên khối lượng, biến kỉ lục ghi nhận kết quả tốt nhất khi thực hiện Độ phức tạp: ·Nếu sử dụng sắp xếp đơn giản (chèn, nổi bọt…) thì độ phức tạp của cả bài toán là O(n2) ·Nếu sử dụng quick sort hoặc merge sort thì độ phức tạp là O(nlogn) tốt hơn so với giải trực tiếp

Chương IV: Giải bài toán cái túi bằng thuật toán nhánh cận

4.1 Giới thiệu. Một bài toán tìm phương án tối ưu đơn thuần chỉ cần liệt kê tập tất cả các phương án và chọn phương án tốt nhất. Tuy nhiên như thế ta phải tốn kém nhiều thời gian cho quá trình giải bài toán. Thử nghĩ nếu trong quá trình tìm kết quả cho một phương án, nhận thấy phương án này không thể là phương án tối ưu được liệu ta có nên bỏ qua để duyệt phương án khác hay không ? Kỹ thuật nhánh cận là như vậy. Trong quá trình tìm lời giải của một phương án, luôn xây dựng điều kiện nếu đi theo thương án này liệu có tốt hơn các phương án đã có hay không nhằm mục đích loại bỏ sớm các phương án không dẫn đến lời giải tối ưu. Cụ thể luôn xây dựng một giá trị lớn nhất (cận) đạt được nếu đi theo phương án (nhánh) này từ đó sẽ quyết định đi theo nhánh có cận cho là tốt nhất. Vì thế nên nó mới có tên là kỹ thuật nhánh cận ( Branch and Bound ). 4.2Ứng dụng. Ví Dụ: Có một tên trộm mang theo một cái túi có thể đựng trọng lượng tối đa là M vào một cửa hàng có n loại đồ vật, mỗi loại đồ vật có một giá trị (v) và trọng lượng (w) riêng ( giả sử số lượng mỗi đồ vật là rất nhiều ). Hỏi tên trộm chọn những loại đồ vật nào với số lượng bao nhiêu để tổng trọng lượng không vượt quá trọng lượng tối đa của cái túi (M) và tổng giá trị của các đồ vật (V) là lớn nhất ? Áp dụng kỹ thuật nhánh cận để giải bài toán. Ký hiệu : w[i] là trọng lượng của loại đồ vật i. (i = 1..n). v[i] là giá trị của loại đồ vật i. (i = 1..n). Mô hình bài toán có thể đưa về dạng bài toán quy hoạch tuyến tính nguyên tìm vectơ x = [ x1 , .. , xn ] ( với x1, .. , , xn là số lượng loại đồ vật 1,..,n được chọn ) như sau. Hàm mục tiêu : f = v1*x1 + ... + vn*xn  max. Hệ ràng buộc : w1*x1 + .. + wn*xn ≤ M xi ≥ 0 ( i = 1 .. n ) Để đánh giá giá trị của đồ vật so với trọng lượng ta dùng hệ số giá trị : vi/wi ( i = 1..n). Ưu tiên các đồ vật có hệ số giá trị lớn chọn trước nên ta sắp xếp các loại đồ vật từ cao đến thấp theo hệ số giá trị. v1/w1 ≥ v2/w2 ≥ .. ≥ vn/wn. Dễ thấy giá trị tối đa của cái túi f(x) ≤ M*v1/w1. Vậy x1 có thể nhận các giá trị trong tập S1 = { k1 | k1 ≤ M/w1 }. Ứng với mỗi giá trị x1 = k1  S ta thiết lập một nhánh phương án có cập trên là: k1*v1 + ( M – k1*w1 )* v2/w2. Và trong nhánh này, x2 có thể nhận các giá trị trong tập: S2 = { k2 | k2*w2 ≤ ( M – k1*w1 ) } Ứng với mỗi giá trị x2 = k2  S2 ta lại thiết lập một nhánh phương án có cận trên là : k1*v1 + k2*v2 + ( M – k1*w1 - k2*w2)* v3/w3. Tương tự quá trình thiết lập nhánh và cận trên cứ lặp lại cho tới khi nào không thể chọn thêm một đồ vật nào nữa. (túi không thể chứa thêm đồ vật nào nữa). Để tìm phương án tối ưu ta đi theo nhánh có cận lớn nhất. Ký hiệu : a : giá trị đồ vật đang đạt được, b: cận trên của nhánh, M’ là trọng lượng còn lại. Chương trình (C): Input : File balo.inp ( Đã xếp theo thứ tự nhỏ dần của v[i]/w[i]. 4 8 5 3 2 4 10 5 3 6 Giải thích: File balo.inp tương ứng với: n M w[1] w[2] w[3] w[4] v[1] v[2] v[3] v[4] Ouput: File balo.out 15 1 1 0 0 Giải thích: File balo.out tương ứng với: Vmax //Giá trị tối ưu. x[1] x[2] x[3] x[4] //Số lượng loại đồ vật được chọn. Code: #include<iostream> #include<stdio.h> #include<conio.h> #define MAX 100 int x[MAX],y[MAX]; int w[MAX]; int v[MAX]; int n; int m; int wrem; int a; float b; int vmax,vsel,wsel; FILE *fp; char *finp = "balo.inp"; char *fout = "balo.out"; void init(); void ouput(); void ghinhan(); void Try(int i); void main(){ init(); Try(1); output(); getch(); } void init(){ int i; if((fp=fopen(finp,"r"))!=NULL){ fscanf(fp,"%d %d\n",&n,&m); for(i=1;i<=n;i++){ fscanf(fp,"%d",&w[i]); } fscanf(fp,"\n"); for(i=1;i<=n;i++){ fscanf(fp,"%d",&v[i]); } //====== a=0; wrem=m; b=wrem*v[1]/(float)w[1]; vmax = 0; vsel=0; wsel=0; fclose(fp); } else{ printf("Khong tim thay file input"); exit(1); } } void output(){ if((fp=fopen(fout,"w"))!=NULL){ int i; fprintf(fp,"%d\n",vmax); for(i=1;i<=n;i++){ fprintf(fp,"%3d",y[i]); } fclose(fp); } else{ printf("Khong tim thay file output"); } } void ghiNhan(){ int i; if(vmax<vsel){ vmax=vsel; for(i=1;i<=n;i++){ y[i]=x[i]; } } } void Try(int i){ int j; for(j=0;j<=wrem/(float)w[i];j++){ b=vsel+j*v[i] + (wrem-j*w[i])*v[i+1]/(float)w[i+1]; if(b>=vmax){ x[i]=j; vsel = vsel + j*v[i]; wsel = wsel + j*w[i]; wrem = wrem - j*w[i]; if((i==n)||(wrem<=0)) else ghiNhan(); Try(i+1); x[i] = 0; vsel = vsel - j*v[i]; wsel = wsel - j*w[i]; wrem = wrem + j*w[i]; } } Return 0; } Người đăng: Unknown vào lúc 04:02 Gửi email bài đăng nàyBlogThis!Chia sẻ lên XChia sẻ lên FacebookChia sẻ lên Pinterest

Không có nhận xét nào:

Đăng nhận xét

Bài đăng Mới hơn Trang chủ Đăng ký: Đăng Nhận xét (Atom)

Giới thiệu về tôi

Unknown Xem hồ sơ hoàn chỉnh của tôi

Lưu trữ Blog ▼  2015 (2) ▼  tháng 10 (2)                           Bài Tập Môn Cơ Sở Dữ Li...                    Bài Tập Môn Toán Rời Rạc