[DIS] Một bài toán rất hay và cũng rất khó

[Zero]

Theo như mình biết thì chưa có ai giải bài này với thuật toán tối ưu (thậm chí gần đúng cũng chưa chạy được test lớn mà cho kết quả chấp nhận được) - cả đội tuyển trường mình đã bó tay trước bài này - mọi người thử giải xem (Turbo Pascal or Borland Pascal - Real Mode)
Bài này chạy trên máy P4 - 1.6 Ghz - 5s
Cho 1 mạng gt có n đỉnh (n < 100) một số đỉnh có 1 con robot, mỗi con robot cần phải đi đến 1 đỉnh đích. Bài toán ở đây là hãy tìm hành trình tối ưu nhất cho các robot để số lần di chuyển là ít nhất. Chú ý là robot không được đi vào đình có robot khác đang ở đó.

[songbien]

Chào bạn,

Tui cũng chưa biết phương pháp nào để giải thật tối ưu bài toán của bạn. Tuy nhiên, nếu bạn muốn tìm 1 phương pháp để giải gần tối ưu và nhanh chóng thì thử Genetic Algorithm thử xem. Phương pháp này dựa trên các quy luật di truyền của Mendel để giải những bài toán không có cấu trúc hoặc những vấn đề mà giải theo các phương pháp toán học thông thường đòi hỏi quá nhiều thời gian.

Nếu bạn muốn tìm hiểu thêm về GA thì ghé qua trang web của tui, sau đó vào phần Projects rồi đến Genetic Algorithm. Trong đó tui có 3 cái links tới GA khá bổ ích.

MHhttp://www.songbien.com/

[skywalker]

sao em vô thấy toàn tiếng anh ko vậy, bác có bản tiếng việt không (cả về web site lẫn về genetic algorithm)

[skywalker]

kỷ niệm bài viết thứ 90 của em :D
hành trình tối ưu của robot nghĩa là tổng số bước của tất cả các robot là ít nhất hay sao ạ

[songbien]

Xin lỗi bạn vì trang web của tui toàn tiếng Anh không nhé. Tui bận quá nên chưa viết phần tiếng Việt kịp.

Dạng toán mà bạn hỏi theo tôi biết thì đã có nhiều nghiên cứu về nó, bạn thử kiếm về "network optimization algorithm" thử xem. Nếu bạn muốn biết thêm về GA thì đọc tiếp.

Thuật toán di truyền dựa theo các nguyên tắc di truyền trong tự nhiên để giải mấy loại toán phức tạp không có cấu trúc hoặc các bài toán lớn tốn nhiều thời gian. Có khá nhiều công trình nghiên cứu dựa trên ý tưởng này để giải nhiều vấn đề rất khác nhau, từ mô phỏng cát rơi cho tới lĩnh vực hàng không vũ trụ. Tuy nhiên, nhược điểm lớn nhất của nó là nó có thể không tìm thấy đáp số tối ưu. (lý do khá đơn giản: ta thà chấp nhận 1 đáp số gần đúng còn hơn tốn vài tỉ năm để tìm đáp số tuyệt đối) :)

Giả sử ta có 1 mạng giao thông với n điểm. Ta cần xuất hành từ 1 điểm và phải đi hết tất cả các điểm rồi trở lại điểm khởi hành, tìm đường đi sao cho gần nhất.

1/ Trước hết, ta tạo ra khoảng 50 hành trình bất kỳ nào đó gọi là chromosome (số hành trình là tùy ý). Sau đó chấm điểm mỗi hành trình, ví dụ chromosome 1 dài 100km, chromosome 2 dài 200km, vv.

2/ Khi tìm thấy 2 chromosome ngắn nhất, ta đem hoán chuyển (cross-over) chúng với nhau. Giống như kiểu đem 2 giống đực và cái cho lai ấy mà.
VD: hành trình 1: ABC - DEF
hành trình 2: XYZ - PQR
sau khi lai sẽ cho ra 2 hành trình con là:
ABC - PQR và XYZ - DEF

ý tưởng là giống như trong tự nhiên, ta muốn đem 2 vật cho lai với nhau với hy vọng con lai sẽ tốt hơn.

3/ Ngoài ra, để tạo ra đột biến với hy vọng thế hệ sau sẽ tốt hơn thế hệ trước, ta có thể thay đổi chromosome một cách ngẫu nhiên. VD: lấy con lai ABC - PQR và biến nó thành AYC - PRQ

Lặp lại 3 thao tác trên qua nhiều thế hệ cho đến khi ta tìm được kết quả chấp nhận được.

Hy vọng giúp bạn được 1 tẹo.

MH

[Zero]

Hey dùng GA cũng là 1 ý nhưng vấn đề ở đây là trong bài toán này việc sinh ra được 1 hành trình hợp lệ đã rất tốt thời gian rồi chưa kể việc đem lai hai ht tôt chưa chắc đã sinh ra được 1 hành trình hợp lệ ? nếu áp dụng GA theo hướng này sợ rằng không ổn chăng ?

[songbien]

Trên lý thuyết thì GA không hề có 1 cấu trúc xác định nào cả. Đó là cái hay và cũng là cái dở của GA. Ví dụ như câu hỏi của bạn đưa ra hoàn toàn hợp lệ bởi vì bạn dự định tìm hai hành trình tốt nhất, sau đó đem lai với nhau. Bạn có thể tìm được kết quả tốt hơn, nhưng có lẽ sẽ gặp kết quả xấu hơn bởi vì lai hai cái tốt chưa chắc đã cho ra cái tốt. Trong tự nhiên cũng thế, cha mẹ đẹp chưa chắc đã sinh ra con đẹp mà. Bởi vậy cho nên ta cần phải cho lai qua nhiều thế hệ. Hơn nữa, theo GA thì con lai tệ lắm cũng chỉ bằng bố mẹ, nếu nó tệ hơn sẽ bị loại trừ.

Theo tôi hiểu thì câu hỏi của bạn cụ thể hơn là: giả sử ta tìm được 2 đường tối ưu cho 2 robot bằng cách áp dụng GA cho từng robot một. Sau đó đem kết hợp hai đường này lại để xem coi cả 2 robot có thể cùng đi 1 lúc được hay không. Chưa chắc gì kết quả chấp nhận được. Đúng vậy, tui cũng nghĩ thế. Nhưng cái hay của GA là ở chỗ không có cấu trúc. Chính vì bạn đặt ra phương pháp như thế cho nên mới gặp trở ngại.

Tôi chưa có ý tưởng hay ho nào trong đầu ngay lúc này cả. Hay bạn thử dùng GA để giải song song thử xem. Ta vẫn giữ tất cả các thao tác chính của GA và thêm 1 thao tác mới: kiểm tra xem nếu hành trình A và B dành cho robot 1 và robot 2 có 1 điểm nào đó trùng nhau, ví dụ:
A: 1-2-3-4-5-6-7-8-9
B: 9-8-7-6-5-4-3-2-1

A và B có chung 1 điểm là 5, tức robot 1 và 2 đi đến điểm 5 cùng 1 lúc, vi phạm đề bài. Khi đó ta giết bớt hành trình A hoặc B. Hoặc ta cũng có thể tăng độ dài của hành trình đó lên 1 số cực lớn để loại trừ nó.

Phương pháp này tương đối dễ áp dụng, tuy nhiên nó có 1 nhược điểm là nếu số robot khá lớn so với số điểm thì gần như là tụi robot sẽ đụng nhau chan chát và không khéo chả có cái nào nhúc nhích đi đâu được.

Và tất nhiên, GA không đảm bảo sẽ tìm ra nghiệm tốt nhất, nhưng nó sẽ tìm ra nhanh nhất khi bài toán của ta lớn và không có cấu trúc.

MH

[skywalker]

hic
sao em nghe loảng xoảng quá vậy, có thể cho một bài thật căn bản về GA không

[skywalker]

songbien cũng nên làm một cái tutor về GA đi

[monkeyvu]

Theo mình nghĩ bài này là tìm đường đi ngắn nhất của các con robot í mà.Mình cứ cho độ dài đường đi là 1 thì đường đi ngắn nhất cũng chính là số bước di chuyển min,nhưng mình phải thêm điều kiện vào khi cài thuật toán.Nếu n<100 thì bạn có thể xài tạm Floy thử xem.

[CrazyBabe]

Bài này có thể làm chế lày: Quy về mạng robot, chuyển vị từ trạng thái bắt đầu về trạng thái đích, có thể cài trực tiếp bằng Dijstra nhưng nếu cài bằng BP thì có lẽ thiếu bộ nhớ, mà cũng kô chắc làm trong 5s là xong đâu, trường hợp 100 robot có thể phát sinh đến cả tỉ đỉnh, làm 5s chắc phải máy 1tera wá, hé hé...