Tôi đang làm Tetris như một dự án bên vui vẻ (không phải bài tập về nhà) và muốn thực hiện AI để máy tính có thể tự chơi. Cách tôi đã nghe để làm điều đó là sử dụng BFS để tìm kiếm thông qua các địa điểm có sẵn, sau đó tạo một điểm tổng hợp của vị trí thả hợp lý nhất ...Tìm kiếm đầu tiên về chiều sâu và chiều rộng Tìm hiểu đầu tiên
Nhưng tôi không hiểu các thuật toán BFS và DFS. Cách tôi học tốt nhất là vẽ nó ra ... bản vẽ của tôi có đúng không?
Cảm ơn!
Kết quả cuối cùng của các lần duyệt của bạn là chính xác, bạn gần đúng. Tuy nhiên, bạn có một chút thông tin chi tiết.
Trong tìm kiếm chiều sâu đầu tiên, bạn sẽ bật một nút, đánh dấu nút đó là đã truy cập và ngăn xếp các trẻ chưa được xem của nó. Theo thứ tự đó. Thứ tự có vẻ không liên quan đến một cái cây, nhưng nếu bạn có một biểu đồ với chu kỳ, bạn có thể rơi vào một vòng lặp vô hạn, nhưng đây là một cuộc thảo luận khác.
Với đường cơ sở của thuật toán, sau khi bạn đẩy nút gốc vào ngăn xếp, bạn sẽ bắt đầu lặp lại đầu tiên, ngay lập tức xuất hiện A. Nó sẽ không còn trên ngăn xếp cho đến khi kết thúc thuật toán. Bạn sẽ bật A, ngăn xếp D, C và B cùng một lúc (hoặc B, C và D, bạn có thể làm điều đó sang trái hoặc phải sang trái, đó là lựa chọn của bạn) và đánh dấu A là đã truy cập. Ngay bây giờ, ngăn xếp của bạn có D ở dưới cùng, C ở giữa và B trên đầu.
Nút tiếp theo xuất hiện là B. Bạn sẽ đẩy F và E vào ngăn xếp (tôi sẽ giữ nguyên thứ tự giống như của bạn), đánh dấu B là đã truy cập. Ngăn xếp có, từ trên xuống dưới, E F C D. Tiếp theo, E xuất hiện, không có nút mới nào được thêm vào và E được đánh dấu là đã truy cập. Các vòng lặp sẽ tiếp tục, làm như vậy để F, C và D. Trình tự cuối cùng là ABEFC D.
tôi sẽ cố gắng viết lại thuật toán theo cách tương tự như của bạn:
Push root into stack
Loop until stack is empty
Pop node N on top of stack
Mark N as visited
For each children M of N
If M has not been visited (M.visited() == false)
Push M on top of stack
tôi thắng 't đi vào chi tiết cho tìm kiếm đầu tiên bề rộng, thuật toán là chính xác như nhau. Sự khác biệt là trong cấu trúc dữ liệu và cách nó hoạt động. Một hàng đợi là FIFO (First In First Out) và, do đó, bạn sẽ truy cập tất cả các nút trong cùng một cấp độ trước khi bạn bắt đầu truy cập các nút ở các cấp thấp hơn.
Trước hết, tôi tin rằng các thông tin phản đối của bạn có vẻ ổn thỏa (từ tổng quan nhanh). Tôi sẽ cung cấp cho bạn một số liên kết hữu ích bên dưới.
Tôi đã tìm thấy một số video phong nha trên youtube về điều này trước đây nhưng đây là một (không phải là tốt nhất tôi đã nhìn thấy) bao gồm nó http://www.youtube.com/watch?v=eXaaYoTKBlE. Nếu bạn đang làm nó cho vui làm cho hai phiên bản, một với DFS và một với BFS và chuẩn cho họ để quan sát sự khác biệt. Ngoài ra, hãy tải xuống trình tìm kiếm đồ thị và bất kỳ công cụ nào khác mà bạn thấy hữu ích từ http://www.aispace.org/downloads.shtml nếu bạn muốn theo dõi một số công cụ để hiểu rõ hơn. Và câu hỏi cuối cùng nhưng không kém phần quan trọng trên DFS và BFS http://www.stackoverflow.com/questions/687731/
Lưu ý: Việc sử dụng DFS không hiệu quả hoặc thời gian thực vì số lượng khả năng trở nên rất lớn, vì vậy bạn sử dụng BFS để đưa ra một động thái hợp lý dựa trên một số tính toán. Không hoàn toàn có liên quan ở đây nhưng bạn có thể muốn xem xét thuật toán Minimax cho AI vì nó tương đối đơn giản và thể hiện việc cắt giảm số lượng khả năng đi lên nhanh hơn (thường là ở Tic-tac-toe). – wazy
@ wazy nó sẽ phụ thuộc vào dữ liệu.Điều gì xảy ra nếu biểu đồ có nhiều nút trên mỗi cấp độ hơn mỗi chiều cao? –
Tôi ghét phải nói "phụ thuộc" nhưng nó phụ thuộc vào bạn đang cố gắng tìm một giải pháp "nhanh" (hoặc ít nhất là cố gắng và không nhất thiết phải tối ưu) hoặc bạn đang cố gắng đánh giá mọi giải pháp/kết hợp có thể. – wazy