trang_lovely_kt8689
New Member
Download miễn phí Đề tài Thuật toán nhánh cận trên môi trường song song
MỤC LỤC
Chương 1 : TỔNG QUAN VỀ THUẬT TOÁN NHÁNH CẬN - 3 -
1.1. Thuật toán nhánh cận - 3 -
1.2. Một số ví dụ cụ thể áp dụng thuật toán nhánh cận - 4 -
Chương 2 : XÂY DỰNG KHUNG THUẬT TOÁN NHÁNH CẬN - 6 -
* Nhóm các lớp yêu cầu - 7 -
* Nhóm các lớp cung cấp - 9 -
2.1. Xây dựng khung nhánh cận - 11 -
2.1.1. Cấu trúc dữ liệu - 11 -
2.1.2. Thuật toán - 11 -
2.2. Xây dựng khung nhánh cận tuần tự - 14 -
2.3. Xây dựng khung nhánh cận song song - 15 -
2.3.1. Lược đồ song song dữ liệu tập trung - 18 -
2.3.2. Lược đồ song song dữ liệu phân tán - 20 -
2.4. Công cụ phát triển hệ thống - 24 -
2.5. Lựa chọn mô hình phát triển hệ thống - 25 -
Chương 3 : SỬ DỤNG THUẬT TOÁN NHÁNH CẬN ĐỂ GIẢI QUYẾT BÀI TOÁN TSP - 27 -
* Bài toán TSP (Bài toán người du lịch) - 27 -
3.1. Giới thiệu bài toán - 27 -
3.2. Định nghĩa bài toán - 27 -
3.3. Sử dụng thuật toán nhánh cận để giải bài toán TSP - 28 -
3.4. Chương trình thực thi - 31 -
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ai 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.Để áp dụng phương pháp nhánh cận đối với 1 tập các bài toán tối ưu chúng ta cần làm theo các bước sau:
Bước1 ( khởi tạo): L:={П0}, Q: ={П0},bs:= -∞ và T:=(tập hợp rỗng).
Bước 2( tìm kiếm): đi tới Bước 9 nếu L =
đi đến Bước 3 sau khi lựa chọn Пi:= s(Ls) để kiểm tra.
Bước 3 (cập nhật ): Nếu lower_bound(Пi)> bs, thì bs:= lower_bound(Пi) và T:={σ } với σ là lời giải khả thi của Пi sao cho f(x,σ )= lower_bound(П i). Đi tới bước 4.
Bước 4 : đi tới Bước 8 nếu Пi G (tập hợp các bài toán bộ phận Пi được giải trong tiến trình tính toán cận trên của Пi). ngược lại thì đi đến Bước 5.
Bước 5: ( kiểm tra cận trên): đi đến bước 8 nếu cận trên nhỏ hơn bs: upper_bound(Пi) ≤ bs. Ngược lại đi tới bước 6.
Bước 6: đi tới bước 8 nếu tồn tại một Пk (≠ Пi) Q mà f(Пk) ≥ f(Пi). Ngược lại đi tới bước 7.
Bước7: (phân nhánh): Phân và cập nhật . Quay trở lại bước 2.
Bước 8 ( kết thúc bài toán con): gán L:= L - Пi sau đó quay trở lại bước 2.
Bước 9 ( kết thúc toàn bộ ) : Dừng. bs = f(П0) và T lưu trữ một lời giải tối ưu của П0, nếu bs = - ∞ , П0 không có lời giải
Một số ví dụ cụ thể áp dụng thuật toán nhánh cận
Bài 1: Bài toán người du lịch( TSP)
Phát biểu bài toán : Một người du lịch muốn đi thăm 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ố đúng một lần, rồi quay trở lại thành phố xuất phát. Biết ci,j là chi phí từ thành phố Ti đến thành phố Tj . Hãy tìm hành trình với tổng chi phí nhỏ nhất
Xây dựng công thức :
Phương án : p = (p1, p2, … pn) là hoán vị của 1, 2, …, n
Hành trình : T p1 ® T p2 ® …… ® T pn
Chi phí : f(p) = c p1, p2 + c p2, p3 + …. + c pn, p1
P : tập tất cả các hoán vị
=> min {f(p) : p Î P }
Tư tưởng của thuật toán nhánh cận:
Cố định thành phố 1
Tìm cực tiểu của hàm :
f(x2, x3, . . , xn) = c[1,x2] + c[x2,x3] + ... + c[xn,1] => min
x2, x3, . . , xn là hoán vị của các số 2, 3, …, n
Ký hiệu : cmin = min{c[i,j]; i, j = 1,2,…,n, i≠j}
Giả sử có phương án bộ phận (u1,u2, …, uk)
Chi phí phải trả là : s = c[1,u2] + c[u2,u3] + ... + c[uk-1, uk]
Cận dưới là : g (u1,u2, …, uk) = s + (n-k+1)*cmin
Phương pháp phân nhánh:
+ Nếu bài toán con có g() > f -(Kỉ lục tạm thời) thì cắt luôn nhánh của bài toán này
+ Nếu không thì phân nhánh tiếp bài toán con cho đến khi tính được kỉ lục của bài toán con này. Nếu kỉ lục của bài toán con nhỏ hơn f() thì cập nhật lại kỉ lục tạm thời f()
Phương pháp tính cận:
tính cận trên của bài toán con dựa vào công thức
= c[1,u2] + c[u2,u3] + ... + c[uk-1, uk]
g (u1,u2, …, uk) = s + (n-k+1)*cmin
Bài 2: Bài toán cái túi
Phát biểu bài toán : Một nhà thám hiểm cần đem theo một cái túi có trọng lượng không quá b. Có n đồ vật có thể đem theo. Đồ vật thứ j có trọng lượng a và giá trị sử dụng là c . Hỏi rằng nhà thám hiểm cần đem theo các đồ vật nào để cho tổng giá trị sử dụng của các đồ vật đem theo là lớn nhất.
Xây dựng công thức :
Phương án x = {x1,x2, …, xn}
Giá trị đồ vật đem theo
Tổng trọng lượng đồ vật
min{f(x) : g(x) ≤ b}
XÂY DỰNG KHUNG THUẬT TOÁN NHÁNH CẬN
Thuật toán nhánh cận được xây dựng với mong muốn giải quyết được tập các bài toán tối ưu tổ hợp. Có nghĩa là tất cả các bài toán đó sẽ được giải quyết dựa trên một khung chung của thuật toán để khi vào một bài toán cụ thể người viết chương trình chỉ cần thêm vào khung đó những dữ liệu phù hợp với bài toán của mình. Nó giảm bớt thời gian xây dựng thuật toán đồng thời nó hữu ích cho những người không biết kỹ thuật nhánh cận trên môi trường song song vẫn có thể cài đặt song song. Chương này sẽ trình bày việc xây dựng khung của kĩ thuật nhánh cận và kỹ thuật nhánh cận trên môi trường tuần tự hay song song.
Hệ thống gồm hai nhóm : một nhóm các lớp cung cấp (Provided) bao hàm các thủ tục chung cho thuật toán nhánh cận (ví dụ như khung của thuật toán nhánh cận tuần tự, khung của thuật toán nhánh cận song song ...) và nhóm các lớp yêu cầu (Required) bao hàm các thủ tục riêng để giải quyết một bài toán cụ thể sử dụng kỹ thuật nhánh cận (ví dụ như các thủ tục tính cận, thủ tục phân nhánh, ...). Để giải quyết một bài toán bằng kỹ thuật nhánh cận, người sử dụng chỉ cần viết các khai báo và xây dựng các hàm trong nhóm yêu cầu mà không cần xây dựng lại nhóm cung cấp. Hình 4.1 diễn tả mô hình UML tổng quan của hệ thống.
Hình 1 : Mô hình UML
* Nhóm các lớp yêu cầu
Mô hình chung của nhóm các lớp yêu cầu
Hình 2 diễn tả các lớp và thủ tục chính trong nhóm yêu cầu.
Hình 2 : Các lớp yêu cầu
Các lớp yêu cầu được sử dụng để lưu trữ dữ liệu cơ bản của thuật toán : bài toán, trạng thái không gian tìm kiếm. Nó bao gồm các lớp chính sau :
Bài toán (Problem): Diễn tả các tham số của bài toán cần giải quyết.
Bài toán con (Subproblem) : Diễn tả vùng không gian chưa được khai thác và cung cấp các chức năng sau :
InitSubProblem(pbm) : Sinh ra bài toán con đầu tiên từ bài toán ban đầu
LowerBound(pbm, sol) : Tính toán cận dưới của hàm mục tiêu cho lời giải bộ phận sol của bài toán pbm.
UpperBound(pbm, sol) : Tính giá trị hàm mục tiêu của lời giải toàn cục sol của bài toán pbm.
Branch(pbm, sps) : Sinh ra một tập các bài toán con của bài toán đang xét và lưu vào sps.
Lớp bài toán con diễn tả một bài toán bộ phận. Một bài toán con được xác định bởi các dữ liệu sau : vector sol chứa các chỉ số đỉnh làm median của bài toán con (hay là lời giải bộ phận của bài toán cần giải quyết) và được sắp xếp theo thứ tự tăng dần, chỉ số đỉnh cuối eV của lời giải bộ phận, và cận dưới cost ứng với lời giải bộ phận sol.
Lớp bài toán con phải cung cấp các hàm chính sau :
InitSubProblem(pbm): sinh ra bài toán con ban đầu với
Các hàm tính cận dưới (LowerBound), tính cận trên (UpperBound), phân nhánh (Branch).
* Nhóm các lớp cung cấp
Trước khi mô tả lớp cung cấp chúng ta cần xem xét cấu trúc dữ liệu để lưu các bài toán con chưa được giải quyết trong quá trình tính toán. Vì số lượng các bài toán con là rất lớn và không biết trước nên ta sử dụng một danh sách liên kết kép để quản lý chúng.
Lớp Solver : Làm nhiệm vụ đưa ra và duy trì các thông tin có liên quan tới trạng thái tìm kiếm trong suốt quá trình thực hiện
class Solver {
protected:
const Problem& pbm;// bài toán cần giải quyết
Direction dir;
SubProblem sp; // bài toán con hiện thời cần giải quyết
Solution sol; // giải pháp tốt nhất hiện thời
container HP;// danh sách các bài toán con cần giải quyết
Bound high;// cận trên của nhánh bài toán con
Bound low;// cận dưới của nhánh bài toán con
Bound bestSol;// kỉ lục hiện thời của bài toán
public:
Solver(const Problem &problem);
..........................
Có hai lớp kế thừa từ lớp Solver
L
