ตรวจจับวัฏจักรในการจำลอง

การจำลองบางข้อถามหาสถานะหลังจากทำขั้นตอนจำนวน มหาศาล เช่น หนึ่งล้านล้านครั้ง การทำทีละขั้นจะไม่มีวันเสร็จทันเวลา ⏳

หากจำนวน สถานะ ที่เป็นไปได้มีจำกัด การจำลองจะต้องกลับมาเจอสถานะเดิมในที่สุด จากจุดนั้นสถานะจะวนซ้ำไปตลอด

เส้นทางมี ช่วงหาง ที่นำเข้าสู่วัฏจักร แล้วมีวงวนที่เกิดซ้ำ การมองเห็นวงวนช่วยให้ข้ามขั้นตอนนับพันล้านขั้นไปได้อย่างรวดเร็ว

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

ก่อนแต่ละขั้น ให้ตรวจสอบว่าสถานะปัจจุบันอยู่ใน รายการที่พบแล้ว หรือไม่ หากอยู่ แสดงว่าคุณเพิ่งปิดวัฏจักรลง

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

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

จำลองต่ออีกเพียงขั้นตอน ที่เหลือจากจุดเริ่มต้นของวัฏจักร สถานะสุดท้ายจะตรงกับสถานะเมื่อถึงขั้นตอน N พอดี

คีย์ของพจนานุกรมต้อง แฮชได้ ดังนั้นให้เปลี่ยนรายการเป็นทูเพิลก่อนจัดเก็บ สถานะที่เปลี่ยนแปลงได้จะใช้เป็นคีย์ไม่ได้

หากสถานะใหญ่เกินกว่าจะจัดเก็บ อัลกอริทึมเต่าและกระต่ายของ Floyd จะค้นหาวัฏจักรโดยใช้ตัวชี้สองตัวและหน่วยความจำเพิ่มเติมเพียงเล็กน้อย

การตรวจจับวัฏจักรเปลี่ยนวงวนที่มีขั้นตอนหนึ่งล้านล้านครั้งซึ่ง เป็นไปไม่ได้ ให้เหลือเพียงไม่กี่พันขั้น การมองเห็นการเกิดซ้ำคือเคล็ดลับทั้งหมด

คุณพบสถานะปัจจุบันเป็นครั้งแรกที่ขั้นตอน s และตอนนี้อยู่ที่ขั้นตอน t

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