Efficient Branch and Bound Search with Application to Computer-Aided Design

جستجوی شاخه و کران برای مدت طولانی شناخته شده است و به طور گسترده ای در حل انواع مسائل در طراحی به کمک کامپیوتر (CAD) و بسیاری از مسائل مهم بهینه سازی استفاده می شود.
در بسیاری از برنامه‌ها، روش‌های کلاسیک جستجوی شاخه و کران، محاسبات را تکرار می‌کنند، یا به درخت‌های تصمیم جستجو تکیه می‌کنند که فرآیندهای جستجوی شاخه و کران را پیگیری می‌کنند. در CAD و بسیاری از زمینه‌های فنی دیگر، هزینه محاسباتی ساخت درخت‌های تصمیم‌گیری جستجوی شاخه و کران در حل مسائل در مقیاس بزرگ بسیار زیاد است و تکرار محاسبات غیرقابل تحمل است. برای مقابله با چالش‌های محاسباتی امروزی به روش‌های کارآمد شاخه و کران نیاز است. روش های کارآمد شاخه و کران نباید محاسبات را تکرار کنند.
جستجوی کارآمد شاخه و کران با استفاده از طراحی به کمک کامپیوتر یک روش کارآمد شاخه و کران را برای توجیه منطقی توصیف می‌کند که برای اساسی است. الگوی تست خودکارنسل (ATPG)، شناسایی افزونگی، سنتز منطق، کمینه سازی، تأیید و سایر مشکلات در CAD. این روش Equivalence توجیه نامیده می‌شود، بر اساس این مشاهده که فرآیندهای توجیه ممکن است دنباله‌های تصمیم جستجوی بعدی مشابهی را به اشتراک بگذارند. با معادل سازی توجیهی، از تکرار محاسبات در فرآیند جستجوی شاخه و کران پویا بدون استفاده از درخت های تصمیم جستجو اجتناب می شود.
جستجوی کارآمد شاخه و کران با برنامهطراحی به کمک رایانه از دو بخش تشکیل شده است. بخش اول، شامل سه فصل اول، کار نظری را ارائه می دهد. بخش دوم به کاربردها، به ویژه ATPG برای مدارهای ترتیبی می پردازد.
این کتاب به ویژه برای خوانندگانی که علاقه مند به طراحی و آزمایش مدارهای دیجیتال هستند مفید است.

Branch-and-bound search has been known for a long time and has been widely used in solving a variety of problems in computer-aided design (CAD) and many important optimization problems.
In many applications, the classic branch-and-bound search methods perform duplications of computations, or rely on the search decision trees which keep track of the branch-and-bound search processes. In CAD and many other technical fields, the computational cost of constructing branch-and-bound search decision trees in solving large scale problems is prohibitive and duplications of computations are intolerable. Efficient branch-and-bound methods are needed to deal with today's computational challenges. Efficient branch-and-bound methods must not duplicate computations.
Efficient Branch and Bound Search with Application to Computer-AidedDesign describes an efficient branch-and-bound method for logic justification, which is fundamental to automatic test patterngeneration (ATPG), redundancy identification, logic synthesis, minimization, verification, and other problems in CAD. The method is called justification equivalence, based on the observation that justification processes may share identical subsequent search decision sequences. With justification equivalence, duplication of computations is avoided in the dynamic branch-and-bound search process without using search decision trees.
Efficient Branch and Bound Search with Application to Computer-AidedDesign consists of two parts. The first part, containing the first three chapters, provides the theoretical work. The second part deals with applications, particularly ATPG for sequential circuits.
This book is particularly useful to readers who are interested in the design and test of digital circuits.