Wednesday, August 22, 2007

ซูเปอร์คอมพ์แก้เกม "ลูกบาศก์รูบิค" บิดแค่ 26 ครั้ง


บีซีนิวส์/เดอะการ์เดียน/ดิจิตอลเทรนด์ - 2 นักศึกษาสหรัฐใช้ซูเปอร์คอมพิวเตอร์แก้วิธีหมุน "ลูกบาศก์รูบิค" แค่เพียง 26 ครั้ง เข้าใกล้ "จำนวนแห่งเทพ" ซึ่งเป็นการหมุนน้อยครั้งที่สุดให้ลูกบาศก์คืนสภาพ

หลายคนคงเคยเห็น "ลูกบาศก์รูบิค" (Rubik's Cube) ของเล่นที่ให้เราบิดเพื่อให้สี่เหลี่ยมแต่ละด้านกลับคืนสู่รูปเดิม ซึ่งหลายคนอาจจะท้อจนอยากปาของเล่นทิ้งไปไกลๆ ขณะบางคนอาจใช้เวลาแค่ 5 นาทีจัดการกับความยุ่งเหยิงบนลูกบิดให้คืนสู่ความเรียบร้อย แต่ไม่ว่าจะแน่แค่ไหนคงต้องยอมแพ้ 2 นักศึกษาสหรัฐที่ใช้ "ซูเปอร์คอมพิวเตอร์" แก้เกมด้วยการบิดเพียงแค่ 26 ครั้ง และคาดว่าจะทำได้น้อยกว่านี้อีก

แดนเนียล คันเกิล (Daniel Kunkle) และ ยีน คูเปอร์แมน (Gene Cooperman) 2 นักศึกษาคอมพิวเตอร์จากมหาวิทยาลัยนอร์ธอีสเทิร์น (Northeastern University) ในบอสตัน แมสซาซูเซ็ตส์ สหรัฐอเมริกา ได้ทำงานวิจัยโดยอาศัยซูเปอร์คอมพิวเตอร์ค้นวิธีแก้เกมลูกบาศก์รูบิค ด้วยการบิดจำนวนครั้งน้อยที่สุด

จากการทำงานของซูเปอร์คอมพิวเตอร์อย่างต่อเนื่อง 63 ชั่วโมง ได้ผลว่าสามารถบิดลูกบาศก์รูบิคให้กลับคืนสู่รูปร่างเดิมด้วยการหมุนแค่ 26 ครั้ง และนักวิจัยทั้ง 2 ยังเชื่อว่าจะสามารถหาวิธีบิดด้วยจำนวนครั้งที่น้อยกว่านี้อีก โดยสถิติดีที่สุดก่อนหน้านี้คือ 27 ครั้ง

ทั้งนี้การหาตำแหน่งที่เป็นไปได้ของลูกบาศก์ 43 ล้านล้านล้านล้านตำแหน่ง (43x1024) ก็ยังเป็นเรื่องที่ยุ่งเหยิงเกินไปสำหรับคอมพิวเตอร์ ดังนั้น 2 นักศึกษาจึงได้การแก้ปัญหา 2 ขั้นตอน

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

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

การค้นพบของทั้ง 2 ทำให้อาจนำไปสู่สิ่งที่เรียกว่า "จำนวนแห่งเทพ" (God’s number) ซึ่งเป็นจำนวนการบิดลูกบาศก์รูบิคที่น้อยที่สุดให้คืนสู่สภาพเดิม โดยตามทฤษฎีแล้วจำนวนดังกล่าวจะอยู่ในช่วง 20 ต้นๆ

คันเกิลและคูเปอร์แมนเปิดเผยผลการวิจัยดังกล่าว ระหว่างการประชุมนานาชาติด้านการคำณวนเชิงสัญญลักษณ์และพีชคณิต ที่วอเตอร์ลู ออตาริโอ แคนาดา (International Symposium on Symbolic and Algebraic Computation in Waterloo, Ontario)

ที่มา: http://www.manager.co.th/
Link: http://www.manager.co.th/Science/ViewNews.aspx?NewsID=9500000098077

No comments: