A Reordering Binary Decision Diagram based on Decision Tree Learning and Tabu Search
Article Sidebar
Main Article Content
Abstract
เนื่องจากแผนภาพตัดสินใจทวิภาคเป็นโครงสร้างข้อมูลแบบกราฟที่มีประสิทธิภาพในการแทนฟังก์ชันบูลีน แผนภาพตัดสินใจทวิภาคจึงถูกนำไปประยุกต์ใช้กับงานต่างๆของการใช้คอมพิวเตอร์ช่วยในการออกแบบ แต่ปัญหาหนึ่งที่พบเกี่ยวกับแผนภาพตัดสินใจทวิภาคคือ ขนาดของแผนภาพตัดสินใจทวิภาคจะขึ้นอยู่กับลำดับของตัวแปร ดังนั้น วิธีการหาลำดับตัวแปรที่ดีจึงเป็นสิ่งสำคัญในการสร้างแผนภาพตัดสินใจทวิภาคที่มีขนาดเล็ก งานวิจัยฉบับนี้ได้นำเสนอวิธีการปรับลำดับแผนภาพตัดสินใจทวิภาค โดยวิธีการที่นำเสนอจะใช้การเรียนรู้ต้นไม้ตัดสินใจ ร่วมกับเทคนิคการค้นหาต้องห้าม ซึ่งเป็นเทคนิคของปัญญาประดิษฐ์ โดยการหาลำดับตัวแปรเริ่มต้นของแผนภาพตัดสินใจทวิภาคจากนั้นจะลดขนาดของแผนภาพตัดสินใจทวิภาคด้วยเทคนิคการค้นหาต้องห้าม โดยเปรียบเทียบกับวิธีการปรับปรุงแบบก้าวหน้าที่มีอยู่เดิมซึ่งได้รับการปรับปรุงการเลือกตัวแปรแล้ว เช่น AD2 AD3 AD4 AR ARSA และ SIFTING ผลการทดลองกับวงจรวัดเปรียบเทียบสมรรถนะของ MCNC แสดงให้เห็นว่าวิธีการปรับลำดับแผนภาพตัดสินใจทวิภาคที่นำเสนอ สามารถให้แผนภาพที่มีขนาดเล็กกว่าเมื่อเทียบกับขนาดแผนภาพตัดสินใจทวิภาคที่ได้จากวิธีการการปรับปรุงแบบก้าวหน้าทุกแบบที่กล่าวมาข้างต้น
Article Details
The manuscript, information, content, picture and so forth which were published on Journal of Engineering, RMUTT has been a copyright of this journal only. There is not allow anyone or any organize to duplicate all content or some document for unethical publication.
References
Aker, S. B. Binary decision diagrams.IEEE Transactions on Computer Vol.C27 No.6 (June 1978): 509-516.
Bryant, R. E. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computer Vol.C-35 No.8 (August 1986): 677-691.
Bryant, R. E. Symbolic Boolean manipulation with ordered binary decision diagrams. ACM Computing Surveys Vol.24 No.3 (September1992): 293-318.
Micheli, G .D. Synthesis and optimization of digital circuits. New York: McGrawHill, 1994.
Fujita, M.; Fujisawa, H. and Kawato,N. Evaluations and improvementa of Boolean comparison method based on binary decision diagrams. Proceedings of the IEEE Conference on Computer Aided Design (November 1988):2-5
Malik, S.; Wang, A. R.; Brayton, R. K. and Sangiovanni-Vincentelli, A. Logic verification using binary decision diagrams in a logic synthesis environment.Proceedings of the IEEE Conference
on Computer-Aided Design (November1988):6-9
Masunaga , Y, and Fujita , M. Mulis level logic optimization using binary decision diagrams. Proceeding of the IEEE Conference on Computer – Aided Design ( November 1989 ).
Calazans , N; Jasobi , R;; Zhang , Q. and Trullemans , C. Improveing BDDs manipulation through incremental reduction and enhanced heuristics Proceeding of the IEEE Custom
Integrated Circuit Conference (1991): 472-475.
Jacobi, R. ; Calazans , N. and Trullemans, C. Incremental reduction of binary decision diagrams. Proceedings of the IEEE Conference on Computer-Aided Design (November 1991):3174-3177
Ishiura , N.; Sawada , H and Yajima , S Minimization of biary decision diagrams based on exhanges of variables. Proceedings of the IEEE Conference on Computer-Aided Design (November1991): 472 - 475.
Rudell , R. Dynamic variable ordering for ordered binary diagrams. Proceedings of the IEEE Conference on Computer Aided Design (November 1993): 42-47.
Friedman, S.J, and Supowit , K.J. Finding the optimal variable ordering for binary decision diagrams. IEEE Transaction on Computer Vol.39 No.5 (May 1990 ).
Fred Glover,Manuel Laguna TABU SEARCH
Rick, E. and Knight , K. Artificial Intelligence 2"d.ed. Singapore: McGrawHill,1991
Mitchell,T.M. Machine Learning.Massachussetts: McGraw-Hill,1994
Quinlan , J.R.C4.5 : Programs for machine learning. California : Morgan Kaufmann,1993.
MCNC Benchmark Circuit ,[path:pub/benchmark_dirs/LGSyth91/twolexample], Marc 1994.
MCNC Benchmark Circuit [19] Vinyoonutakul, S.; Kijsirikul ,B.and Thongtak, A. Binary decision diagrams minimization based on decision tree learning. Proceedings of the IEEE International Symposium on Intelligent Signal Processing and Communication Systems. (1999)
ศิริพรรณ วิญญนันทกุล,บุญเสริมกิจศิริกุล และอาทิตย์ ทองทักษ์. การปรับปรุงวิธี การสร้างแผนภาพตัดสินใจทวิภาคโดย การเรียนรู้ต้นไม้ตัดสินใจ. การประชุมวิชาการทางวิศวกรรมไฟฟ้า ครั้งที่ 22(2542).
บุญเสริม กิจศิริกุล, ปัญญาประดิษฐ์ (Artificial Intelligence), เอกสารคำสอน 2004
Christop Meinel,Thorsten Theobald Algorithms and Data Structures in VLSI Design, Springer-Verlag Berlin Heidelberg 1998.