ลอจิกในบล็อกง่ายๆ สามารถทำให้คอมพิวเตอร์ได้ออกกำลังกายอย่างหนักโดยไม่คาดคิด

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

ไบนารีอาร์ต

จราจรติดขัด. ในการไขปริศนา Rush Hour ที่ยากนี้ (ด้านบน) เราต้องเคลื่อนรถออกจากทางเพื่อให้รถสีแดงออกไปทางขวา วิธีแก้ปัญหาที่มาพร้อมกับเกมเกี่ยวข้องกับลำดับของ 43 การเคลื่อนไหว

ไบนารีอาร์ต

ตรรกะการเลื่อน การจัดเรียงอย่างง่ายของบล็อกเลื่อน (บนสุด) สามารถใช้เป็นลอจิคัลหรือเกตได้ ถ้าบล็อก A หรือบล็อก B เลื่อนออกไปด้านนอก ลำดับของการเคลื่อนไหวจะอนุญาตให้ C เลื่อนเข้ามา อาร์เรย์ของบล็อกเลื่อนที่ใหญ่ขึ้น (ด้านล่าง) สามารถดำเนินการทางตรรกะที่ซับซ้อนมากขึ้นได้เฮิร์นและดีเมน

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

บาม และ เดอร์ดาโนวิช

ในช่วงไม่กี่ปีที่ผ่านมา ปริศนาบล็อกเลื่อนได้ทำหน้าที่เป็นพื้นฐานสำหรับกลยุทธ์การวางแผนการเคลื่อนไหวแบบใหม่ พวกเขายังดึงดูดความสนใจของนักวิทยาศาสตร์คอมพิวเตอร์ที่สนใจในขีดจำกัดพื้นฐานของการคำนวณ ตัวอย่างเช่น ในการกำหนดเวลาทำงานสัมพัทธ์หรือจำนวนหน่วยความจำที่คอมพิวเตอร์จะต้องใช้แก้ปัญหาประเภทต่างๆ ในรูปแบบที่ยากที่สุด (SN: 5 /6/00 น. 296: การเปลี่ยนแปลงของสถานะทางคณิตศาสตร์ ).

เมื่อพวกเขาเผชิญหน้ากับปริศนา นักวิจัยจะค้นหาว่าคอมพิวเตอร์ต้องใช้ทรัพยากรใดบ้างในการตัดสินใจว่าความท้าทายนั้นแก้ไขได้หรือไม่ เมื่อมีวิธีแก้ปัญหา ผู้ตรวจสอบจะพยายามระบุว่ามีกี่วิธีหรือระบุวิธีที่มีขั้นตอนน้อยที่สุด

ปริศนาบล็อกเลื่อนหนึ่งที่มีบทบาทสำคัญในความพยายามในการวิจัยล่าสุดหลายชิ้นคือ Rush Hour ซึ่งเป็นผลิตภัณฑ์เชิงพาณิชย์ที่จำหน่ายครั้งแรกในสหรัฐอเมริกาในปี 1996 ผู้เล่นเริ่มต้นด้วยบล็อกสี่เหลี่ยมที่มีรูปร่างเหมือนรถยนต์และรถบรรทุก แต่ละชิ้นอยู่ในตำแหน่งที่กำหนดบน ถาดสี่เหลี่ยม และคิดลำดับการเคลื่อนที่ที่ช่วยปลดปล่อยรถเป้าหมายจากการจราจรที่ติดขัดและพาไปยังทางออก

สมัครสมาชิกข่าววิทยาศาสตร์

รับวารสารวิทยาศาสตร์ที่ยอดเยี่ยมจากแหล่งที่น่าเชื่อถือที่สุดส่งตรงถึงหน้าประตูคุณ

ติดตาม

การศึกษาโดย Gary W. Flake และ Eric B. Baum จากสถาบันวิจัย NEC ในเมืองพรินซ์ตัน รัฐนิวเจอร์ซี ระบุว่า Rush Hour เป็นปริศนาที่น่ากลัวอย่างแท้จริง จากมุมมองด้านการคำนวณ การวิเคราะห์ของพวกเขาทำให้ Rush Hour อยู่ในระดับความยากเดียวกับเกมที่ท้าทายอย่าง Othello (SN: 8/16/97, p. 100) แต่ต่ำกว่าหมากรุกและเกมโกะ

“เราพบว่าผลลัพธ์เหล่านี้น่าประหลาดใจเมื่อพิจารณาจากความ เรียบง่ายของเกม” Flake และ Baum กล่าวใน January Theoretical Computer Science

การค้นพบนี้ชี้ให้เห็นว่า “การทำให้รถหลายคันไม่ติดขัดอาจเป็นงานที่ท้าทาย” Flake กล่าว Flake และ Baum บรรยายรายงานการวิจัย Rush Hour ของพวกเขาว่า “ทำไมคุณควรให้ทิปพนักงานจอดรถอย่างไม่เห็นแก่ตัว”

Credit : เว็บตรง