Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/64257
| Title: | ขั้นตอนวิธีแบบขนานที่ใช้หน่วยความจำอย่างมีประสิทธิภาพ สำหรับหาคำตอบที่ดีที่สุดในปริศนาที่มีการเลื่อนเป็นลำดับ |
| Other Titles: | Memory-efficient parallel algorithm for finding optimal solution to sequential move puzzle |
| Authors: | วรวุธ วรวิชญวงศา |
| Advisors: | ศุภกานต์ พิมลธเรศ |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิทยาศาสตร์ |
| Advisor's Email: | Suphakant.P@Chula.ac.th |
| Issue Date: | 2561 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | ปริศนาที่มีการเลื่อนเป็นลำดับเป็นกลุ่มปัญหาสำหรับทดสอบขั้นตอนวิธีในการค้นหาในกราฟเนื่องจากปริศนาที่มีการเลื่อนเป็นลำดับสามารถแทนได้ด้วยกราฟ จึงสามารถค้นหาเส้นทางที่สั้นที่สุดระหว่างสองจุดยอดได้ โดยมักจะให้จุดยอดหนึ่งจุดแทนรูปแบบเริ่มต้นของปัญหา และเส้นทางที่สั้น ที่สุดไปสู่จุดยอดนั้นจะเป็นคำตอบที่ดีที่สุดของปริศนา งานวิจัยนี้จึงออกแบบให้จำนวนเต็มแทนรูปแบบต่าง ๆ ของปัญหา และใช้หน่วยประมวลผลกราฟิกเพื่อเพิ่มความเร็วของขั้นตอนวิธีการค้นหาในกราฟ ผลการทดสอบแสดงให้เห็นว่าขั้นตอนวิธีในงานวิจัยนี้สามารถเพิ่มความเร็วได้ถึงสี่เท่าและแปดเท่าสำหรับปริศนาเรียงแปดเลขและปริศนาเรียงสิบห้าเลขตามลำดับ และลดปริมาณหน่วยความจำที่จำเป็นต้องใช้ลงได้ |
| Other Abstract: | Sequential move puzzle is a group of problems that is usually used for testing graph searching algorthms. Since sequential move puzzle can be represented by a graph, the shortest path between any vertices can be found easily. For such puzzle, one of vertices will be an initial configuration and the shortest path to that vertex will be an optimal solution to the puzzle. In this research, each configuration will be assigned by distinct integer and GPU is used to accelerate the graph searching algorithm. The result shows that the proposed algorithm can speed up by x4 and x8 for 8-puzzle and 15-puzzle respectively and reduce the memory used during the calculation. |
| Description: | โครงงานเป็นส่วนหนึ่งของการศึกษาตามหลักสูตรปริญญาวิทยาศาสตรบัณฑิต สาขาวิชาวิทยาการคอมพิวเตอร์. คณะวิทยาศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย ปีการศึกษา 2561 |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/64257 |
| Type: | Senior Project |
| Appears in Collections: | Sci - Senior Projects |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| worawut_W_Se_2561.pdf | 9.02 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.