กลับไปหน้าบทความ

อ่าน 1 นาที

อัลกอริทึมการหมุน

อั ลกอริทึม Pivot เป็นรูปแบบหนึ่งของ อัลกอริทึม Monte Carlo ที่ใช้ในการสร้างการกำหนดค่าของ การเดินที่หลีกเลี่ยงตัวเอง โดยทั่วไปบน แลตทิซ [ 1 ] อั...

อัลกอริทึมการหมุน

อัลกอริทึม Pivot บนตารางสี่เหลี่ยมจัตุรัส
ตัวอย่างของการใช้อัลกอริทึมแบบ Pivot ในการปรับเปลี่ยนโครงสร้างของการเดินแบบหลีกเลี่ยงตัวเองระยะสั้นบนโครงตาข่ายสี่เหลี่ยม โดยเลือกโมโนเมอร์สีแดงเป็นจุดหมุน หากหมุนตามเข็มนาฬิการอบจุดนั้น โมโนเมอร์สองตัวจะครอบครองตำแหน่งเดียวกัน และการเคลื่อนที่นั้นจะถูกปฏิเสธ หากหมุนทวนเข็มนาฬิกา การเคลื่อนที่นั้นจะได้รับการยอมรับ

อัลกอริทึม Pivotเป็นรูปแบบหนึ่งของอัลกอริทึม Monte Carloที่ใช้ในการสร้างการกำหนดค่าของการเดินที่หลีกเลี่ยงตัวเองโดยทั่วไปบนแลตทิซ [ 1 ] อัลกอริทึมนี้โดยทั่วไปจะเริ่มต้นด้วยเส้นตรงที่ประกอบด้วยจุด N จุดบนแลตทิซ และแปลงเป็นรูปร่างที่ไม่เป็นระเบียบที่เรียกว่าการเดิน ซึ่งไม่มีจุดสองจุดใดบนการเดินที่ครอบครองไซต์เดียวกันบนแลตทิซ ในสองมิติ อัลกอริทึมนี้ทำงานตามขั้นตอนต่อไปนี้:

  1. เลือกจุดสุ่มpระหว่าง 1 ถึงNเพื่อใช้เป็นจุดหมุน การทำเช่นนี้จะแบ่งการเดินออกเป็นสองส่วน ส่วนหนึ่งมีความยาวpและอีกส่วนหนึ่งมีความยาว ( Np )
  2. สุ่มเลือกด้านใดด้านหนึ่งของจุดที่จะใช้เป็นจุดหมุน
  3. สุ่มเลือกการแปลงเช่นการหมุน 90, 180 หรือ 270 องศา หรือการสะท้อนเกี่ยวกับแกนแนวนอนหรือแนวตั้ง แล้วนำไปใช้กับจุดบนด้านที่เลือกของจุดหมุน
  4. ตรวจสอบว่ามีจุดสองจุดใดอยู่บนตำแหน่งเดียวกันบนตารางหรือไม่ ถ้าใช่ ให้ตัดจุดหมุนนั้นทิ้งแล้วลองใหม่ ถ้าไม่อยู่บนตำแหน่งเดียวกัน ให้ลองใช้จุดหมุนอื่นต่อไป

การกำหนดค่าที่สร้างขึ้นโดยอัลกอริทึมให้ข้อมูลเกี่ยวกับการจัดเรียงของการเดินแบบหลีกเลี่ยงตัวเอง และใช้เพื่อทำความเข้าใจฟิสิกส์ของพอลิเมอร์ซึ่งสามารถประมาณได้ว่าเป็นการเดินแบบหลีกเลี่ยงตัวเอง อัลกอริทึมนี้คิดค้นโดย Moti Lal ในปี 1969 [ 2 ]สามารถนำไปใช้งานได้อย่างมีประสิทธิภาพ โดยมีความซับซ้อนในการคำนวณที่ทำให้สามารถสร้าง การเดินที่มีความยาว N ได้ในเวลาที่แปรผันตามลอการิทึม ของNซึ่งเรียกว่าเวลาลอการิทึม[ 1 ]

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Pivot_algorithm&oldid=1312028742 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ อัลกอริทึมการหมุน

อั ลกอริทึม Pivot เป็นรูปแบบหนึ่งของ อัลกอริทึม Monte Carlo ที่ใช้ในการสร้างการกำหนดค่าของ การเดินที่หลีกเลี่ยงตัวเอง โดยทั่วไปบน แลตทิซ [ 1 ] อั...