Chulalongkorn University Theses and Dissertations (Chula ETD)

การแก้ปัญหาซูโดะกุโดยขั้นตอนวิธีการบรรจวบ

Other Title (Parallel Title in Other Language of ETD)

Solving sudoku problems by coincidence algorithm

Year (A.D.)

2012

Document Type

Thesis

First Advisor

ประภาส จงสถิตย์วัฒนา

Faculty/College

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

Degree Name

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

Degree Level

ปริญญาโท

Degree Discipline

วิศวกรรมคอมพิวเตอร์

DOI

10.58837/CHULA.THE.2012.1275

Abstract

วิทยานิพนธ์ฉบับนี้เป็นการนำเสนอวิธีการแก้ปัญหาเชิงการจัดอย่างซูโดะกุโดยขั้นตอนวิธีการบรรจวบ ซึ่งเป็นขั้นตอนวิธีใหม่ในขั้นตอนวิธีประมาณการแจกแจงในกลุ่มขั้นตอนวิธีเชิงวิวัฒน์ ขั้นตอนวิธีดังกล่าวอาศัยการเรียนรู้เชิงลบควบคู่กับการเรียนรู้เชิงบวกในการหาผลเฉลยที่เป็นไปได้ ซึ่งขั้นตอนวิธีดังกล่าวถูกนำมาสำรวจประสิทธิภาพในหลากหลายปัญหาที่อยู่ในกลุ่มปัญหาเชิงการจัด แล้วว่าสามารถแก้ปัญหากลุ่มดังกล่าวได้อย่างมีประสิทธิภาพเมื่อเทียบกับหลายขั้นตอนวิธีในกลุ่มขั้นตอนวิธีเชิงวิวัฒน์ และ จากผลการทดลอง แสดงให้เห็นว่าขั้นตอนวิธีการบรรจวบสามารถแก้ปัญหาซูโดะกุได้แม่นยำและรวดเร็วขึ้น เมื่อเทียบกับขั้นตอนวิธีในกลุ่มขั้นตอนวิธีเดียวกัน ภายในจำนวนประชากร และจำนวนรุ่นค้นหาที่เท่ากัน

Other Abstract (Other language abstract of ETD)

In this dissertation, we proposed solving a kind of combinatorial problem, Sudoku, by Coincidence Algorithm, COIN. The algorithm is in a class of estimation of distribution algorithms in evolutionary computation. The algorithm makes use of both better and worse genetic materials for finding satisfactory solutions. COIN can outperform many traditional evolutionary algorithms in part of combinatorial optimization. Especially, in experimental results of Sudoku puzzles, Coin converges to the exact solution in fewer number of evaluation functions with more accuracy comparing to the traditional algorithms in the same experimental setting.

Link to Full Text

Share

COinS