Chulalongkorn University Theses and Dissertations (Chula ETD)

การสร้างแผนภาพตัดสินใจทวิภาคโดยเทคนิคการเรียนรู้ต้นไม้ตัดสินใจ

Other Title (Parallel Title in Other Language of ETD)

Construction of binary decision diagrams by the decision tree learning technique

Year (A.D.)

1999

Document Type

Thesis

First Advisor

อาทิตย์ ทองทักษ์

Second Advisor

บุญเสริม กิจศิริกุล

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาศาสตร์คอมพิวเตอร์

DOI

10.58837/CHULA.THE.1999.718

Abstract

เนื่องจากแผนภาพตัดสินใจทวิภาคเป็นโครงสร้างข้อมูลที่มีประสิทธิภาพสำหรับการแทนฟังก์ชันบูลีน จึงทำให้แผนภาพตัดสินใจทวิภาคถูกใช้อย่างกว้างขวางกับงานต่าง ๆ ของการออกแบบใช้คอมพิวเตอร์ช่วย แต่ปัญหาหนึ่งที่มักพบในภาพตัดสินใจทวิภาคก็คือ ขนาดของแผนภาพจะขึ้นอยู่กับการเลือกลำดับของตัวแปร ดังนั้นวิธีการหาลำดับของตัวแปรที่ดีจึงเป็นสิ่งสำคัญสำหรับการสร้างแผนภาพตัดสินใจทวิภาคที่มีขนาดเล็ก วิทยานิพนธ์ฉบับนี้ได้นำเสนอวิธีการสร้างแผนภาพตัดสินใจทวิภาค โดยวิธีการที่เสนอจะใช้การเรียนรู้ต้นไม้ตัดสินใจ ซึ่งเป็นเทคนิคหนึ่งของปัญญาประดิษฐ์ สำหรับการหาลำดับตัวแปรเริ่มต้นของแผนภาพตัดสินใจทวิภาค จากนั้นจะลดขนาดแผนภาพตัดสินใจทวิภาคเริ่มต้น ด้วยขั้นตอนวิธีการพัฒนาทีละขั้นที่มีอยู่เดิม เช่น AD2 AD3 AD4 AR ARSA และ SIFTING นอกจากนี้วิทยานิพนธ์ยังได้นำเสนอวิธีการปรับปรุงการเลือกตัวแปรและแผนภาพตัดสินใจทวิภาคที่ใช้ในขั้นตอนวิธีเหล่านี้ด้วย ผลการทดลองกับวงจรวัดเปรียบเทียบสมรรถนะของ MCNC แสดงให้เห็นว่าการสร้างแผนภาพตัดสินใจทวิภาคด้วยวิธีการที่นำเสนอ สามารถให้ขนาดแผนภาพที่เล็กกว่าวิธีการใช้ขั้นตอนวิธีการพัฒนาทีละขั้นเพียงอย่างเดียว โดยเฉพาะอย่างยิ่งการสร้างแผนภาพตัดสินใจทวิภาคด้วยวิธีการที่นำเสนอร่วมกับขั้นตอนวิธี SIFTING จะให้ผลดีที่สุด เมื่อเทียบกับขั้นตอนวิธีการพัฒนาทีละขั้นทุกแบบที่กล่าวข้างต้น

Other Abstract (Other language abstract of ETD)

Since the Binary Decision Diagram is an efficient data structure for representing Boolean functions, it has been widely used in computer-aided design applications. One problem of the Binary Decision Diagram is that its size largely depends on the choice of an ordering of variables. Thus a method of finding good variable ordering is needed for small Binary Decision Diagram construction. This thesis presents a method for the Binary Decision Diagram construction. The method is based on the Decision Tree Learning technique appeared in artificial intelligence. Decision Tree Learning is employed to find an initial variable ordering for the Binary Decision Diagram. Then the initial Binary Decision Diagram is minimized by the gradual improvement algorithms known in the literature such as AD2, AD3, AD4, AR, ARSA and SIFTING. The thesis also presents a method for improving variables and the Binary Decision Diagram selection used in these algorithms. Experiments on the MCNC (Microelectronics Center of North Carolina) benchmark circuits show that the Binary Decision Diagram constructed by the proposed method is smaller than those by the only gradual improvement algorithms. Moreover, the Binary Decision Diagram produced by the proposed method with SIFTING algorithm yields the best of all gradual improvement algorithms above.

Link to Full Text

Share

COinS