PDA

View Full Version : Cải tiến thuật toán tìm kiếm theo chiều rộng và chiều sâu trên đồ thị theo cách nào?



ducthy132
09-09-2012, 09:31 PM
Mình sẽ đặt 1 vấn đề như đúng tựa đề. Thường thì để giải quyết vấn đề tìm đường đi ngắn nhất, người ta hay dùng đến thuật toán quen thuộc nhất là Heuristics, tuy nhiên, mình lại có ý tưởng muốn tìm đường đi ngắn nhất bằng cách áp dụng thuật toán Heuristics vào thuật toán tìm kiếm theo rộng và sâu trên đồ thị, tức là: mình sẽ duyệt đồ thị theo chiều rộng, nó sẽ cho ra 1 kết quả từ đỉnh A đến đỉnh B, nhưng nếu lỡ đoạn đường từ A đến B lại ko tối ưu, thì nó sẽ cho ra 1 kết quả khác, tất nhiên là phải theo thuật toán BFS ỏ DFS. Tuy nhiên, điều mình thắc mắc là, không biết trong 1 đồ thị, thì việc duyệt đồ thị theo BFS or DFS có bao giờ cho ra >=2 kết quả không? hay luôn luôn chỉ có 1. Tuy trên mạng có khá nhiều code cài đặt thuật toán BFS và DFS, nhưng kết quả trên 1 đồ thị thì mình thấy luôn cho ra 1. Nếu như kết quả luôn luôn cho ra 1 tức là trên 1 đồ thị tìm kiếm thì BFS or DFS chỉ có 1 kết quả, vậy thì ý tưởng của mình không thể áp dụng đc rồi? Có bạn nào trả lời thắc mắc của mình đc ko?

caonguyengl
09-09-2012, 09:47 PM
Mình sẽ đặt 1 vấn đề như đúng tựa đề. Thường thì để giải quyết vấn đề tìm đường đi ngắn nhất, người ta hay dùng đến thuật toán quen thuộc nhất là Heuristics, tuy nhiên, mình lại có ý tưởng muốn tìm đường đi ngắn nhất bằng cách áp dụng thuật toán Heuristics vào thuật toán tìm kiếm theo rộng và sâu trên đồ thị, tức là: mình sẽ duyệt đồ thị theo chiều rộng, nó sẽ cho ra 1 kết quả từ đỉnh A đến đỉnh B, nhưng nếu lỡ đoạn đường từ A đến B lại ko tối ưu, thì nó sẽ cho ra 1 kết quả khác, tất nhiên là phải theo thuật toán BFS ỏ DFS. Tuy nhiên, điều mình thắc mắc là, không biết trong 1 đồ thị, thì việc duyệt đồ thị theo BFS or DFS có bao giờ cho ra >=2 kết quả không? hay luôn luôn chỉ có 1. Tuy trên mạng có khá nhiều code cài đặt thuật toán BFS và DFS, nhưng kết quả trên 1 đồ thị thì mình thấy luôn cho ra 1. Nếu như kết quả luôn luôn cho ra 1 tức là trên 1 đồ thị tìm kiếm thì BFS or DFS chỉ có 1 kết quả, vậy thì ý tưởng của mình không thể áp dụng đc rồi? Có bạn nào trả lời thắc mắc của mình đc ko?
vì nó cũng tìm theo 1 giải thuật thì nó ra cùng 1 kết quả nhanh và ngắn nhất roài.nó cũng là thuật toán tìm kiếm thì đương nhiên người nghĩ ra thuật toán này phải chú trọng đến mục tiêu của bài toán là tìm (chính xác + nhanh nhất trong phạm vi có thẻ). vậy nên đừng làm bác học làm gì? cố quá thành quá cố đấy àh nha.hehe

Quy_ny
09-09-2012, 11:03 PM
Mình sẽ đặt 1 vấn đề như đúng tựa đề. Thường thì để giải quyết vấn đề tìm đường đi ngắn nhất, người ta hay dùng đến thuật toán quen thuộc nhất là Heuristics, tuy nhiên, mình lại có ý tưởng muốn tìm đường đi ngắn nhất bằng cách áp dụng thuật toán Heuristics vào thuật toán tìm kiếm theo rộng và sâu trên đồ thị, tức là: mình sẽ duyệt đồ thị theo chiều rộng, nó sẽ cho ra 1 kết quả từ đỉnh A đến đỉnh B, nhưng nếu lỡ đoạn đường từ A đến B lại ko tối ưu, thì nó sẽ cho ra 1 kết quả khác, tất nhiên là phải theo thuật toán BFS ỏ DFS. Tuy nhiên, điều mình thắc mắc là, không biết trong 1 đồ thị, thì việc duyệt đồ thị theo BFS or DFS có bao giờ cho ra >=2 kết quả không? hay luôn luôn chỉ có 1. Tuy trên mạng có khá nhiều code cài đặt thuật toán BFS và DFS, nhưng kết quả trên 1 đồ thị thì mình thấy luôn cho ra 1. Nếu như kết quả luôn luôn cho ra 1 tức là trên 1 đồ thị tìm kiếm thì BFS or DFS chỉ có 1 kết quả, vậy thì ý tưởng của mình không thể áp dụng đc rồi? Có bạn nào trả lời thắc mắc của mình đc ko?

Đã là đồ thị thì nó sẽ cho ta rất nhiều kết quả chứ không phải là 1 đặc biệt là các phương pháp tiềm kiếm mù. Có thể bạn thấy cho ra 1 là do số bước nó tìm thấy là = nhau thôi. chứ nó đang đi theo đường khác mà vẫn đến đích. Các phương pháp cải tiến người ta cũng đã đề cập. bạn chịu khó search google. Có 1 thuật toán tìm kiếm Sử dụng Heuristics + DFS. điển hình để giải >=15 ô (IDA*).

ducthy132
10-09-2012, 05:20 PM
Đã là đồ thị thì nó sẽ cho ta rất nhiều kết quả chứ không phải là 1 đặc biệt là các phương pháp tiềm kiếm mù. Có thể bạn thấy cho ra 1 là do số bước nó tìm thấy là = nhau thôi. chứ nó đang đi theo đường khác mà vẫn đến đích. Các phương pháp cải tiến người ta cũng đã đề cập. bạn chịu khó search google. Có 1 thuật toán tìm kiếm Sử dụng Heuristics + DFS. điển hình để giải >=15 ô (IDA*).

Uhm, mình đã nghe bài toán này, trên mạng thì mình thấy hầu như chẳng có forum nào để cập cả, muốn nghiên cứu vấn đề này thì search với từ khóa: Breath First-Heuristics Search or Depth First-Heuristics Search. Tuy nhiên, những tài liệu mình down ở forum nước ngoài về thì toàn giả ngữ, để đọc hiểu đc thì thật là vãi cháy, T_T

conrongchautien
10-09-2012, 06:34 PM
Mình đoán bạn đang học Trí tuệ nhân tạo. Nếu vậy bạn hãy tìm hiểu theo thứ tự Tìm kiếm mù -> tìm kiếm kinh nghiệm - > tìm kiếm tối ưu.
Theo mình thì tất cả các chiến thuật tìm kiếm này đều lấy gốc từ DFS và BFS