ขั้นตอนวิธีแบบขนานที่ใช้หน่วยความจำอย่างมีประสิทธิภาพ สำหรับหาคำตอบที่ดีที่สุดในปริศนาที่มีการเลื่อนเป็นลำดับ

วรวุธ วรวิชญวงศา

Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/64257

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	ศุภกานต์ พิมลธเรศ	-
dc.contributor.author	วรวุธ วรวิชญวงศา	-
dc.contributor.other	จุฬาลงกรณ์มหาวิทยาลัย. คณะวิทยาศาสตร์	-
dc.date.accessioned	2020-02-26T03:43:43Z	-
dc.date.available	2020-02-26T03:43:43Z	-
dc.date.issued	2561	-
dc.identifier.uri	http://cuir.car.chula.ac.th/handle/123456789/64257	-
dc.description	โครงงานเป็นส่วนหนึ่งของการศึกษาตามหลักสูตรปริญญาวิทยาศาสตรบัณฑิต สาขาวิชาวิทยาการคอมพิวเตอร์. คณะวิทยาศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย ปีการศึกษา 2561	en_US
dc.description.abstract	ปริศนาที่มีการเลื่อนเป็นลำดับเป็นกลุ่มปัญหาสำหรับทดสอบขั้นตอนวิธีในการค้นหาในกราฟเนื่องจากปริศนาที่มีการเลื่อนเป็นลำดับสามารถแทนได้ด้วยกราฟ จึงสามารถค้นหาเส้นทางที่สั้นที่สุดระหว่างสองจุดยอดได้ โดยมักจะให้จุดยอดหนึ่งจุดแทนรูปแบบเริ่มต้นของปัญหา และเส้นทางที่สั้น ที่สุดไปสู่จุดยอดนั้นจะเป็นคำตอบที่ดีที่สุดของปริศนา งานวิจัยนี้จึงออกแบบให้จำนวนเต็มแทนรูปแบบต่าง ๆ ของปัญหา และใช้หน่วยประมวลผลกราฟิกเพื่อเพิ่มความเร็วของขั้นตอนวิธีการค้นหาในกราฟ ผลการทดสอบแสดงให้เห็นว่าขั้นตอนวิธีในงานวิจัยนี้สามารถเพิ่มความเร็วได้ถึงสี่เท่าและแปดเท่าสำหรับปริศนาเรียงแปดเลขและปริศนาเรียงสิบห้าเลขตามลำดับ และลดปริมาณหน่วยความจำที่จำเป็นต้องใช้ลงได้	en_US
dc.description.abstractalternative	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.	en_US
dc.language.iso	th	en_US
dc.publisher	จุฬาลงกรณ์มหาวิทยาลัย	en_US
dc.rights	จุฬาลงกรณ์มหาวิทยาลัย	en_US
dc.title	ขั้นตอนวิธีแบบขนานที่ใช้หน่วยความจำอย่างมีประสิทธิภาพ สำหรับหาคำตอบที่ดีที่สุดในปริศนาที่มีการเลื่อนเป็นลำดับ	en_US
dc.title.alternative	Memory-efficient parallel algorithm for finding optimal solution to sequential move puzzle	en_US
dc.type	Senior Project	en_US
dc.email.advisor	Suphakant.P@Chula.ac.th	-
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

Show simple item record