A. GIẢI THUẬT THAM ĂN

1. Mô tả bài toán

Chúng ta sẽ xét một bài toán rất nổi tiếng có tên là bài toá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 toán người du lịch.

Một cách tổng quát, 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 toá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.

2. Một ứng dụng

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 toán đặt ra.

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.

3. Phương pháp vét cạn

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à (n-1)!/2 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-1)(n-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ả  (n-1)!/2 phương án. Ðó là một giải thuật thời gian mũ !

4. Kỹ thuật tham ăn

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:

o        Không tạo thành một chu trình thiếu (không đi qua đủ n đỉnh)

o        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)

4.       Lặp lại bước 3 cho đến khi xây dựng được một chu trình.

Với kỹ thuật này ta chỉ cần n(n-1)/2 phép chọn nên ta có một giải thuật cần O(n2) thời gian.

5. Ví dụ

Cho bài toán TSP với 6 đỉnh được cho bởi các tọa độ như sau

  • · c(1,7)                                                 · d(15,7)

    · b(4,3)                         · e(15,4)

    · a(0,0)                                                                        · f(18,0)

Do có 6 đỉnh nên có tất cả 15 cạnh. Ðó là các cạnh: abacadaeafbcbdbebfcdcecfdedf 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 abbc 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 bdcd 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.

6. Giải thuật

void TSP() {

            /*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 = F;

            Gia = 0.0;

            while (E != F) {

                        if (cạnh e có thể chọn) {

                                    Chu_Trinh = Chu_Trinh + [e];

                                    Gia = Gia + độ dài của e;

                        }

                        E := E-[e];

            }

}

7. Cách tiếp cận khác

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.

B. GIẢI THUẬT NHÁNH CẬN

1. Phân nhánh

Cây tìm kiếm phương án là cây nhị phân trong đó:

  • Nút gốc là nút biểu diễn cho cấu hình bao gồm tất cả các phương án.
  • Mỗi nút sẽ có hai con, con trái biểu diễn cho cấu hình bao gồm tất cả các phương án chứa một cạnh nào đó, con phải biểu diễn cho cấu hình bao gồm tất cả các phương án không chứa cạnh đó (các cạnh để xét phân nhánh được thành lập tuân theo một thứ tự nào đó, chẳng hạn thứ tự từ điển).
  • Mỗi nút sẽ kế thừa các thuộc tính của tổ tiên của nó và có thêm một thuộc tính mới (chứa hay không chứa một cạnh nào đó).
  • Nút lá biểu diễn cho một cấu hình chỉ bao gồm một phương án.
  • Ðể quá trình phân nhánh mau chóng tới nút lá, tại mỗi nút ta cần có một quyết định bổ sung dựa trên nguyên tắc là mọi đỉnh trong chu trình đều có cấp 2 và không tạo ra một chu trình thiếu.

2. Ví dụ:

Xét bài toán TSP có 5 đỉnh với độ dài các cạnh được cho trong hình bên dưới:

Các cạnh theo thứ tự từ điển để xét là: ab, ac, ad, ae, bc, bd, be, cd, ce và de.

Nút gốc A của cây bao gồm tất cả các phương án.

Hai con của A là B và C, trong đó B bao gồm tất cả các phương án chứa cạnh ab, C bao gồm tất cả các phương án không chứa ab, kí hiệu là .

Hai con của B là D và E. Nút D bao gồm tất cả các phương án chứa ac. Vì các phương án này vừa chứa ab (kế thừa của B) vừa chứa ac nên đỉnh a đã đủ cấp hai nên D không thể chứa ad và ae. Nút E bao gồm tất cả các phương án không chứa ac, …

Ta được cây (chưa đầy đủ) trong hình sau:

3. Tính cận dưới

Ðây là bài toán tìm min nên ta sử dụng cận dưới. Cận dưới tại mỗi nút là một số nhỏ hơn hoặc bằng giá của tất cả các phương án được biểu diễn bởi nút đó. Giá của một phương án ở đây là tổng độ dài của một chu trình.

Ðể tính cận dưới của nút gốc, mỗi đỉnh ta chọn hai cạnh có độ dài nhỏ nhất. Cận dưới của nút gốc bằng tổng độ dài tất cả các cạnh được chọn chia cho 2.

Với số liệu cho trong ví dụ trên, ta tính cận dưới của nút gốc A như sau:

  • §         Ðỉnh a chọn ad = 2, ab = 3
  • §         Ðỉnh b chọn ba = 3, be = 3
  • §         Ðỉnh c chọn ca = 4, cb = 4
  • §         Ðỉnh d chọn da = 2, dc = 5
  • §         Ðỉnh e chọn eb = 3, ed = 6
  • Tổng độ dài các cạnh được chọn là 35, cận dưới của nút gốc A là 35/2 = 17.5

Ðối với các nút khác, chúng ta phải lựa chọn hai cạnh có độ dài nhỏ nhất thỏa điều kiện ràng buộc (phải chứa cạnh này, không chứa cạnh kia).

Tính cận dưới cho nút D. Ðiều kiện ràng buộc là phải chứa ab, ac và không chứa ad, ae.

  • §         Ðỉnh a chọn ab = 3, ac = 4, do hai cạnh này buộc phải chọn.
  • §         Ðỉnh b chọn ba = 3, be = 3
  • §         Ðỉnh c chọn ca = 4, cb = 4
  • §         Ðỉnh d chọn de = 6, dc = 5, do không được chọn da nên ta phải chọn de.
  • §         Ðỉnh e chọn eb = 3, ed = 6

Tổng độ dài các cạnh được chọn là 41, cận dưới của nút D là 41/2 = 20.5

4. Áp dụng kỹ thuật nhánh cận cho bài toán TSP

Bây giờ ta sẽ kết hợp hai kỹ thuật trên để xây dựng cây tìm kiếm phương án. Quy tắc như sau:

  • Xây dựng nút gốc, bao gồm tất cả các phương án, tính cận dưới cho nút gốc.
  • Sau khi phân nhánh cho mỗi nút, ta tính cận dưới cho cả hai con.
  • Nếu cận dưới của một nút con lớn hơn hoặc bằng giá nhỏ nhất tạm thời của một phương án đã được tìm thấy thì ta không cần xây dựng các cây con cho nút này nữa (Ta gọi là cắt tỉa các cây con của nút đó).
  • Nếu cả hai con đều có cận dưới nhỏ hơn giá nhỏ nhất tạm thời của một phương án đã được tìm thấy thì nút con nào có cận dưới nhỏ hơn sẽ được ưu tiên phân nhánh trước.
  • Mỗi lần quay lui để xét nút con chưa được xét của một nút ta phải xem xét lại nút con đó để có thể cắt tỉa các cây của nó hay không vì có thể một phương án có giá nhỏ nhất tạm thời vừa được tìm thấy.
  • Sau khi tất cả các con đã được phân nhánh hoặc bị cắt tỉa thì phương án có giá nhỏ nhất trong các phương án tìm được là phương án cần tìm.

Trong quá trình xây dựng cây có thể ta đã xây dựng được một số nút lá, như ta biết mỗi nút lá biểu diễn cho một phương án. Giá nhỏ nhất trong số các giá của các phương án này được gọi là giá nhỏ nhất tạm thời.

5. Ví dụ

Xét bài toán TSP trong ví dụ trên.

Tập hợp các cạnh để xét phân nhánh là ab, ac, ad, ae, bc, bd, be, cd, ce và de. Ðiều kiện bổ sung ở đây là mỗi đỉnh phải được chọn hai cạnh, bị loại hai cạnh và không được tạo ra chu trình thiếu.

Nút gốc A bao gồm tất cả các phương án, có cận dưới là 17.5. Phân nhánh cho A, xây dựng hai con là B và C. Tính cận dưới cho hai nút này được cận dưới của B là 17.5 và C là 18.5. Nút B có cận dưới nhỏ hơn nên được phân nhánh trước. Hai con của B là D và E. Các ràng buộc của D và E giống nh-ư ta đã nói trong ví dụ của phần phân nhánh. Tính cận cho D và E, được cận dưới của D là 20.5 và của E là 18. Nút E được xét trước. Phân nhánh cho nút E theo cạnh ad, hai con của E là F và G. F chứa ad và G không chứa ad. Do F kế thừa các thuộc tính của E và B, nên F là tập hợp các phương án chứa ab, ad và không chứa ac, đỉnh a đã đủ cấp 2 vậy F không chứa ae. Tương tự G chứa ab, không chứa ac, không chứa ad nên phải chứa ae. Tính cận dưới cho F và G được cận dưới của F là 18 và của G là 23. Tiếp tục xây dựng hai con cho F theo cạnh bc là H và I. H chứa bc và I không chứa bc. Do H kế thừa các thuộc tính của B, E và F nên H là các phương án chứa ab, ad, không chứa ac và chứa bc. Như vậy đỉnh a đã thỏa điều kiện là được chọn hai cạnh (ab và ad) và bị loại hai cạnh (ac và ae), Ðỉnh b đã được chọn 2 cạnh (ba và bc) nên bd và be bị loại. Ðỉnh c đã được chọn cb, bị loại ca, ta có thể chọn cd hoặc ce. Nếu chọn cd thì sẽ có một chu trinh thiếu a b c d a, như vậy cd bị loại nên phải chọn ce.  Ðỉnh d có db và dc đã bị loại, da đã được chọn nên phải chọn thêm de. Lúc đó đỉnh e cũng đã có hai cạnh được chọn là ec và ed, hai cạnh bị loại là eb và ea. Tóm lại H là tập chỉ bao gồm một phương án a b c e d a có giá là 23.  Ðối với I ta đã có I chứa ab, không chứa ac, chứa ad, không chứa ae và không chứa bc. Bằng lý luận tương tự ta có I không chứa bd, chứa be, cd, ce và không chứa de. Một phương án mới là a b e c d a với giá 21. Ðây là giá nhỏ nhất tạm thời mới được tìm thấy.

Bây giờ ta quay lui về E và xét nút con của nó là G. Vì G có cận dưới là 23 lớn hơn giá thấp nhất tạm thời 21 nên cắt tỉa các con của G.

Quay lui về B và xét nút con D của nó. Cận dưới của D là 20.5 không lớn hơn 21. Nhưng vì độ dài các cạnh trong bài toán đã cho là số nguyên nên nếu ta triển khai các con của D tới nút lá gồm một phương án. Giá của phương án này phải là một số nguyên lớn hơn 20.5 hay lớn hơn hoặc bằng 21. Vậy ta cũng không cần xây dựng các con của D nữa.

Tiếp tục quay lui đến A và xét con C của nó. Phân nhánh C theo cạnh ac thành hai con J và K. J chứa ac có cận dưới là 18.5. K không chứa ac nên phải  chứa ad và ae, cận dưới của K là 21 bằng giá nhỏ nhất tạm thời nên cắt tỉa các con của K.

Hai con của J là L và M. M không chứa ad, ab, chứa ac và ae có cận dưới 23.5 nên bị cắt tỉa các con. Hai con của L là N và O, N chứa bc và O không chứa bc.

Xét nút N ta có: Ðỉnh a được chọn hai cạnh ac và ad, bị loại hai cạnh ab và ae. Ðỉnh b đã được chọn bc, bị loại ba, ta có thể chọn bd hoặc be. Nếu chọn bd thì sẽ có một chu trình thiếu là a c b d a, vậy phải loại bd và chọn be. Ðỉnh c đã được chọn ca, cb nên phải loại cd và ce. Ðỉnh d đã được chọn da, bị loại db và dc nên phải chọn de. Khi đó đỉnh e có đủ hai cạnh được chọn là eb, ed và hai cạnh bị loại là ea và ec. Vậy N bao gồm chỉ một phương án là a c b e d a với giá 19.

Tương tự nút O bao gồm chỉ một phương án a c e b d a có giá là 23.

Tất cả các nút con của cây đã được xét hoặc bị cắt tỉa nên phương án cần tìm là a c b e d a với giá 19.

6. Minh họa kỹ thuật nhánh cận cho bài toán TSP