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

Abstract

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