State-Space Search: Algorithms, Complexity, Extensions, and Applications

این کتاب در مورد حل مسئله است. به طور خاص، این در مورد جستجوی فضای حالت-اکتشافی تحت چارچوب شاخه و کران برای حل مسائل بهینه سازی ترکیبی است. دو موضوع اصلی این کتاب عبارتند از پیچیدگی حالت میانگین الگوریتم‌های جستجوی فضای حالت اکتشافی مبتنی بر شاخه و کران، و کاربرد آن‌ها برای توسعه روش‌ها و الگوریتم‌های حل مسئله جدید. جستجوی فضای حالت اکتشافی یکی از تکنیک های اساسی حل مسئله در علوم کامپیوتر و تحقیقات عملیاتی است و معمولاً جزء مهمی از اکثر سیستم های حل مسئله هوشمند را تشکیل می دهد. الگوریتم های جستجوی در نظر گرفته شده در این کتاب را می توان در دسته بندی شاخه و کران طبقه بندی کرد. Branch-and-Bound یک الگوی کلی حل مسئله است و یکی از بهترین تکنیک ها برای حل بهینه مسائل محاسباتی فشرده مانند زمان بندی و برنامه ریزی است. الگوریتم‌های جستجوی اصلی در نظر گرفته شده عبارتند از: جستجوی اول بهترین، اولین شاخه و کران عمق، عمق‌بخشی تکراری، جستجوی بهترین اول بازگشتی، و جستجوی اول با فضای محدود. بهترین جست و جو و شاخه و کران اول عمق بسیار شناخته شده است و به طور گسترده در علوم کامپیوتر و تحقیقات عملیاتی استفاده شده است. یکی از ویژگی‌های مهم Depth-first branch-and-bound این است که فقط به فضایی نیاز دارد که در حداکثر عمق جستجو خطی باشد، و اغلب آن را به یک ریتم الگوی جستجوی مطلوب نسبت به جستجوی اول بهترین در عمل تبدیل می‌کند. تعمیق تکراری و جستجوی بازگشتی بهترین اول دو الگوریتم دیگر جستجوی فضای خطی هستند. عمیق‌سازی تکراری یک الگوریتم مهم در هوش مصنوعی است و نقشی بی‌بدیل در ساختن یک برنامه بازی در زمان واقعی بازی می‌کند.

This book is about problem solving. Specifically, it is about heuristic state-space search under branch-and-bound framework for solving com­ binatorial optimization problems. The two central themes of this book are the average-case complexity of heuristic state-space search algorithms based on branch-and-bound, and their applications to developing new problem-solving methods and algorithms. Heuristic state-space search is one of the fundamental problem-solving techniques in Computer Science and Operations Research, and usually constitutes an important component of most intelligent problem-solving systems. The search algorithms considered in this book can be classified into the category of branch-and-bound. Branch-and-bound is a general problem-solving paradigm, and is one of the best techniques for optimally solving computation-intensive problems, such as scheduling and planning. The main search algorithms considered include best-first search, depth­ first branch-and-bound, iterative deepening, recursive best-first search, and space-bounded best-first search. Best-first search and depth-first branch-and-bound are very well known and have been used extensively in Computer Science and Operations Research. One important feature of depth-first branch-and-bound is that it only requires space this is linear in the maximal search depth, making it very often a favorable search algo­ rithm over best-first search in practice. Iterative deepening and recursive best-first search are the other two linear-space search algorithms. Iterative deepening is an important algorithm in Artificial Intelligence, and plays an irreplaceable role in building a real-time game-playing program.