Áp dụng kĩ thuật tham ăn để giải bài toán này là: để có số tờ giấy bạc phải trả X1 + X2 + X3 + X4 nhỏ nhất thì các tờ giấy bạc mệnh giá lớn phải được chọn nhiều nhất. Trước hết ta chọn tối đa các tờ giấy bạc mệnh giá 100.000 đồng, nghĩa là X1 là số nguyên lớn nhất sao cho X1 100.000 ≤ n. Tức là X1 = n DIV 100.000. Xác định số tiền cần rút còn lại là hiệu n – X1 100000 và chuyển sang chọn loại giấy bạc 50.000 đồng… Ví dụ khách hàng cần rút 1.290.000 đồng n = 1290000, phương án trả tiền như sau: X1 = 1290000 DIV 100000 = 12. Số tiền cần rút còn lại là 1290000 – 12 100000 = 90000. X2 = 90000 DIV 50000 = 1. Số tiền cần rút còn lại là 90000 – 1 50000 = 40000. X3 = 40000 DIV 20000 = 2. Số tiền cần rút còn lại là 40000 – 2 20000 = 0. X4 = 0 DIV 10000 = 0. Ta có X = 12, 1, 2, 0, tức là máy ATM sẽ trả cho khách hàng 12 tờ 100.000 đồng, 1 tờ 50.000 đồng và 2 tờ 20.000 đồng. 3.3.4 Bài toán đường đi của người giao hàngChúng ta sẽ xét một bài tốn rất nổi tiếng có tên là bài tốn tìm đường đi của người giao hàng TSP - Traveling Salesman Problem: Có một người giao hàng cần đi giao hàng tại n thành phố. Xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, khoảng cách từ một thành phố đến các thành phố khác là xác định được. Giả thiết rằng mỗi thành phố đều có đường đi đến các thành phố còn lại. Khoảng cách giữa hai thành phố có thể là khoảng cách địa lý, có thể là cước phí di chuyển hoặc thời gian di chuyển. Ta gọi chung là độ dài. Hãy tìm một chu trình một đường đi khép kín thỏa mãn điều kiện trên sao cho tổng độ dài các cạnh là nhỏ nhất. Hay còn nói là tìm một phương án có giá nhỏ nhất. Bài toán này cũng được gọi là bài tốn người du lịch. Một cách tổng qt, có thể không tồn tại một đường đi giữa hai thành phố a và b nào đó. Trong trường hợp đó ta cho một đường đi ảo giữa a và b với độ dài bằng ∞. Bài tốn có thể biểu diễn bởi một đồ thị vơ hướng có trọng số G = V,E, trong đó mỗi thành phố được biểu diễn bởi một đỉnh, cạnh nối hai đỉnh biểu diễn cho đường đi giữa hai thành phố và trọng số của cạnh là khoảng cách giữa hai thành phố. Một chu trình đi qua tất cả các đỉnh của G, mỗi đỉnh một lần duy nhất, được gọi là chu trình Hamilton. Vấn đề là tìm một chu trình Hamilton mà tổng độ dài các cạnh là nhỏ nhất. Nguyễn Văn Linh Trang 51 Bài toán này có những ứng dụng rất quan trọng. Thí dụ một máy hàn các điểm được điều khiển bởi máy tính. Nhiệm vụ của nó là hàn một số điểm dự định ở trên một tấm kim loại. Người thợ hàn bắt đầu từ một điểm bên ngoài tấm kim loại và kết thúc tại chính điểm này, do đó tấm kim loại phải được di chuyển để điểm cần hàn được đưa vào vị trí hàn tương tự như ta đưa tấm vải vào đầu mũi kim của máy khâu. Cần phải tìm một phương án di chuyển tấm kim loại sao cho việc di chuyển ít nhất. Hình ảnh sau cho chúng ta hình dung về bài tốn đặt ra. Vị trí hàn Tấm kim loại Hình 3-2: Hàn các điểm trên một tấm kim loại Dễ dàng thấy rằng, có thể áp dụng bài toán đường đi của người giao hàng để giải bài toán này. Với phương pháp vét cạn ta xét tất cả các chu trình, mỗi chu trình tính tổng độ dài các cạnh của nó rồi chọn một chu trình có tổng độ dài nhỏ nhất. Tuy nhiên chúng ta cần xét tất cả là 2 1 - n chu trình. Thực vậy, do mỗi chu trình đều đi qua tất cả các đỉnh thành phố nên ta có thể cố định một đỉnh. Từ đỉnh này ta có n-1 cạnh tới n-1 đỉnh khác, nên ta có n-1 cách chọn cạnh đầu tiên của chu trình. Sau khi đã chọn được cạnh đầu tiên, chúng ta còn n-2 cách chọn cạnh thứ hai, do đó ta có n-1n-2 cách chọn hai cạnh. Cứ lý luận như vậy ta sẽ thấy có n-1 cách chọn một chu trình. Tuy nhiên với mỗi chu trình ta chỉ quan tâm đến tổng độ dài các cạnh chứ không quan tâm đến hướïng đi theo chiều dương hay âm vì vậy có tất cả 2 1 - n phương án. Ðó là một giải thuật thời gian mũ. Kĩ thuật tham ăn áp dụng vào đây là: 1. Sắp xếp các cạnh theo thứ tự tăng của độ dài. 2. Xét các cạnh có độ dài từ nhỏ đến lớn để đưa vào chu trình. 3. Một cạnh sẽ được đưa vào chu trình nếu cạnh đó thỏa mãn hai điều kiện sau: • Khơng tạo thành một chu trình thiếu khơng đi qua đủ n đỉnh • Khơng tạo thành một đỉnh có cấp ≥ 3 tức là khơng được có nhiều hơn hai cạnh xuất phát từ một đỉnh, do yêu cầu của bài toán là mỗi thành phố chỉ được đến một lần: một lần đến và một lần đi Nguyễn Văn Linh Trang 52 4. Lặp lại bước 3 cho đến khi xây dựng được một chu trình. 2 Với kĩ thuật này ta chỉ cần nn-12 phép chọn nên ta có một giải thuật cần On thời gian. Ví dụ 3-1: Cho bài tốn TSP với 6 đỉnh được cho bởi các tọa độ như sau: • c1,7 • d15,7 • b4,3 • e15,4 • a0,0 • f18,0 Hình 3-3: Sáu thành phố được cho bởi toạ độ Do có 6 đỉnh nên có tất cả 15 cạnh. Ðó là các cạnh: ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df và ef. Ðộ dài các cạnh ở đây là khoảng cách Euclide. Trong 15 cạnh này thì de = 3 là nhỏ nhất, nên de được chọn vào chu trình. Kế đến là 3 cạnh ab, bc và ef đều có độ dài là 5. Cả 3 cạnh đều thỏa mãn hai điều kiện nói trên, nên đều được chọn vào chu trình. Cạnh có độ dài nhỏ kế tiếp là ac = 7.08, nhưng không thể đưa cạnh này vào chu trình vì nó sẽ tạo ra chu trình thiếu a-b-c-a. Cạnh df cũng bị loại vì lý do tương tự. Cạûnh be được xem xét nhưng rồi cũng bị loại do tạo ra đỉnh b và đỉnh e có cấp 3. Tương tự chúng ta cũng loại bd. cd là cạnh tiếp theo được xét và được chọn. Cuối cùng ta có chu trình a-b-c-d-e-f-a với tổng độ dài là 50. Ðây chỉ là một phương án tốt. Phương án tối ưu là chu trình a-c-d-e-f-b-a với tổng độ dài là 48.39. Hình3-4: Phương án Greedy và phương án tối ưu Giải thuật sơ bộ như sau: PROCEDURE TSP; BEGIN {E là tập hợp các cạnh, Chu_trinh là tập hợp các cạnh được chọn để đưa vào chu trình, mở đầu Chu_trinh rỗng} {Sắp xếp các cạnh trong E theo thứ tự tăng của độ dài} Chu_Trinh := Φ; Gia := 0.0; WHILE E Φ DO BEGIN IF cạnh e có thể chọn THEN BEGIN Chu_Trinh := Chu_Trinh + [e] ; Gia := Gia + độ dài của e; Nguyễn Văn Linh Trang 53 END; E := E-[e]; END; END; Một cách tiếp cận khác của kĩ thuật tham ăn vào bài toán này là: 1. Xuất phát từ một đỉnh bất kỳ, chọn một cạnh có độ dài nhỏ nhất trong tất cả các cạnh đi ra từ đỉnh đó để đến đỉnh kế tiếp. 2. Từ đỉnh kế tiếp ta lại chọn một cạnh có độ dài nhỏ nhất đi ra từ đỉnh này thoả mãn hai điều kiện nói trên để đi đến dỉnh kế tiếp. 3. Lặp lại bước 2 cho đến khi đi tới đỉnh n thì quay trở về đỉnh xuất phát. 3.3.5 Bài tốn cái ba lơ
|
