การหาผลเฉลยของเกม Find a Way ด้วยวิธีการหาวิถีแฮมิลโทเนียน

ชื่อนักเรียนผู้จัดทำโครงงานวิทยาศาสตร์

ไพรัลยา เถานิลมณี, เกรียงศักดิ์ สุใจ, อัครวินท์ วีระ

อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์

รุ่งทิวา บุญมาโตน, ศรายุทธ วิริยะคุณานันท์

โรงเรียนที่กำกับดูแลโครงงานวิทยาศาสตร์

โรงเรียนยุพราชวิทยาลัย

ปีที่จัดทำโครงงานวิทยาศาสตร์

พ.ศ. 2565

บทคัดย่อโครงงานวิทยาศาสตร์

เกม Find a Way มีกติกาการเล่นเกม คือ จะต้องลากเส้นผ่านจุดทุกจุดในเกม โดยสามารถลากเส้นได้ตามแนวตั้งและแนวนอนเท่านั้น (ห้ามลากเส้นในแนวทแยง) จากกติกาการเล่นเกม สามารถแทนจุดในเกม Find a Way ด้วยจุดยอดของกราฟ และกำหนดเส้นเชื่อมของกราฟแทนเส้นที่สามารถลากผ่านจุดที่อยู่ติดกันในเกม (ลากเส้นตามแนวตั้งและแนวนอน) จะทำให้ได้แบบจำลองของเกมเป็นรูปกราฟตาราง และผลเฉลยของเกม คือ วิถีแฮมิลโทเนียน ซึ่งเป็นวิถีที่ผ่านจุดทุกจุดของกราฟตารางเพียงครั้งเดียวเท่านั้น โครงงาน เรื่อง การหาผลเฉลยของเกม Find a Way ด้วยวิธีการหาวิถีแฮมิลโทเนียน มีวัตถุประสงค์เพื่อสร้างขั้นตอนวิธีในการหาผลเฉลยของเกม Find a Way โดยใช้เทคนิคการตัดเส้นเชื่อมในกราฟตาราง ให้เป็นวิถีแฮมิลโทเนียน และหาจำนวนผลเฉลยทั้งหมด นอกจากนี้ยังศึกษาจำนวนผลเฉลยของเกม Find a Way ที่เป็นกราฟตารางขนาด 2 * n และ 3 * n เมื่อ n เป็นจำนวนเต็มบวก โดยไม่มีอุปสรรคในเกม โดยใช้ความรู้เรื่องทฤษฎีกราฟและความสัมพันธ์เวียนเกิดมาประยุกต์ใช้ในการพิสูจน์หาจำนวนผลเฉลยของปัญหา อีกทั้งยังมีการประยุกต์ใช้ขั้นตอนวิธีในการหาวิถีแฮมิลโทเนียนของกราฟด้วยเทคนิคการค้นหาเชิงลึก และเทคนิคกำหนดการเชิงพลวัตร่วมกับตัวดำเนินการระดับบิต เพื่อหาผลเฉลยของเกม Find a Way พร้อมทั้งแสดงการเปรียบเทียบประสิทธิภาพของขั้นตอนวิธีทั้งสามด้วยค่าความซับซ้อนด้านเวลาและค่าความซับซ้อนด้านพื้นที่ในรูปของ Big O จากการศึกษาพบว่า สามารถหาวิถีแฮมิลโทเนียนในกราฟตาราง (ผลเฉลยของเกม Find a Way) ได้โดยใช้เทคนิคการตัดเส้นเชื่อม และสามารถหาจำนวนวิถีแฮมิลโทเนียนทั้งหมด (จำนวนผลเฉลยของเกม Find a Way ทั้งหมด) ในกราฟตารางเมื่อกำหนดจุดเริ่มต้นและจุดปลายเป็นจุดสองจุดใด ๆ ในกราฟ และพบว่าผลเฉลยของเกม Find a Way ที่เป็นกราฟตารางขนาด 2 * n และ 3 * n เมื่อ n เป็นจำนวนเต็มบวก โดยไม่มีอุปสรรคในเกม เท่ากับ 2n^2 – 2n + 4 และผลบวกของ 2N(3, n, 2, 1) ,4N(3, n, 1, 1), ผลรวมของ M(i) เมื่อ i เท่ากับ 2 ถึง n - 1 และผลรวมของ 2 * U(i) เมื่อ i เท่ากับ 2 ถึง n – 1 จากการเปรียบเทียบประสิทธิภาพของขั้นตอนวิธีทั้งสามพบว่า เทคนิคกำหนดการเชิงพลวัตร่วมกับตัวดำเนินการระดับบิตมีค่าความซับซ้อนด้านเวลาน้อยที่สุด เท่ากับ O( m^2 * n^2 * 2^mn) เทคนิคการตัดเส้นเชื่อมและเทคนิคการค้นหาเชิงลึกมีค่าความซับซ้อนด้านพื้นที่น้อยที่สุด เท่ากับ O(m * n)