Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Dự đoán chi phí giải pháp tối ưu bằng xác suất điều kiện
Tóm tắt
Các thuật toán tìm kiếm theo quy tắc được thiết kế để trả về một lộ trình tối ưu từ trạng thái khởi đầu đến trạng thái mục tiêu. Chúng tìm được chi phí giải pháp tối ưu như một tác dụng phụ. Tuy nhiên, có những ứng dụng mà điều mà người ta muốn biết chỉ là ước lượng chi phí giải pháp tối ưu. Lộ trình thực tế từ khởi đầu đến mục tiêu không cần thiết phải có ngay từ đầu. Ví dụ, người ta có thể quan tâm đến việc đánh giá nhanh chi phí tài chính của một dự án cho mục đích thầu. Trong những trường hợp như vậy, chỉ cần biết chi phí thực hiện dự án. Kế hoạch xây dựng thực tế có thể được lập ra sau, sau khi quá trình thầu kết thúc. Trong bài báo này, chúng tôi đề xuất một thuật toán, được gọi là Dự đoán Chi phí Giải pháp (SCP), có khả năng dự đoán chính xác và hiệu quả chi phí giải pháp tối ưu của một trường hợp vấn đề mà không cần tìm ra giải pháp thực tế. Mặc dù SCP có thể được coi là một hàm ngữ nghĩa, nhưng nó khác với một hàm ngữ nghĩa về mặt khái niệm như sau: 1) SCP không cần phải nhanh đủ để hướng dẫn các thuật toán tìm kiếm; 2) SCP không cần phải được thừa nhận (admissible); 3) thước đo cho hiệu quả của chúng tôi là độ chính xác trong dự đoán, điều này trái ngược với chất lượng giải pháp và số lượng nút được mở rộng dùng để đo lường hiệu quả của các hàm ngữ nghĩa. Chúng tôi chứng minh một cách kinh nghiệm rằng SCP đưa ra dự đoán chính xác trong một số chuẩn tìm kiếm theo quy tắc.
Từ khóa
#thuật toán tìm kiếm #dự đoán chi phí #giải pháp tối ưu #độ chính xác dự đoán #hàm ngữ nghĩaTài liệu tham khảo
Archer, A.F.: A modern treatment of the 15-puzzle. Am. Math. Mon. 106, 793–799 (1999)
Balas, E., Toth, P.: Branch and bound methods. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kart, A.H.G., Shmoys, D.B. (eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York (1985)
Burns, E., Ruml, W.: Iterative-deepening search with on-line tree size prediction. In: Proceedings of the International Conference on Learning and Intelligent Optimization, pp. 1–15 (2012)
Chen, P.-C.: Heuristic Sampling on Backtrack Trees. PhD thesis, Stanford University (1989)
Chenoweth, S.V., Davis, H.W.: High performance A* search using rapidly growing heuristics. In: International Joint Conference on Artificial Intelligence (1991)
Culberson, J.C., Schaeffer, J.: Searching with pattern databases. In: Proceedings of the Canadian Conference on Artificial Intelligence, volume 1081 of Lecture Notes in Computer Science, pp. 402–416. Springer (1996)
Dweighter, H.: Problem E2569. Am. Math. Mon. 82, 1010 (1975)
Ernandes, M., Gori, M.: Likely-admissible and sub-symbolic heuristics. In: Proceedings of the European Conference on Artificial Intelligence, pp. 613–617 (2004)
Felner, A., Korf, R.E., Hanan, S.: Additive pattern database heuristics. J. Artif. Intell. Res. 22, 279–318 (2004)
Felner, A., Zahavi, U., Schaeffer, J., Holte, R.C.: Dual lookups in pattern databases. In: Proceedings of the International Joint Conference on Artificial Intelligence, pp. 103–108 (2005)
Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. SSC-4(2), 100–107 (1968)
Helmert, M.: Landmark heuristics for the pancake problem. In: Proceedings of the Symposium on Combinatorial Search, pp. 109–110. AAAI Press (2010)
Helmert, M., Haslum, P., Hoffmann, J.: Flexible abstraction heuristics for optimal sequential planning. In: Proceedings of the International Conference on Automated Planning and Scheduling, pp. 176–183 (2007)
Jabbari Arfaee, S., Zilles, S., Holte, R.C.: Learning heuristic functions for large state spaces. Artif. Intell. 175(16–17), 2075–2098 (2011)
Kilby, P., Slaney, J.K., Thiébaux, S., Walsh, T.: Estimating search tree size. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp. 1014–1019. AAAI Press (2006)
Knuth, D.E.: Estimating the efficiency of backtrack programs. Math. Comp. 29, 121–136 (1975)
Korf, R.E.: Depth-first iterative-deepening: An optimal admissible tree search. Artif. Intell. 27(1), 97–109 (1985)
Korf, R.E.: Linear-space best-first search. Artif. Intell. 62(1), 41–78 (1993)
Korf, R.E.: Linear-time disk-based implicit graph search. J. ACM 55(6), 26:1–26:40 (2008)
Korf, R.E., Felner, A.: Disjoint pattern database heuristics. Artif. Intell. 134(1–2), 9–22 (2002)
Korf, R.E., Felner, A.: Recent progress in heuristic search: A case study of the four-peg Towers of Hanoi problem. In: Proceedings of the International Joint Conference on Artificial Intelligence, pp. 2324–2329 (2007)
Korf, R.E., Reid, M., Edelkamp, S.: Time complexity of iterative-deepening-A ∗. Artif. Intell. 129(1–2), 199–218 (2001)
Lelis, L., Stern, R., Felner, A., Zilles, S., Holte, R.C.: Predicting optimal solution cost with bidirectional stratified sampling. In: Proceedings of the International Conference on Automated Planning and Scheduling, pp. 155–163. AAAI Press (2012)
Lelis, L., Stern, R., Jabbari Arfaee, S.: Predicting solution cost with condiditional probabilities. In: Proceedings of the Symposium on Combinatorial Search, pp. 100–107. AAAI Press (2011)
Lelis, L., Zilles, S., Holte, R.C.: Improved prediction of IDA*’s performance via 𝜖-truncation. In: Proceedings of the Symposium on Combinatorial Search, pp. 108–116. AAAI Press (2011)
Lelis, L.H.S.: Active stratified sampling with clustering-based type systems for predicting the search tree size of problems with real-valued heuristics. In: Proceedings of the Symposium on Combinatorial Search, pp. 123–131. AAAI Press (2013)
Lelis, L.H.S., Otten, L., Dechter, R.: Predicting the size of depth-first branch and bound search trees. In: International Joint Conference on Artificial Intelligence, pp. 594–600 (2013)
Lelis, L.H.S., Zilles, S., Holte, R.C.: Predicting the size of IDA*’s search tree. Artif. Intell., 53–76 (2013)
Pearl, J.: Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann (1988)
Prieditis, A.E.: Machine discovery of effective admissible heuristics. Mach. Learn. 12(1–3), 117–141 (1993)
Richter, S., Helmert, M.: Preferred operators and deferred evaluation in satisficing planning. In: Proceedings of the International Conference on Automated Planning and Scheduling, pp. 273–280 (2009)
Samadi, M., Felner, A., Schaeffer, J.: Learning from multiple heuristics. In: Proceedings of the AAAI Conference on Artificial Intelligence, pp. 357–362. AAAI Press (2008)
Slocum, J., Sonneveld, D.: The 15 Puzzle. Slocum Puzzle Foundation (2006)
Stern, R., Puzis, R., Felner, A.: Potential search: a bounded-cost search algorithm. In: Proceedings of the International Conference on Automated Planning and Scheduling, pp. 234–241 (2011)
Sturtevant, N.R., Felner, A., Barrer, M., Schaeffer, J., Burch, N.: Memory-based heuristics for explicit state spaces. In: Proceedings of the International Joint Conference on Artificial Intelligence, pp. 609–614 (2009)
Thayer, J., Dionne, A., Ruml, W.: Learning inadmissible heuristics during search. In: Proceedings of the International Conference on Automated Planning and Scheduling, pp. 250–257 (2011)
Thayer, J.T., Stern, R., Lelis, L.H.S.: Are we there yet? - estimating search progress. In: Proceedings of the 5th Annual Symposium on Combinatorial Search, pp. 129–136. AAAI Press (2012)
Yang, F., Culberson, J.C., Holte, R.C., Zahavi, U., Felner, A.: A general theory of additive state space abstractions. J. Artif. Intell. Res. 32, 631–662 (2008)
Zahavi, U., Felner, A., Burch, N., Holte, R.C.: Predicting the performance of IDA* using conditional distributions. J. Artif. Intell. Res. 37, 41–83 (2010)
Zahavi, U., Felner, A., Holte, R.C., Schaeffer, J.: Duality in permutation state spaces and the dual search algorithm. Artif. Intell. 172(4–5), 514–540 (2008)