Bất cứ ai đã thực hiện thuật toán tìm kiếm SMA *?

Question

Tôi tìm thấy mô tả thuật toán trong AIMA (Artificial Intelligence: A Modern Approach) là không chính xác chút nào. 'Cần thiết' có nghĩa là gì? Giới hạn bộ nhớ là gì? Kích thước hàng đợi hoặc nút được xử lý? Nếu nút hiện tại không có con thì sao?

Tôi tự hỏi liệu thuật toán này có chính xác hay không. Bởi vì tôi đã tìm kiếm trên Internet và chưa có ai thực hiện nó.

Cảm ơn.

Answer 1

Tôi tin rằng this PDF là phần SMA * của AIMA, dành cho những người không có sách.

đầu tiên tôi chú ý giả từ Wikipedia có một lỗi khá rõ ràng trong dòng: (? Làm thế nào có thể một phụ huynh có kế riêng của mình)

parent.successors.remove(parent); 

Nó phải là

parent.successors.remove(badNode); 

'Cần thiết' có nghĩa là gì?

Nếu cha mẹ của nó chưa có trong hàng đợi, thì chúng tôi phải thêm nó vào hàng đợi. Nếu không, chúng tôi sẽ kết thúc tìm kiếm nút này một lần nữa.

Giới hạn bộ nhớ là gì? Kích thước hàng đợi hoặc nút được xử lý?

Hàng đợi sẽ chiếm hết bộ nhớ khả dụng. Không có hàng đợi cho các nút đã xử lý. Đây chính là lý do tại sao SMA * có thể duyệt lại các nút và có khả năng gặp khó khăn.

Nếu nút hiện tại không có con thì sao?

Nếu nút không có con thì đó là nút lá. Và nếu đó là nút lá, thì đó là nút đầu cuối. Trong trường hợp đó, nếu đó không phải là nút mục tiêu, chúng tôi đặt chi phí f thành vô cùng và truyền thông tin đó cho phụ huynh của nó.

Answer 2

Tôi đã quản lý để thực hiện tìm kiếm đồ thị với nó trong C#, sử dụng the PDF.

Tôi đã sử dụng 3 danh sách - biên giới (danh sách mở), danh sách lá và danh sách "nhánh cây".

• Biên giới là Hàng đợi, được đề cập trong PDF, đó là hàng đợi ưu tiên chung được sắp xếp từ tốt nhất đến xấu nhất.

• Danh sách lá chỉ giữ lá, được sắp xếp từ xấu nhất đến tốt nhất, chúng tôi sẽ cần đến khi chúng tôi quyết định lá nào sẽ bị quên. SMA chỉ quên lá, không phải toàn bộ cành cây.

• Danh sách nhánh cây giữ các nút được mở rộng hoàn toàn, có tất cả các con trong bộ nhớ. Chúng tôi sẽ cần nó để kiểm tra giao lộ tiểu bang.

Tôi đã sử dụng đống nhị phân nhanh cho biên giới và danh sách lá, và bảng băm cho danh sách cành cây.

Nodes nên giữ các thông tin bổ sung sau đây:

• thừa kế iterator với vị trí (vị trí là cần thiết để chỉ trong danh sách kế vị). Chúng tôi hoàn toàn không được thiết lập lại kiểu liệt kê kế thừa của chúng tôi bằng không nếu chúng ta quên đi khi chúng ta đi, vì điều đó là có thể, rằng chúng ta quên nút mà chúng ta vừa thêm vào. Tôi sử dụng IEnumerator, int cho vị trí và bool cho "hoàn thành" cờ.

• Danh sách người kế nhiệm. Chúng tôi chắc chắn cần điều này để tăng chi phí lên trên. Ngoài ra tôi giữ danh sách các trạng thái kế thừa đơn giản - như [bị chặn, bị lãng quên, tồn tại]. Nó là cần thiết để theo dõi các nút bị lãng quên và bị chặn. (Bị chặn - trong đồ thị - bởi một số nút, mà mở rộng nhanh hơn)

• Hai F, được đề cập trong PDF, F hiện tại của chúng tôi, và người kế nhiệm bị lãng quên nhất F.

• Node sâu

Phân loại các nút trong cả hai biên giới và danh sách lá nên được thực hiện như thế này: "nếu chúng tôi đã" hoàn thành "bảng điều tra, chọn người kế nhiệm quên F tốt nhất, chọn F hiện tại, nếu bằng, chọn sâu nhất". Danh sách lá được sắp xếp theo thứ tự ngược lại bằng cách sử dụng cùng một điều kiện chính xác.

phác thảo thuật toán cơ bản là như thế này (tương tự như PDF):

• Chúng tôi chọn nút tốt nhất từ ​​biên giới, nếu nó đã "hoàn thành" cờ - chúng tôi biết chúng tôi sẽ ghi nhớ, thiết lập lại các iterator, và chúng ta phải thiết lập lại người kế nhiệm F bị quên lãng nhất trong trường hợp này (vì những lý do phức tạp).

• Nếu chúng tôi không có người kế nhiệm này trong danh sách (có thể, khi chúng tôi nhớ) - chúng tôi tạo ra và đặt F là được mô tả trong PDF.

• Sau đó, sau điều phức tạp nhất - chúng tôi kiểm tra xem nút có cùng trạng thái có tồn tại trong biên giới hay danh sách nhánh cây không. Nếu có - Tôi sẽ mô tả những việc cần làm sau. Nếu không, chúng ta chỉ cần thêm con vào biên giới (và loại bỏ cha mẹ khỏi danh sách lá).

• Trong mọi trường hợp điều tra kết thúc - chúng tôi thực hiện sao lưu chi phí f và nếu chúng tôi không có nút bị lãng quên (và có một số người kế thừa), chúng tôi sẽ xóa nút hiện tại khỏi biên giới và thêm nó vào danh sách nhánh cây.

Làm thế nào để quên: chúng ta chọn lá đầu tiên trong danh sách lá (lá tồi tệ nhất), loại bỏ nó ra khỏi biên giới, loại bỏ nó khỏi danh sách kế vị của cha mẹ, người kế nhiệm bị lãng quên nhất của bản cập nhật (giảm) của cha mẹ F, nếu cần thiết, và nếu cha mẹ không ở trên biên giới - chúng tôi xóa nó khỏi danh sách cây và thêm nó vào biên giới và cũng thêm nó vào danh sách lá, nếu bây giờ nó là một chiếc lá (không có người thừa kế nữa).

Việc cần làm, nếu chúng tôi tạo ra người thừa kế, đã có trong danh sách chi nhánh hoặc biên giới cây. Đầu tiên, chúng ta sẽ cần kiểm tra nó tốt hơn - chúng ta so sánh PathCost + H ("gốc" F) của hai nút. Lưu ý rằng chúng tôi không thể so sánh F được sao lưu - điều này sẽ không hoạt động. Nếu nó không tốt hơn - chúng ta chỉ cần thiết lập trạng thái kế nhiệm để chặn. Nếu có - có thể có trường hợp, nút tệ hơn là gốc của một cây con lớn (quá phức tạp để giải thích một lần nữa). Trong trường hợp này, chúng tôi cắt hoàn toàn cây con và SMA quên một loạt các nút cùng một lúc. Sau khi thay thế nút tệ hơn bằng nút tốt hơn, chúng tôi xóa nút tệ hơn khỏi danh sách người kế nhiệm cha mẹ, từ biên giới, danh sách lá hoặc thậm chí danh sách nhánh cây (thậm chí có thể ở đó!), thiết lập trạng thái kế thừa để chặn cho nó là cha mẹ và đừng quên kiểm tra xem cha mẹ nút tồi tệ hơn có tất cả các nút bị chặn bây giờ - chúng ta sẽ cần đặt F là vô cùng, khiến nó trở thành nút đầu cuối.

Có lẽ tôi đã không thực hiện đơn giản nhất, nhưng nó là duy nhất, phù hợp với tôi. Tôi đã sử dụng 8-câu đố cho các bài kiểm tra - giải quyết n-bước với tối thiểu (n + 1) -memory (đếm bắt đầu nút), và kiểm tra sự tối ưu giải pháp với một ngôi sao thông thường. Tôi đã dành 20-30 giờ cố gắng tìm ra tất cả các chi tiết - vấn đề chính là sự phức tạp của các trường hợp kiểm tra không thành công - tôi đã có các lỗi logic "thay thế bằng nút tốt hơn" chỉ trên 20 bước với một thử nghiệm rộng rãi hàng ngàn hạt giống ngẫu nhiên. Ngoài ra xem ra cho hàng đợi ưu tiên - Tôi đã phải nhập lại các mục trong nhiều trường hợp, gây ra bất kỳ thay đổi trong F, tốt nhất quên F, hoặc "hoàn thành" cờ - thay đổi thứ tự sắp xếp. Tôi đã kết thúc kiểm tra sự thống nhất heaps nhị phân của tôi trên mỗi dequeue. Và ý tưởng chính của việc loại bỏ các lỗi phức tạp nhất để hiểu được về việc đạp xe bất tận là kiểm tra, rằng bạn không giảm F trong mọi trường hợp. Bằng cách này, F sẽ tiếp tục tăng.

Tôi sẽ chia sẻ nguồn triển khai hoạt động trong một vài tuần.