BFS và DFS
Khoa Đỗ Anh
So sánh giữa BFS và DFS:
BFS tốn bộ nhớ hơn vì nó lưu lại tất cả các con ở mỗi cấp.
Tuy nhiên , tùy vào bài toán cụ thể mà BFS hay DFS sẽ “chạy” nhanh hơn
Ví dụ: Ta có 1 cây gia phả qua nhiều thế hệ của một gia tộc lớn
Nếu 1 người nào đó trong gia phả muốn tìm kiếm 1 người nào đó vẫn còn sống thì ta thấy DFS thường hoạt động nhanh hơn.Tuy nhiên, nếu người đó muốn tìm một người nào đó đã mất cách đây rất lâu thì BFS thường nhanh hơn DFS.
Nói tóm lại , cái nào tốt hơn cái nào thì còn tùy thuộc vào dữ liệu và những gì bạn đang tìm kiếm.
Code: nếu bạn nào rành C# thì sẽ thấy code rất gần với mã giả vì trong C# đã hỗ trợ kiểu dữ liệu tree, stack, queue, list(có sẵn các hàm truy vấn dữ liệu luôn)… vì vậy công việc của bạn chỉ là gọi đúng hàm đúng việc là được.
Ah còn câu thầy hỏi BFS và DFS là thuật toán hay giải thuật mình xin có vài ý kiến.
Theo mình biết vẫn chưa có định nghĩa thuật toán nào được chấp nhận cả và ít thông dụng, nhưng còn giải thuật (đặc biệt là giải thuật heurictis) thì được sử dụng rộng rãi. Để đáp ứng những yêu cầu của thuật toán đòi hỏi thời gian chạy rất lớn, hoặc các điều kiện cho thuật toán khó đáp ứng(tính xác định và tính đúng đắn). Tuy nhiên ngày nay người ta đã mở rộng 2 tiêu chuẩn này.Chẳng hạn mở rộng tính xác định thể hiện qua các giải thuật đệ quy và ngẫu nhiên.Còn tính chính xác thì người ta đã chấp nhận các cách giải ít phức tạp và cho kết quả tốt(nhưng không phải lúc nào cũng tốt).
Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đủ các tiêu chuẩn của thuật toán được gọi là giải thuật.
Vì vậy mình nghĩ BFS và DFS là thuật toán. Vì nó thỏa 2 yêu cầu của thuật toán.Dữ liệu là có giới hạn, chẳng hạn các trạng thái của 1 ván cờ vua tuy nhiều nhưng có giới hạn vì nó giới hạn trong phạm vi bàn cờ, giới hạn số quân và giới hạn cách đi của mỗi quân cờ. Vậy là thỏa tính xác định. Tính đúng đắn thì khỏi bàn cải, chỉ cần thứ mình tìm có tồn tại trong dữ liệu chắc chắn sẽ tìm thấy, vì nó duyệt qua hết “ngóc ngách” của dữ liệu.
Nếu bạn nào có ý kiến xin góp ý thêm cho mình nha.
I am Phan Mê Thật
+ cách giải thích của bạn chấp nhận được
+một số tài liệu khác có nói 2 cái này là thuật toán
Nhưng mà,tui thấy hình như vẫn có sự mập mờ giữa 2 khái niệm này.Cụ
thể là trong Bài giảng của Thầy Dương ở CHƯƠNG 3,slide 14 và 16 có 2
cụm từ thuật toán HCS và thuật giải leo đồi dốc đứng(là 1 trường hợp
của HCS).Phải chăng có sự nhập nhằng gì ở đây không?
Đỗ Anh Khoa
Như mình đã nói chưa có định nghĩa nào cho thuật toán được chấp nhận
cả.
Hay nói cách khác thuật toán chỉ được hiểu một cách mơ hồ và người ta
chỉ đánh giá 1 lời giải cho 1 bài toán có phải là thuật toán không
thông qua 2 tiêu chuẩn mình đã đề cập.
Chính ở điểm này làm ta khó phân biệt rõ thuật giải và thuật toán vì
ta không thể nào chứng minh nó có thỏa mãn được 2 tiêu chuẩn theo một
chừng mực nào đó hay không (vì như trên mình nói xác định nhưng chưa
hẳn là xác định và đúng đắn nhưng chưa hẳn đúng trong mọi trường hợp
cái đó còn tùy vào đánh giá của mấy ông giáo sư tiến sĩ). Mà khi chưa
được chứng minh thì mình có thể gọi thế nào cũng được. Còn trong tài
liệu của thầy thì mình công nhận cậu chú ý kỹ từng chi tiết thiệt nha.
Lên hỏi thầy sẽ rõ chắc là thầy thử bọn mình ấy mà hihi.
Mr.HAPPY
là gì ?
Thuật toán:
+ để kiểm tra đó có phải thuật toán hay không thì phải thỏa mãn 2
tiêu chí: tính xác định và tính đúng đắn.
- Tính xác định được mở rộng đối với thuật toán được thể hiện qua các
giải thuật đệ quy và ngẫu nhiên.
cách giải bài toán, nhất là các cách giải gần đúng.
-> Nếu thỏa mãn 2 tiêu chí trên là thuật toán
+ Trong thực tiễn có nhiều trường hợp người ta chấp nhận các cách giải
thường cho kết quả tốt (nhưng không phải lúc nào cũng tốt) nhưng ít
phức tạp và hiệu quả. Chẳng hạn nếu giải một bài toán bằng thuật toán
tối ưu đòi hỏi máy tính thực hiên nhiều năm thì chúng ta có thể sẵn
lòng chấp nhận một giải pháp gần tối ưu mà chỉ cần máy tính chạy trong
vài ngày hoặc vài giờ.
Thuật giải:
- là các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ
các tiêu chuẩn của thuật toán thường
- Mở rộng này của thuật toán đã mở cửa cho chúng ta trong việc tìm
kiếm phương pháp để giải quyết các bài toán được đặt ra.
Trả lời câu hỏi của bạn thật
Thuật toán leo đồi, nó luôn cho ra kết quả
Về cơ bản, leo đồi dốc đứng cũng giống như leo đồi, chỉ khác ở điểm là
leo đồi dốc đứng sẽ duyệt tất cả các hướng đi có thể và chọn đi theo
trạng thái TỐT NHẤT trong số các trạng thái kế tiếp có thể có (trong
khi đó leo đồi chỉ chọn đi theo trạng thái kế tiếp đầu tiên TỐT HƠN
trạng thái hiện hành mà nó tìm thấy) nên ng ta gọi nó là thuật giải
leo đồi dốc đứng.
Mình cũng đồng ý BFS và DFS là thuật toán
So sánh BFS và DFS qua 4 điểm sau:
DFS: Chiều sâu
+ Tính hiệu quả:
- Hiệu quả khi lời giải nằm sâu trong cây tìm kiếm và có một phương án
chọn hướng đi chính xác.
- Hiệu quả của chiến lược phụ thuộc vào phương án chọn hướng đi.
- Phương án càng kém hiệu quả thì hiệu quả của chiến lược càng giảm.
- Thuận lợi khi muốn tìm chỉ một lời giải.
+ Lượng bộ nhớ sử dụng để lưu trữ các trạng thái:
- Chỉ lưu lại các trạng thái chưa xét đến.
+ Trường hợp xấu nhất:
- Vét cạn toàn bộ
+ Trường hợp tốt nhất
- Phương án chọn hướng đi tuyệt đối chính xác.
- Lời giải được xác định một cách trực tiếp.
BFS: Chiều rộng
+ Tính hiệu quả:
- Hiệu quả khi lời giải nằm gần gốc của cây tìm kiếm.
- Hiệu quả của chiến lược phụ thuộc vào độ sâu của lời giải.
- Lời giải càng xa gốc thì hiệu quả của chiến lược càng giảm.
- Thuận lợi khi muốn tìm nhiều lời giải.
+ Lượng bộ nhớ sử dụng để lưu trữ các trạng thái:
Phải lưu toàn bộ các trạng thái.
+ Trường hợp xấu nhất:
- Vét cạn toàn bộ
+ Trường hợp tốt nhất
- Vét cạn toàn bộ.
Mr.HAPPY
có tìm thấy trạng thái TỐT NHẤT
Đỗ Anh Khoa
đồi mà luôn luôn cho ra kết quả sao???Nên nhớ nó dùng các hàm đánh giá
để loại bỏ một số trạng thái, nó không có quay lại chọn trạng thái
khác nếu hướng đi của nó không cho ra kết quả. Mà đã bỏ trạng thái thì
có thể bỏ mất trạng thái đích.