|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
04-06-2011, 10:22 PM | #1 |
+Thành Viên+ Tham gia ngày: Nov 2007 Bài gởi: 289 Thanks: 85 Thanked 162 Times in 100 Posts | Thuật toán tìm kiếm theo chiều rộng và chiều sâu Hôm nay học toán rời rạc có một bài toán mà đáp số thầy trò khác nhau . Mình đọc sách làm kết quả khác với thầy giáo . Mong mọi người chỉ dẫn Tìm thuật toán tìm kiếm theo chiều rộng và chiều sâu. Cho graph 1(2,6) ; 2(1,3) ; 3(2,4,5) ; 4(3,8) ; 5(3,8) ; 6(1,7) ; 7(6) ; 8(4,5) . Thầy tìm được tìm kiếm theo chiều rộng 1;2;6;3;7;4;5;8 Mình tìm được là 1;2;3;4;8;5. __________________ Ultra |
The Following User Says Thank You to asimothat For This Useful Post: | tranbatphong (04-06-2011) |
04-06-2011, 11:44 PM | #2 |
Administrator | Trước hết, vẽ cái hình minh họa cho dễ thấy: Ý tưởng của hai thuật toán tìm theo chiều sâu (depth-first-search hay thường viết gọn là dfs) và tìm theo chiều rộng (breadth-first-search hay thường viết gọn là bfs) là ngược nhau. Có thể nói tóm tắt là: *Tìm theo chiều sâu: duyệt graph từ đỉnh đầu (root), xét các đỉnh kề với nó và cho vào danh sách v (đánh dấu là đã duyệt rồi) và mỗi lần đi như thế thì càng xa đỉnh đầu càng tốt. *Tìm theo chiều rộng: cũng như trên nhưng đổi thành thì càng gần đỉnh đầu càng tốt. Nếu so sánh về mặt implement thì tất nhiên một bên sẽ dùng stack, một bên dùng queue. Nếu tìm theo chiều rộng thì kết quả chính là cách của thầy bạn giải đấy. Có thể giải thích thế này: -Đầu tiên root=1, cho vào v. -Đỉnh kề với root là 2 và 6, duyệt 2 trước và đưa 2 vào danh sách v. -Do điều kiện của bfs là duyệt càng gần root càng tốt nên ngay tại 2, ta không đi tiếp mà chuyển qua đỉnh kề root tiếp theo là 6, cho 6 vào v. -Kế đến ta cũng không đi tiếp tại 6 mà quay về root, tại đây không còn đỉnh nào kề nữa nên chuyển qua 2, ta có 2 đỉnh kề là 1 và 3. Do 1 đã nằm trong v rồi nên duyệt 3 và cứ thế mà tiếp tục. Cách duyệt của bạn dùng là dfs nhưng sau khi duyệt xong 5, ta quay về root, đỉnh kề với root vẫn còn là 6, ta duyệt tiếp 6 và 7 và hoàn tất chu trình là: 1;2;3;4;8;5;6;7. Nếu bạn đang học Cấu trúc dữ liệu và thuật toán dùng Java thì test thử là biết ngay mà! Dưới đây là 2 chương trình bfs và dfs, bạn xem thử nha! thay đổi nội dung bởi: huynhcongbang, 04-06-2011 lúc 11:47 PM |
Bookmarks |
Ðiều Chỉnh | |
Xếp Bài | |
|
|