Trang

Thứ Hai, 17 tháng 1, 2011

GIẢI BÀI TOÁN NGƯỜI DU LỊCH NỔI TIẾNG BẰNG MÔ PHỎNG HÀNH VI CỦA ĐÀN KIẾN TRONG TỰ NHIÊN

Bài toán Người du lịch (Travelling Salesman Problem) là một trong những bài toán kinh điển và khó trong tin học. Có rất nhiều cách tiếp cận giải bài toán này ngay từ khi nó mới ra đời, như sử dụng quy hoạch tuyến tính, nhánh và cận (đã được đăng trên Tin học và Nhà trường), nhưng mới chỉ dừng lại ở các bộ dữ liệu nhỏ. Gần đây các cách tiếp cận về tiến hóa, như thuật toán di truyền được áp dụng có những kết quả khả quan hơn.
Trong bài này, chúng tôi xin được phép giới thiệu một phương pháp độc đáo dựa vào mô phỏng hành vi của đàn kiến thực với quá trình tha thức ăn về tổ trong tự nhiên để giải bài toán tìm đường đi ngắn nhất cho người du lịch. Đây là phương pháp tương đối khó so với trình độ Tin học của học sinh phổ thông, nên trong bài viết chúng tôi nhấn mạnh vào ý tưởng, và hướng dẫn cài đặt, cũng như trình bày một cách đơn giản nhất. Các tác giả hy vọng qua bài viết, các em học sinh yêu Tin học nói chung và các em học sinh khối phổ thông chuyên Tin nói riêng có được một các nhìn khác với các cách giải truyền thống bài toán này.


1. Nhắc lại bài toán Người du lịch 

Bài toán Người du lịch, tìm đường đi ngắn nhất cho người thương nhân (salesman), hay còn gọi là người chào hàng xuất phát từ một thành phố, đi qua lần lượt tất cả các thành phố duy nhất một lần và quay về thành phố ban đầu với chi phí rẻ nhất, được phát biểu vào thế kỷ 17 bởi hai nhà toán học vương quốc Anh là Sir William Rowan Hamilton và Thomas Penyngton Kirkman, và được ghi trong cuốn giáo trình Lý thuyết đồ thị nổi
tiếng của Oxford. Nó nhanh chóng trở thành bài toán khó thách thức toàn thế giới bởi độ phức tạp thuật toán tăng theo hàm số mũ (trong chuyên ngành thuật toán người ta còn gọi chúng là những bài toán NP-khó). Người ta bắt đầu thử và công bố các kết quả giải bài toán này trên máy tính từ năm 1954 (49 đỉnh), cho đến năm 2004 bài toán giải được với số đỉnh lên tới 24.978, và dự báo sẽ còn tiếp tục tăng cao nữa. Bài toán có thể phát biểu dưới ngôn ngữ đồ thị như sau :
Cho đồ thị n đỉnh đầy đủ và có trọng số G=(V-tập đỉnh,E-tập cạnh) có hoặc vô hướng. Tìm chu trình Halmilton
có tổng trọng số
là nhỏ nhất.
>
2. Ý tưởng mô phỏng hành vi của đàn kiến thực trong tự nhiên

Năm 1989, nhà bác học người Đan Mạnh Deneubourg và các cộng sự công bố kết quả nghiên cứu về thí nghiệm trên đàn kiến Argentina (một loài kiến hiếm trên thế giới), gọi là thí nghiệm “Chiếc cầu đôi” (Double Bridge Experiment).
Cụ thể, họ đã đặt một chiếc cầu đôi gồm hai nhánh (nhánh dài hơn có độ dài bằng hai lần nhánh ngắn hơn, như hình vẽ) nối tổ của đàn kiến với nguồn thức ăn, sau đó thả một đàn kiến và bắt đầu quan sát hoạt động của chúng trong một khoảng thời gian đủ lớn. Kết quả là ban đầu các con kiến đi theo cả hai nhánh của chiếc cầu với số lượng gần như ngang nhau, nhưng càng về cuối thời gian quan sát người ta nhận thấy các con kiến có xu hướng chọn nhánh ngắn hơn để đi (80-100% số lượng).

Kết quả được các nhà sinh học lý giải như sau : Do đặc tính tự nhiên và đặc tính hóa học, mỗi con kiến khi di chuyển luôn để lại một lượng hóa chất gọi là các vết mùi (pheromone trail) trên đường đi và thường thì chúng sẽ đi theo con đường có lượng mùi đậm đặc hơn. Các vết mùi này là những loại hóa chất bay hơi theo thời gian, do vậy ban đầu thì lượng mùi ở hai nhánh là xấp sỉ như nhau, nhưng sau một khoảng thời gian nhất định nhánh ngắn hơn sẽ có lượng mùi đậm đặc hơn so với nhánh dài hơn do cũng lượng mùi gần xấp sỉ như nhau khi phân bố ở nhánh dài hơn mật độ phân bố mùi ở nhánh này sẽ không dày bằng nhánh có độ dài ngắn hơn, thêm nữa cũng do lượng mùi trên nhánh dài hơn cũng sẽ bị bay hơi nhanh hơn trong cùng một khoảng thời gian.

Năm 1991, với cơ sở là kết quả của thí nghiệm nổi tiếng trên, nhà khoa học người Bỉ Marco Dorigo đã xây dựng thuật toán đàn kiến (Ant Algorithm, hay còn gọi là Hệ kiến, Ant System)
đầu tiên ứng dụng vào giải bài toán người du lịch, và công bố trong luận án tiến sĩ của ông. Trong bài báo này, các tác giả muốn giới thiệu về thuật toán cơ bản Ant-Cycle (thuật toán nổi tiếng và hiệu quả nhất trong lớp các thuật toán Hệ kiến) được công bố năm 1996 trên tạp chí lý thuyết của IEEE (Institute of Electrical and Electronics Engineers, là hiệp hội nghiên cứu công nghệ và khoa học hàng đầu thế giới). Hiện nay, Dorigo và các cộng sự đã xây dựng được nhiều hệ kiến phức tạp hơn ứng dụng trong nhiều bài toán khó hơn và có nhiều ý nghĩa khoa học và thực tiễn hơn, nhưng với khuôn khổ và phạm vi của bài báo là giành cho học sinh phổ thông, chúng tôi xin được phép không trình bày ở đây, bạn đọc quan tâm có thể tìm đọc trong các tài liệu tham khảo có ở phần cuối của bài báo.

3. Thuật toán đàn kiến giải bài toán người du lịch


Để bắt chước hành vi của các con kiến thực, Dorigo xây dựng các con kiến nhân tạo (artificial ants) cũng có đặc trưng sản sinh ra vết mùi để lại trên đường đi và khả năng lần vết theo nồng độ mùi để lựa chọn con đường có nồng độ mùi cao hơn để đi. Với bài toán Người du lịch trên đồ thị trong không gian hai chiều với trọng số là khoảng cách Euclide giữa hai đỉnh bất kỳ, Dorigo gắn với mỗi cạnh (i, j) ngoài trọng số d(i, j) trên là nồng độ vết mùi trên cạnh đó, đặt là . Ban đầu, các nồng độ mùi trên mỗi cạnh được khởi tạo bằng một hằng số c nào đó.

Phương pháp tìm đường đi mô phỏng hành vi con kiến
Các con kiến sẽ tiến hành tìm đường đi từ đỉnh xuất phát qua một loạt các đỉnh và quay trở về đỉnh ban đầu, tại đỉnh u một con kiến sẽ chọn đỉnh v chưa được đi qua trong tập láng giềng của u theo xác suất sau :
trong đó

- UV(u) là tập các đỉnh láng giềng của u chưa được con kiến hiện tại đi qua.
gọi là thông tin heurtistic giúp đánh giá chính xác hơn sự lựa chọn của con kiến khi quyết định đi từ đỉnh u qua đỉnh v.


Ta có thể hiểu công thức trên đơn giản như sau : quyết định lựa chọn đỉnh tiếp theo để đi của con kiến được lựa chọn ngẫu nhiên theo xác suất (tức là đỉnh nào có xác suất cao hơn sẽ có khả năng được chọn cao hơn, nhưng không có nghĩa là các đỉnh có xác suất thấp hơn không được chọn mà nó được chọn với cơ hội thấp hơn mà thôi). Ý tưởng này được thể hiện qua kỹ thuật Bánh xe xố số (Lottery Wheel) sẽ được trình bày sau. Và xác suất này (hay khả năng chọn đỉnh tiếp theo của con kiến) tỷ lệ thuận với nồng độ vết mùi trên cạnh được chọn (theo đặc tính của con kiến tự nhiên) và tỷ lệ nghịch với độ dài cạnh, là những hệ số điểu khiển việc lựa chọn của con kiến nghiêng về phía nào.

Kỹ thuật bánh xe xổ số
Đây là kỹ thuật phổ biến hay sử dụng trong các phương pháp tìm kiếm dựa vào xác suất, đặc biệt trong phép toán Chọn lọc (Selection) của thuật toán di truyền (Genetic Algorithm). Cụ thể kỹ thuật như sau :

Giả sử V={v1,v2, …, vn} là tập các láng giềng của u, p1, p2, …, pn là xác suất lựa chọn đỉnh tiếp theo từ u của tương ứng v1,v2, …, vn
tức là chắc chắn chọn 1 trong các đỉnh trên để đi tiếp. Để đảm bảo ưu thế của những đỉnh có xác suất lớn, nhưng vẫn đảm bảo cơ hội của các đỉnh có xác suất thấp hơn người ta sinh ra một số ngẫu nhiên k (0, sum] rồi chọn i nhỏ nhất sao cho Cách làm này mô phỏng hoạt động của một vòng quay xổ số (vòng được chia làm nhiều phần không bằng nhau), rõ ràng khi quay ta không biết kim của bánh quay sẽ chỉ vào phần nào nhưng ta cũng có thể nhận thấy ngay là phần lớn hơn sẽ nhiều khả năng kim rơi vào đó hơn. Chính vì vậy kỹ thuật này được gọi là Bánh xe xổ số.
Như vậy, các con kiến từ một đỉnh xuất phát, lần lượt tới thăm các đỉnh tiếp theo theo quy tắc trên (thăm xong đánh dấu chúng lại) cho đến thăm tới đỉnh cuối cùng và quay về đỉnh ban đầu, kết thúc một hành trình. Quá trình này được lặp đi lặp lại, hành trình tốt hơn (có chiều dài ngắn hơn) sẽ được cập nhật cho đến một khoảng thời gian đủ tốt (thông thường tính toán theo số vòng lặp, với các trường hợp nhỏ (số đỉnh <=200) số vòng lặp bằng 500 là đủ tìm ra kết quả tối ưu, còn với các trường hợp lớn hơn ta phải thử với số lần lặp lớn hơn nhiều, tùy thuộc vào từng bộ dữ liệu cụ thể.

Sau khi và trong quá trình các con kiến tìm đường đi các vết mùi ( ) được cập nhật lại, vì chúng bị biến đổi do quá trình bay hơi và do quá trình tích lũy của các con kiến trên cạnh đó. Có rất nhiều cách cập nhật mùi, mỗi cách có ảnh hưởn nhất định đến chất lượng của thuật toán. Trong phạm vi kiến thức phổ thông, chúng tôi giới thiệu cách cập nhật mùi đơn giản nhất như sau :

Sau mỗi vòng lặp (các con kiến đều tìm được hành trình riêng của mình), vết mùi trên mỗi cạnh được cập nhật lại theo công thức sau :
trong đó gọi là tham số bay hơi (sở dĩ gọi như vậy vì sau mỗi lần cập nhật lượng mùi trên cạnh (i,j) sẽ mất đi một lượng là  thường được chọn là 0,8 trong cài đặt và chạy chương trình. Ngoài lượng bay hơi mất đi đó mỗi cạnh (i, j) còn được tích tụ thêm một lượng mùi  nhất định tùy thuộc vào từng con kiến đi qua, cụ thể được tính như sau :
trong đó Q là một hằng số, Lk là độ dài hành trình của con kiến thứ k.
Nhờ việc cập nhật mùi này, sau mỗi vòng lặp (hay sau mỗi lần các con kiến đi hết hành trình), nồng độ vết mùi trên các cạnh sẽ thay đổi (hoặc giảm hoặc tăng dần) ảnh hưởng đến quyết định chọn của các con kiến, có thể ở bước lặp này chọn một cạnh để đi nhưng đến bước lặp khác vẫn con kiến đó lại không đi qua cạnh đó nữa. Nhờ vậy thuật toán có khả năng tìm được lời giải tốt trong những trường hợp dữ liệu cực lớn.

4. Hướng dẫn cài đặt bằng ngôn ngữ PASCAL



Cấu trúc dữ liệu
D[1..N, 1..N] : mảng số thực hai chiều lưu độ dài các cạnh.

T[1..N, 1..N] : mảng số thực hai chiều lưu nồng độ vết mùi trên các cạnh.

Delta[1..N, 1..N] : mảng số thực hai chiều lưu sự cập nhật mùi.

W[1..N] : mảng số nguyên một chiều lưu hành trình của mỗi con kiến.

Mark[1..N] : mảng boolean một chiều đánh dấu đỉnh đã thăm.

UV[1..N-1] : mảng số nguyên 1 chiều lưu các đỉnh chưa thăm của con kiến.
	

Các thủ tục đặc tả 

Procedure Init;
Begin For i := 1 to n-1 do For j :=i+1 to n do Begin T[i,j] := c; {c là một hằng số thường lấy bằng 0.5} Delta[i,j] := 0; T[j,i] := T[i,j]; Delta[j,i] := Delta[i,j]; End; N_Loop := 0; {đếm số vòng lặp hiện tại} L_Best := MaxReal; {biến số thực đủ lớn} End; Procedure Lottery_Wheel (Var k : Integer); Begin sum := 0; dem := 0; Fillchar(UV, Sizeof(UV), 0); For i:= 1 to n do If (Not Mark[i]) then Begin sum := sum+p[i]; {sum là biến tổng các xác suất} Inc(dem); UV[dem] := i; End; k := random(sum); t := 0; i=1; While (t Begin t=t+p[UV[i]]; End; k := UV[i]; End; Procedure Pheromone_Update; Begin For i:=1 to N-1 do For j:=i+1 to N do Begin T[i,j] := rho*T[i,j] + Delta[i,j];{rho thường được chọn bằng 0.8} T[j,i] := T[i,j]; End; End; Procedure Ant_Cycle; Begin Init; Repeat Inc(N_Loop); For i:= 1 to M do {M là số con kiến, thường chọn bằng 25} Begin W[1] := 1; {Giả sử đỉnh xuất phát là 1 cho tất cả các con kiến} Fillchar(Mark, Sizeof (Mark), False); Mark[1] := True; L := 0; {L là độ dài hành trình của con kiến i} For j:= 2 to N do Begin Lottery_Wheel(W[j]); L := L + D[W[j-1], W[j]]; Mark[W[j]] := True; End; End; L := L+D[W[N], W[1]]; If (L Begin L_Best := L; Luu_duong_di := W; {Luu_duong_di là mảng lưu kết quả} End; For i:=1 to N-1 do For j:=i+1 to N do Begin Delta[i,j] := Delta[i,j] + Q/L; Delta[i,j] := Delta[j,i]; End; End; Pheromone_Update; Until (N_Loop < N_C); {N_C là tổng số vòng lặp sẽ chạy, phụ thuộc từng bộ dữ liệu} End;

Tài liệu tham khảo
[1] M.Dorigo and T.Stuzle. Ant Colony Optimization. Nhà xuất bản MIT, Tháng 7/2004.
[2] Đinh Quang Huy, Đỗ Đức Đông và Hoàng Xuân Huấn. “Multi-level Ant System : A new approach through the new pheromone update of Ant Colony Optimization. Kỷ yếu Hội nghị quốc tế Khoa học máy tính RIVF lần thứ 4, tp.Hồ Chí Minh, Tháng 2/2006.
[3] Từ điển Wikipedia tiếng Anh http://en.wikipedia.org/wiki/ 
[4] Website về bài toán Người du lịch http://www.tsp.gatech.edu/index.html 
[5] Dữ liệu thử: www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ 
Tác giả: Đinh Quang Huy

PHƯƠNG PHÁP KHỬ ĐỆ QUY ĐẶC BIỆT

Một số bài toán giải bằng phương pháp đệ quy cho ta lời giải rất gọn và có thể ra được lời giải. Những bài toán giải bằng đệ quy truyền thống như: THÁP HÀ-NỘI, bà toán 8-HẬU, bài toán MÃ ĐI TUẦN, ... Tuy nhiên phương pháp đệ quy khi áp dụng chỉ giải được những bài toán với cấu trúc dữ liệu nhỏ thường là với N<30 (hay NxN < 30x30). Vì vậy bài toán đặt ra là có thể giải quyết những bài toán như trên với dữ liệu lớn được hay không? Ví dụ như: bài toán MÃ ĐI TUẦN và THÁP HÀ-NỘI với bàn cờ cỡ 80x80 hay không? Xin trình bày một số phương pháp khử đệ quy để giải quyết những bài toán đệ quy truyền thống.

1. Bài toán MÃ ĐI TUẦN:

Trên bàn cờ NxN (với 5<=N<=100) đặt một quân mã tại một vị trí bất kỳ. Hãy tìm cách cho mã nhảy theo luật nhảy của quân mã và nhảy hết tất cả các ô trên bàn cờ đó, mỗi ô chỉ nhảy vào đúng một lần.

2. Phân tích và xây dựng chương trình:

Khi quân mã nhảy hết tất cả các ô trên bàn cờ, và tại ô cuối cùng quân mã có thể nhảy về vị trí của ô xuất phát chính là một chu trình Euler (Nhảy qua tất cả các ô, mỗi ô đúng một lần và nhảy về vị trí xuất phát). Còn nếu vị trí cuối cùng không thể nhảy về vị trí xuất phát được chính là một đường đi Euler. Ta thử tìm cách bài toán tìm đường đi Euler qua tất cả các ô của bàn cờ theo luật nhảy của quân mã, mỗi ô chỉ nhảy vào một lần.
a. Phương pháp đệ quy truyền thống:
Với phương pháp đệ quy cho bài mã đi tuần này đã có nhiều bài báo đề cập và có nhiều cải tiến như số 6-2003, số 7-2003. Tuy nhiên chỉ giải quyết được với N<30. Xin nhắc lại sơ phương pháp truyền thống như sau:

Từ vị trí xuất phát trên bàn cờ NxN ta gán giá trị là 1, theo luật nhảy của quân mã có tối đa là 8 vị trí kế tiếp để quân mã nhảy tới theo luật nhảy. Ta lần lượt kiểm tra 8 vị trí này xem vị trí đó có nằm trong bàn cờ hay không, quân mã đã nhảy đến ô này hay chưa nếu chưa nhảy đến và ô này nằm trong bàn cờ thì nhảy vào ô này. Sau đó dùng đệ quy để tiếp tục quá trình trên cho đến khi quân mã nhảy hết tất cả các ô.
b. Phương pháp mới :“xử lý những đoạn gen” 

i. Mô tả: 

Ta để ý rằng đáp án của bài toán là mội chuỗi những bước nhảy liên tiếp qua hết tất cả các ô trên bàn cờ giống như một “đoạn gen” duy nhất gồm nhiền “nhiễm sắc thể” nối tiếp nhau. Các nhiễm sắc thể tức là các ô của bàn cờ. Hai nhiễm sắc thể liên tiếp được nối với nhau nếu thỏa mãn luật nhảy của quân mã . Như vậy ta có thể đưa bài toán về một bài toán khác là từ những “nhiễm sắc thể” đơn lẻ hãy tìm cách ghép nối chúng lại với nhau sao cho tạo thành một “đoạn gen” duy nhất.

Ví dụ: Ta xem đáp án của bàn cờ 5x5 và “đoạn gen” hoàn chỉnh:
ii. Định nghĩa các thuật ngữ: 

1. Nhiễm sắc thể: là một ô trên bàn cờ NxN

2. Đoạn gen: là một chuỗi gồm một hoặc nhiều nhiễm sắc thể liên tiếp nhau.Hai nhiễm sắc thể liên tiếp nhau trong một đoạn gen thỏa mãn luật nhảy của quân mã. Mỗi đoạn gen sẽ có đầu và đuôi, đoạn gen gồm duy nhất một nhiễm sắc thể thì đầu và đuôi là một.
(hình trên gồm 7 đọan gen có đầu là các ô tô đậm)
3. Nối gen: Ta nối đầu (hay đuôi) của đoạn gen A vào đầu (hay đuôi) của đoạn gen B tạo thành đoạn C thỏa mãn C là một đoạn gen có các nhiễm sắc thể là các nhiễm sắc thể từ đoạn gen A và đoạn gen B.
4. Trộn gen: Ta trộn gen A vào trong gen B như sau: Từ đầu và đuôi của đoạn gen A ta nối vàotại một bước nhảy nào đó của đoạn gen B tạo thành đoạn C thỏa mãn đoạn C là một đoạn gen có các nhiễm sắc thể là các nhiễm sắc thể từ A và B.
5. Cắt gen: Cắt hai đoạn gen A và đoạn B tạo thành hai đoạn gen C và đoạn gen D như sau: ta tìm trên đoạn gen B vị trí để có thể nối đầu (hay đuôi) của đoạn gen A vào và tạo thành đoạn gen C. Phần còn lại của đoạn gen B sẽ bị cắt ra ngoài tạo thành đoạn gen D.
iii. Chứng minh quy tắc: 

Với ba công cụ biến đổi những đoạn gen như trên: nối gen, trộn gen và cắt gen ta chứng minh rằng sẽ luôn tìm ra lời giải cho bài toán đặt ra: nối các nhiễm sắc thể riêng lẻ lại và tạo thành một đoạn gen duy nhất

Ta thấy rằng với phương pháp nối gen, từ hai đoạn gen A và đoạn gen B ban đầu sau khi nối tạo thành đoạn gen C chứa các nhiễm sắc thể có trong A và B. Như vậy số đoạn gen sau khi thực hiện một phép nối sẽ giảm đi một đoạn.

Trộn đoạn gen A vào đoạn gen B tạo thành đoạn gen C chứa các nhiễm sắc thể có trong A và B. Nên sau khi thực hiêm một phép trộn gen số đoạn gen sẽ giảm đi một đoạn.

Với phép cắt gen, đoạn gen A cắt vào đoạn gen B, tạo thành đoạn gen C và đoạn gen D trong đó đoạn gen C và đoạn gen D chứa các nhiễm sắc thể của đoạn gen A và đoạn gen B. Như vậy số đoạn gen sau khi thực hiện phép cắt gen sẽ không đổi (nhưng nó sẽ tạo ra những trường hợp mới để có thể thực hiện hai phép nối gen và trộn gen.

Vì quân mã tại một vị trí bất kỳ trên bàn cờ có tối thiểu là 2 cách chọn cho bước nhảy kế tiếp nên ta luôn luôn tồn tại hai cặp gen nào đó mà chúng có thể cắt nhau được.

Từ đó ta có thể kết luận rằng số đoạn gen ban đầu N*N đoạn sau nhiều lần biến đổi gen (dùng lần lượt ba phép biến đổi trên) sẽ tạo thành một đoạn gen duy nhất chính là lời giải ta cần tìm.
iv. Tiến hành xây dựng chương trình 

Bước 1: Chuyển N*N ô bàn cờ vào các đoạn ghen ta sẽ được N*N đoạn ghen. Mỗi đoạn ghen có chiều dài là 1.

Bước 2: Thược hiện các phép “nối ghen”, “trộn gen” và “cắt gen” cho đến khi chỉ còn một đoạn gen duy nhất. Đoạn gen này có chiều dài là N*N chính là đáp án của bài toán.

Tuy nhiên để tiết kiệm bộ nhớ ta có thể thực hiện theo các sau : Ngay từ khi khởi tạo ta dùng phương pháp đệ quy truyền thống nhưng chỉ cho chương trình đệ quy tới giá trị N*(N-1), sau đó mới áp dụng phương pháp xử lý các đoạn gen như sau.

Bước 1. Ban đầu ta dùng cách đệ quy truyền thống cho mã nhảy đến một giá trị là N*(N-1) thì dừng lại. (Còn lại N ô chưa điền)

Bước 2. Lần lượt điền những ô chưa điền với những giá tri tăng dần N*(N-1)+1, N*(N-1)+2,... đến N*N thì dừng lại (nhu vậy tất cả các ô đều được điền nhưng không đúng luật nhảy của quân mã).

Bước 3. Biến đổi mảng mảng 2 chiều đã điền thành các đoạn gen

Bước 4. Sau đó ta phân tích bàn cờ hai chiều (đã đánh số từ 1=>NxN) thành các đoạn gen.

Bước 5. Tiến hành xử lý các đoạn gen dùng lần lượt 3 công cụ “nối gen”, “trộn gen” và “cắt gen” để nối các đọan gen thành một đoạn gen duy nhất.

Bước 6. Xuất kết quả ra file.

Chương trình minh họa được viết bằng ngôn ngữ Pascal (Free Pascal Compiler Version 1.0.4) load trên trang web: http://www.freepascal.org/
Khi viết trong Free Pascal bộ nhớ có thể mở rộng phù hợp cho việc khai báo của bài toán trên.

Chương trình viết bằng ngôn ngữ Visual C (cho phép N<=87) vớn ngôn ngữ Free Pascal (N<=80 có thể khai báo maxN=90 nhưng khi khởi động có thể hơi lâu).
v. Những lưu ý khi khi xây dựng chương trình 

Khi “nối gen” và “trộn gen” không thể thực hiện được nữa chương trình thường chạy “cắt gen”. Sau khi đoạn gen A cắt đoạn gen B và sinh ra đoạn gen C và gen D thì ta phải đảo ngược đoạn gen C này để tránh trường hợp đoạn gen C lại cắt đoạn gen D sẽ sinh ra đoạn gen A và B thì chương trình sẽ bị lặp.

Tuy nhiên ta không thể dự đoán trước được có những trường hợp bị lặp đặc biệt nào đó nên cách giải quyết tốt nhất là khi đoạn gen A cắt đoạn gen B ta tìm hết các vị trí cắt trên B mà A có thể cắt (tối đa là 8 vị trí), nếu có vị trí cắt ta lấy ngẫu nhiên một vị trí trên B trong các vị trí có thể đó để làm điểm cắt. Như thế chương trình sẽ tránh được những trường hợp lặp đặc biệt nào đó.
vi. Đánh giá và mở rộng bài toán: 

- Với chương trinh đệ quy truyền thống cũng như đệ quy có tri thức (thuật tóan Warnsdorff) thì chỉ giải quyết đuợc vói những bàn cờ kích thước nhỏ và thời giai đưa ra kết quả khá lâu. Không những thế một số vị trí xuất phát và hướng nhảy của quân mã trên bàn cờ có thể sẽ đưa ra lời giải trong thời gian khá lâu cho dù N bé vì đệ quy chính là “vét cạn” các trường hợp nếu đáp án nằm ở vị trí cuối của các lần lặp đệ quy ban đầu.

- Với cách giải quyết qua các “đoạn gen” khắc phục được những điểm yếu của đệ quy truyền thống. Kích thước của bàn cờ có khả năng đạt đến là 87x87 khi sử dụng mảng lưu trữ tĩnh. Kích thức của bàn cờ có thể lớn hơn nữa nếu tổ chức dữ liệu bằng danh sách liên kết.

3. Bài tập:

1. Lập trình giải bài toán tìm đường đi Euler dùng cách “xử lý các đoạn gen” như trên dùng cấu trúc lưu trữ mảng tĩnh.

2. Lập trình giải bài toán tìm đường đi Euler (hay bài MÃ ĐI TUẦN) dùng cách “xử lý các đoạn gen” như trên dùng cấu trúc lưu trữ mảng động.

4. Tài liệu tham khảo:

Giáo trình trí tuệ nhân tạo – Cấu trúc dữ liệu + thuật giải di truyền = Lập trình tiến hóa Ts. Nguyễn Đình Thúc (NXB LĐ-XH)



URL của bài viết này::http://www.schoolnet.vn/modules.php?name=News&file=article&sid=4389

© Cong ty Cong Nghe Tin hoc Nha truongcontact: schoolnet@vnschool.net

Học thuật toán qua các bài toán

Học tập thuật toán là một trong những yêu cầu cơ bản để trở thành các lập trình viên. Đối với các sinh viên ngành tin học và những ai yêu thích lập trình, việc học thuật toán còn là một thú vui, giúp nâng cao tư duy logic và làm phong phú thêm kiến thức về việc xây dựng các giải thuật cho các bài toán mới. Trong bài báo nhỏ này tôi xin đưa ra một số bài toán nhỏ, để qua đó trình bày một số thuật toán khá tinh tế để giải quyết chúng, mong rằng bài báo sẽ mang lại cho các bạn độc giả những điều thú vị.

Bài toán 1: Cho một dãy số nguyên a có N phần tử và một số nguyên k. Hãy xác định xem trong dãy a có tồn tại hai số nguyên a[i] và a[j] sao cho k là trung bình cộng của a[i] và a[j] (i≠j).
Bài toán này còn có thể chuyển thành bài toán tìm xem có tồn tại hai phần tử a[i], a[j] mà k là hiệu của chúng không.
Thuật toán dành cho bài toán 1 cũng không có gì quá phức tạp, chỉ cần hai vòng lặp lồng nhau, một dành cho chỉ số i và một dành cho chỉ số j (chạy từ 0 tới N-1) sau đó trong thân của hai vòng lặp này ta kiểm tra điều kiện a[i] + a[j] = 2*k hay không. Đoạn chương trình cài đặt cụ thể như sau:
Các bạn có thể dễ dàng nhận thấy thuật toán trên có độ phức tạp . Tuy nhiên xem xét kỹ hơn một chút chúng ta thấy rằng có thể cải tiến để nhận được thuật toán tốt hơn cho bài toán 1. Để ý vòng lặp thứ 2 với chỉ số j chính là áp dụng của thuật toán tìm kiếm tuyến tính đối với dãy a (điều kiện tìm kiếm là tìm xem có tồn tại a[i], a[j] thỏa mãn điều kiện của bài toán 1 hay không), nên chúng ta có thể thay bằng thuật toán tìm kiếm nhị phân với độ phức tạp . Thay vì tìm điều kiện tồn tại a[i]+a[j] == 2*k, chúng ta sẽ tìm xem có tồn tại chỉ số j mà a[j] = 2*k – a[i] hay không, cụ thể nếu 2*k – a[i] > a[i] thì chúng ta sẽ tìm trên mảng a[i+1..N-1] còn nếu 2*k – a[i] < a[i] thì ta sẽ tìm trên mảng a[0..i-1]. Để có thể thực hiện thuật toán tìm kiếm nhị phân chúng ta sẽ sắp xếp dãy a trước khi tiến hành tìm kiếm, thuật toán sắp xếp được chọn ở đây sẽ là thuật toán quick sort, có độ phức tạp là  . Vòng lặp đối với chỉ số i có độ phức tạp là  nên đoạn thuật toán tìm kiếm sẽ có độ phức tạp là  và do đó thuật toán cuối cùng sẽ có độ phức tạp là . Cài đặt cụ thể của thuật toán như sau:
Về hàm qsort() của C/C++ các bạn có thể tra thêm với Turbo C 3.0 để biết thêm chi tiết, ở đây chúng ta chỉ cần chú ý là khi gọi tới hàm này cần có một hàm trợ giúp làm nhiệm vụ so sánh các phần tử trong dãy cần sắp, và khi gọi hàm cần chỉ rõ kích thước của một phần tử quan toán tử sizeof của C/C++.
Bài toán 2: Hãy viết chương trình in ra tất cả các số nguyên tố có hai chữ số.
Có thể nói đây là một bài toán khá đơn giản, chỉ cần có một hàm kiểm tra tính nguyên tố (các bạn có thể tham khảo bài viết Số nguyên tố của tôi để biết thêm về thuật toán kiểu này), sau đó chạy một vòng lặp với các số có hai chữ số là xong.Tuy nhiên sẽ là thế nào nếu như đề bài có thêm yêu cầu xây dựng thuật toán tốt nhất cho bài toán trên. Chúng ta sẽ đi tìm một thuật toán tốt hơn ý tưởng sử dụng hàm kiểm tra tính nguyên tố của mỗi số nguyên.
Có thể nhận thấy rằng các số nguyên tố có hai chữ số (hay bất cứ số nguyên tố nào lớn hơn 10) đều chữ số cuối thuộc tập {1, 3, 7, 9}. Lại do các số nguyên tố cần tìm đều là các số nhỏ hơn 100 (có hai chữ số) nên chúng chỉ có thể có các ước số nguyên tố nhỏ hơn 10, hay chính xác là chỉ có thể là 3 hoặc 7 (không có 2, 5). Vậy ta chỉ cần tạo ra các số có hai chữ số mà đảm bảo chúng có chữ số kết thúc thuộc tập {1, 3, 7, 9} và kiểm tra xem chúng có chia hết cho 3 và 7 không là đủ. Đoạn chương trình cài đặt cụ thể của thuật toán là:
Bài toán 3 (bài toán tìm điểm yên ngựa của ma trận): Cho một ma trận kích thước NxM (N hàng, M cột). Hãy tìm xem trên ma trận có tồn tại phần tử a[i][j] nào vừa là phần tử nhỏ nhất của hàng i, lại vừa là phần tử lớn nhất của cột j hay không.
Đây có lẽ là một bài toán khá quen thuộc với đa số các bạn độc giả đã học về cấu trúc dữ liệu và giải thuật. Thuật toán để giải quyết bài toán cũng khá đơn giản: ta sử dụng hai vòng lặp cho các chỉ số hàng (i) và cột (j), với mỗi phần tử a[i][j] đó ta sẽ tìm phần tử nhỏ nhất của hàng i, gọi là x, tìm phần tử lớn nhất của cột j, gọi là y, cuối cùng so sánh xem x, y và a[i][j] có bằng nhau hay không để đi đến kết luận a[i][j] có là phần tử yên ngựa hay không (kết quả là có nếu a[i][j] bằng x, và bằng y). Việc tìm x sẽ tiến hành với M phần tử của hàng i, việc tìm y sẽ tiến hành với N phần tử của cột j nên thuật toán sẽ có độ phức tạp là  . N*M tương ứng với hai vòng lặp của biến i và biến j. Thuật toán này có thể cải tiến nếu chúng ta nhận thấy rằng: việc tìm các giá trị x (có N giá trị x như vậy, do có N hàng), giá trị y (có M giá trị y như vậy) trong thân vòng lặp tương ứng của các biến i, j là chưa tối ưu. Chúng ta có thể tìm N giá trị nhỏ nhất của các hàng và lưu vào mảng minh[0..N-1], thuật toán tương ứng sẽ có độ phức tạp là  , do ta tìm N lần, mỗi lần tìm trong một hàng có M phần tử. Tương tự chúng ta sẽ tìm các phần tử lớn nhất của các cột và lưu vào mảng maxc[0..M-1], thuật toán này cũng có độ phức tạp là  . Cuối cùng trong vòng lặp với các biến i, j chúng ta chỉ cần so sánh a[i][j] với minh[i] và maxc[j], nếu ba số này bằng nhau thì a[i][j] chính là một phần tử yên ngựa. Thuật toán cải tiến cho bài toán 3 này có độ phức tạp  , tất nhiên là tốt hơn so với thuật toán ban đầu có độ phức tạp  .
Việc cài đặt cụ thể thuật toán này xin dành lại như là một bài tập cho các bạn độc giả.
Bài toán 4 (bài toán số trung bình): Cho một dãy các số nguyên a1, a2, … , aN. Một phần tử akđược gọi là phần tử trung bình của dãy đã cho nếu tồn tại hai phần tử ai, aj (i≠j) sao cho ak = (ai + aj)/2. Chẳng hạn với dãy số 3, 7, 10, 22, 17, 15 ta có (a1 + a5)/2 = 10 = a3 nên a3 là một phần tử trung bình. Nhưng dãy 3, 8, 11, 17, 30 lại không có phần tử trung bình nào.
Hãy viết chương trình đếm số phần tử trung bình của một dãy cho trước có N phần tử (N ≤ 10000).
Về thực chất đây là một bài toán khá giống với bài toán 1, nhưng các bạn cần để ý tới điều kiện của N (N ≤ 10000) để tránh dẫn tới sử dụng một thuật toán sai (không chạy hết được các test của bài toán).
Lời giải đơn giản cho bài toán có độ phức tạp là  , lời giải này hoàn toàn trực tiếp đối với lời phát biểu của bài toán:
Vòng lặp kiểm tra tồn tại j và k cần N*N bước thực hiện (cần kiểm tra tất cả các cặp để xem a[i] có là trung bình cộng của cặp đó không). Do đó độ phức tạp của thuật toán sẽ là  . Lời giải này có thể qua được khoảng 30% số test của bài toán, đo điều kiện về biến N.
Tuy nhiên chúng ta có thể đạt được hiệu quả lớn hơn nhiều so với lời giải trên. Chúng ta có thể xác định được một phần tử nào đó có là trung bình cộng của hai phần tử khác không bằng một thuật toán có độ phức tạp  thay vì thuật toán có độ phức tạp  . Quan sát đầu tiên cho chúng ta nhận xét: nếu a[i] là trung bình cộng của a[j] và a[k] thì trong 2 số a[j], a[k] sẽ có một số nhỏ hơn hoặc bằng a[i], số còn lại sẽ lớn hơn hoặc bằng a[i].
Giả sử dãy số của chúng ta đã được sắp theo thứ tự không giảm từ trước: a[0]  a[1]  … a[N-1]. Hơn nữa chúng ta giả sử các số là phân biệt (tôi sẽ để trường hợp các số lặp cho các bạn như là một bài tập nhỏ), do đó a[0] < a[1] < … < a[N-1].
Để kiểm tra a[i] có thể là một phần tử trung bình không, chúng ta trước hết xem xét a[i-1] và a[i+1]. Nếu như trung bình cộng của a[i-1] và a[i+1] là a[i] thì chúng ta kết luận ngay a[i] là một phần tử trung bình. Nhưng nếu không phải thì sẽ có hai trường hợp xảy ra:
Trường hợp 1: trung bình cộng của a[i-1], a[i+1] lớn hơn a[i].
Khi đó a[i] không thể là trung bình cộng của a[i-1] với bất cứ phần tử a[j] nào mà j < i, và trung bình cộng của a[i-1] với bất cứ phần tử a[j] nào mà j > i+1 cũng sẽ lớn hơn a[i]. Do đó ta sẽ không cần thiết phải xem xét phần tử a[i-1] nữa.
Trường hợp 2: trung bình cộng của a[i-1, a[i+1] nhỏ hơn a[i].
Khi đó a[i] sẽ không thể là trung bình cộng của a[i+1] với bất cứ phần tử a[j] nào mà j > i, và a[i] cũng không thể là trung bình cộng của a[i+1] với bất cứ phần tử a[j] nào mà j < i. Có nghĩa là phần tử a[i+1] sẽ không cần phải xét tới nữa.
Thật tuyệt vì chúng ta dường như loại bỏ được rất nhiều các cặp cần xem xét chỉ sau một thao tác so sánh. Có thể áp dụng các nhận xét trên để đưa ra một thuật toán có độ phức tạp N thay vì N*N hay không?
Câu trả lời là có, cùng với lập luận tương tự như trên chúng ta có nhận xét sau:
Giả sử left < i và right > i. Giả sử avg(a[left], a[right]) > a[i] (avg là ký hiệu trung bình cộng).
• a[i] không thể là trung bình cộng của a[left] với bất cứ a[j] nào mà j  right.
• Tương tự nếu avg(a[left], a[right]) < a[i] thì a[i] cũng sẽ không thể là trung bình cộng của a[right] với bất cứ a[j] nào mà j  left.
Nhận xét này dẫn chúng ta tới một thuật toán hiệu quả hơn. Chiến lược của thuật toán là chúng ta xét hai chỉ số left và right thỏa mãn:
1) left < i và right > i
2) a[i] không phải là trung bình cộng của bất cứ cặp đôi nào liên quan tới một phần tử a[j] nào mà left < j < right.
Để bắt đầu ta khởi tạo left = i-1 và right = i+1 (do ta giả sử dãy là phân biệt và sắp xếp tăng dần nên điều kiện 2 luôn được thỏa mãn).
Nếu avg(a[left], a[right]) = a[i] thì ta tăng biến đếm lên 1 đơn vị.
Nếu avg(a[left], a[right]) > a[i] thì ta giảm left đi 1 đơn vị. Tất nhiên điều kiện 1 vẫn thỏa mãn, về điều kiện 2 thì ta biết rằng bất cứ a[j] nào mà left < j < right, a[j] đều không thể xuất hiện trong cặp có trung bình cộng bằng a[i]. Hơn nữa do (1) nên ta biết rằng a[i] cũng không thể là trung bình cộng của a[left] với bất cứ a[j] nào mà j  i. Và rõ ràng là a[i] cũng không thể là trung bình cộng của a[left] với bất cứ a[j] nào mà j < left. Do đó a[i] không thể là trung bình cộng của a[left] với bất cứ a[j] nào, nên giảm left đi 1 đơn vị không mâu thuẫn với (2).
Ngược lại nếu avg(a[left], a[right]) < a[i], chúng ta sẽ tăng right lên 1 đơn vị. Hoàn toàn tương tự ta có thể chứng minh các điều kiện 1 và 2 không bị vi phạm. Chúng ta sẽ dừng lại và kết luận a[i] không phải là một phần tử trung bình trong trường hợp left < 0 hoặc right = N.
Và cài đặt của thuật toán là:
Trong mỗi lần lặp của vòng lặp while, biến chỉ số left sẽ được giảm đi 1 hoặc biến chỉ số right sẽ bị giảm đi 1. Do đó vòng lặp while này chỉ có thể chạy tối đa N lần trước khi kết thúc. Do đó độ phức tạp của thuật toán là N*N.
Vì chúng ta giả sử a[0] < a[1] < … < a[N-1] và các phần tử là khác nhau nên chúng ta cần phải sắp xếp trước khi thực hiện thuật toán trên. Và tất nhiên chúng ta có thể chọn một thuật toán sắp xếp có độ phức tạp  hoặc  . Tóm lại là thuật toán sẽ có độ phức tạp là .
Nếu như các phần tử không phải là phân biệt, thì sau khi sắp xếp xong chúng ta có thể sửa đổi đôi chút để thuật toán trên vẫn có thể làm việc được trong cả trường hợp này (phần này sẽ dành cho các bạn như là một bài tập nhỏ).
Chú ý là trong thuật toán trên chúng ta đã sử dụng một thuộc tính của trung bình cộng: nếu x y và w  z thì agv(x, w)  agv(y, z). Tính chất này được gọi là tính đơn điệu. Nếu như chúng ta cần phải tính số lượng phần tử là tổng của hai phần tử, hay bất cứ giá trị nào thỏa mãn tính đơn điệu thì đều có thể giải quyết bằng một thuật toán có độ phức tạp là O(N2) thay vì một thuật toán có độ phức tạp  .
Các bạn có thể thấy rằng thuật toán trên cũng khá phức tạp và không quá dễ hiểu cho bài toán, lời giải thứ hai của bài toán khá gọn và dễ hiểu: do các số đều là số nguyên, ta lại cần đếm các số là trung bình cộng của hai số trong dãy, nên ta sẽ đánh dấu tất cả các tổng của hai số khác nhau (về vị trí chứ không phải về giá trị) trong dãy, sau đó duyệt lại dãy tổng này để đếm và đưa ra kết quả, cài đặt cụ thể của thuật toán này như sau:
Độ phức tạp của thuật toán này cũng là  , nhưng đơn giản và dễ hiểu hơn nhiều so với thuật toán trước.
Mặc dù đã hết sức thận trọng và xem xét kỹ các ví dụ đưa ra trong bài viết, tuy vậy vẫn có thể không tránh khỏi các sai sót, rất mong nhận được sự đóng góp ý kiến của các bạn độc giả. Mọi góp ý, thắc mắc xin gửi về địa chỉ email: tuannhtn@yahoo.com.



URL của bài viết này::http://www.schoolnet.vn/modules.php?name=News&file=article&sid=2145

© Cong ty Cong Nghe Tin hoc Nha truongcontact: schoolnet@vnschool.net