ในทางคณิตศาสตร์การเดินที่ไม่วนซ้ำตัวเอง ( SAW ) คือลำดับของการเคลื่อนที่บนโครงข่าย ( เส้นทางบนโครงข่าย ) ที่ไม่ผ่านจุดเดิมมากกว่าหนึ่งครั้ง นี่เป็นกรณีพิเศษของแนวคิดเส้นทางในทฤษฎีกราฟรูปหลายเหลี่ยมที่ไม่วนซ้ำตัวเอง ( SAP ) คือการเดินที่ไม่วนซ้ำตัวเองแบบปิดบนโครงข่าย ความรู้เกี่ยวกับเรื่องการเดินที่ไม่วนซ้ำตัวเองจากมุมมองทางคณิตศาสตร์นั้นยังมีน้อยมาก แม้ว่านักฟิสิกส์จะเสนอข้อสันนิษฐานมากมายที่เชื่อว่าเป็นจริงและได้รับการสนับสนุนอย่างมากจากการจำลองเชิงตัวเลขก็ตาม

ในฟิสิกส์เชิงคำนวณ เส้นทางเดินที่หลีกเลี่ยงตัวเอง (Self-avoiding walk หรือ ^{SAW) คือ}เส้นทางคล้ายลูกโซ่ในR²หรือR³ที่มีจำนวนจุดเชื่อมต่อที่แน่นอน โดยทั่วไปมีความยาวช่วงก้าวคงที่ และมีคุณสมบัติที่ไม่ตัดกับตัวเองหรือเส้นทางเดินอื่น ระบบของ SAW จะเป็นไปตามเงื่อนไขปริมาตรที่ถูกกีดกัน ( Excluded volume condition) ในมิติ ที่ สูงกว่า เชื่อกันว่า SAW จะมีพฤติกรรมคล้ายกับเส้นทางเดินสุ่ม ทั่วไป

SAW และ SAP มีบทบาทสำคัญในการสร้างแบบจำลอง พฤติกรรม ทางทอพอโลยีและทฤษฎีปมของโมเลกุลที่มีลักษณะคล้ายเส้นด้ายและห่วง เช่นโปรตีนอันที่จริง SAW อาจได้รับการแนะนำครั้งแรกโดยนักเคมีPaul Flory ^{[ 1 ]} เพื่อจำลองพฤติกรรมในชีวิตจริงของเอนทิตีที่มีลักษณะคล้ายโซ่ เช่นตัวทำละลายและพอลิเมอร์ซึ่งปริมาตรทางกายภาพไม่อนุญาตให้มีการครอบครองจุดเชิงพื้นที่เดียวกันหลายครั้ง

SAW เป็นแฟรกทัลตัวอย่างเช่น ในd = 2 มิติ แฟรกทัลคือ 4/3 สำหรับd = 3จะใกล้เคียงกับ 5/3 ในขณะที่สำหรับd ≥ 4มิติแฟรกทัลคือ2มิตินี้เรียกว่ามิติวิกฤตบน ซึ่งปริมาตรที่ถูกกีดกันนั้นมีค่าน้อยมาก SAW ที่ไม่ตรงตามเงื่อนไขปริมาตรที่ถูกกีดกันได้รับการศึกษาเมื่อเร็ว ๆ นี้เพื่อสร้างแบบจำลองเรขาคณิตพื้นผิว ที่ชัดเจน ซึ่งเป็นผลมาจากการขยายตัวของ SAW ^{[ 2 ]}ขนาดเฉลี่ยของการเดินที่หลีกเลี่ยงตัวเองจะเพิ่มขึ้นตามความยาวตามเลขชี้กำลังที่เป็นส่วนกลับของมิติแฟรกทัลรัศมีไจเรชันของ SAW ขึ้นอยู่กับกำลัง 3/4 ของความยาวในสองมิติ และประมาณกำลัง 3/5 ในสามมิติ

คุณสมบัติของ SAW ไม่สามารถคำนวณได้ด้วยวิธีวิเคราะห์ ดังนั้นจึงต้องใช้การจำลอง เชิงตัวเลข อัลกอริทึม Pivotเป็นวิธีการทั่วไปสำหรับ การจำลอง Markov chain Monte Carloสำหรับการวัด แบบสม่ำเสมอ ใน เส้นทางเดินหลีกเลี่ยงตัวเอง nขั้นตอน อัลกอริทึม Pivot ทำงานโดยการเลือกเส้นทางเดินหลีกเลี่ยงตัวเองและสุ่มเลือกจุดหนึ่งบนเส้นทางนั้น จากนั้นใช้ การแปลง แบบสมมาตร (การหมุนและการสะท้อน) กับเส้นทางนั้นหลังจาก ขั้นตอนที่ nเพื่อสร้างเส้นทางเดินใหม่

การคำนวณจำนวนการเดินที่หลีกเลี่ยงตัวเองในแลตทิซที่กำหนดเป็นปัญหาการคำนวณ ทั่วไป ปัจจุบันยังไม่มีสูตรที่ทราบแน่ชัด แม้ว่าจะมีวิธีการประมาณที่เข้มงวดก็ตาม^{[ 3 ] [ 4 ]}

หนึ่งในปรากฏการณ์ที่เกี่ยวข้องกับการเดินแบบหลีกเลี่ยงตัวเองและแบบจำลองฟิสิกส์เชิงสถิติโดยทั่วไปคือแนวคิดเรื่องความเป็นสากลกล่าวคือ ความเป็นอิสระของตัวแปรที่สังเกตได้ในระดับมหภาคจากรายละเอียดในระดับจุลภาค เช่น การเลือกแลตทิซ ปริมาณสำคัญอย่างหนึ่งที่ปรากฏในข้อสันนิษฐานสำหรับกฎสากลคือค่าคงที่การเชื่อมต่อซึ่งกำหนดไว้ดังนี้ ให้c _nแทนจำนวนการเดินแบบหลีกเลี่ยงตัวเองn ขั้น เนื่องจากทุก การเดินแบบหลีกเลี่ยงตัวเอง( n + m ) ขั้นสามารถแยกย่อยเป็นการ เดินแบบหลีกเลี่ยงตัวเองn ขั้นและ การเดินแบบหลีกเลี่ยงตัวเองm ขั้นได้ ดังนั้น c _{n + m} ≤ c _n c _mดังนั้นลำดับ{log c _n }จึงเป็นลำดับย่อยบวกและเราสามารถใช้ทฤษฎีบทของ Feketeเพื่อแสดงว่าลิมิตต่อไปนี้มีอยู่:

${\displaystyle \mu =\lim _{n\to \infty }c_{n}^{\frac {1}{n}}.}$

μเรียกว่าค่าคงที่การเชื่อมต่อเนื่องจากc _nขึ้นอยู่กับแลตติซเฉพาะที่เลือกสำหรับการเดิน ดังนั้นμก็เช่นกัน ค่าที่แน่นอนของμเป็นที่ทราบเฉพาะสำหรับแลตติซหกเหลี่ยม ซึ่งค้นพบโดยStanislav SmirnovและHugo Duminil-Copinโดยมีค่าเท่ากับ: ^{[ 5 ]}

${\displaystyle {\sqrt {2+{\sqrt {2}}}}.}$

สำหรับแลตทิซอื่นๆμได้รับการประมาณค่าเชิงตัวเลขเท่านั้น และเชื่อกันว่าไม่ใช่จำนวนพีชคณิต ด้วยซ้ำ มีการคาดการณ์ว่า^{[ 6 ]}

${\displaystyle c_{n}\approx \mu ^{n}n^{\frac {11}{32}}}$

เมื่อn → ∞โดยที่μขึ้นอยู่กับโครงสร้างแลตทิซ แต่การแก้ไขตามกฎกำลังไม่ขึ้นอยู่กับแลตทิซ กล่าวอีกนัยหนึ่งคือ เชื่อกันว่ากฎนี้เป็นสากล ${\displaystyle n^{\frac {11}{32}}}$

การเดินแบบหลีกเลี่ยงตัวเองที่เติบโตขึ้น (GSAW) เป็นกระบวนการไดนามิกที่การเดินเริ่มต้นที่จุดกำเนิดของโครงข่ายและก้าวไปยังไซต์ที่ว่างอยู่โดยสุ่ม เมื่อไม่มีไซต์ที่อยู่ติดกันที่ว่างอยู่ การเดินนั้นจะติดกับดัก คล้ายกับสถานการณ์ตอนจบในวิดีโอเกมSnakeบนโครงข่ายสี่เหลี่ยมจัตุรัสจากการจำลองด้วยคอมพิวเตอร์พบว่าจำนวนขั้นตอนโดยเฉลี่ยที่การเดินแบบหลีกเลี่ยงตัวเองที่เติบโตขึ้นไปถึงนั้นอยู่ที่ประมาณ 71 ^{[ 7 ]}การเดินที่สั้นที่สุดที่นำไปสู่การติดกับดักบนโครงข่ายสี่เหลี่ยมจัตุรัสคือหกขั้นตอน และสามารถทำได้โดยเริ่มต้นจากโครงข่ายที่ว่างอยู่และเคลื่อนที่ขึ้น ขวา ขวา ลง ลง ซ้าย และขึ้น จำนวนขั้นตอนโดยเฉลี่ยในการติดกับดักขึ้นอยู่กับโครงข่ายหรือเครือข่าย โดยจะคล้ายกันสำหรับโครงข่ายรังผึ้งแต่ใกล้เคียงกับ 78 สำหรับโครงข่ายสามเหลี่ยมความยาวการดักจับโดยเฉลี่ยจะสูงกว่ามากในสามมิติ โดยใกล้เคียงกับ 4000 สำหรับโครงตาข่ายลูกบาศก์แบบง่าย [ ^{8 ] สถิติ}ของการเดินหลีกเลี่ยงตัวเองแบบดั้งเดิมนั้นถือว่าการเดินแต่ละครั้งที่มีความยาวที่กำหนดมีโอกาสเท่ากัน ซึ่งไม่เป็นเช่นนั้นสำหรับ GSAW ตัวอย่างเช่น มี SAW โครงตาข่ายสี่เหลี่ยมจัตุรัส 100 เส้นที่มีความยาว 4 เริ่มต้นที่จุดกำเนิด และสี่เส้นที่เป็นเส้นตรงโดยสมบูรณ์ ดังนั้นจึงมีความน่าจะเป็น 0.04 ที่ SAW ดังกล่าวจะเป็นเส้นตรง อย่างไรก็ตาม GSAW จะต้องก้าวแรกไปในทิศทางใดก็ได้ด้วยความน่าจะเป็น 1 ก้าวที่สองในทิศทางเดียวกันด้วยความน่าจะเป็น 1/3 เช่นเดียวกับก้าวที่สามและสี่ ดังนั้นความน่าจะเป็นที่ GSAW จะเป็นเส้นตรงคือ 1/81≈0.012 ด้วยเหตุนี้ GSAW จึงได้รับการสังเกตเชิงประจักษ์ในการจำลองว่ามีเลขชี้กำลังการปรับขนาดที่เล็กกว่า (ความสัมพันธ์ระหว่างรัศมีไจเรชัน เฉลี่ย และความยาว) กว่า 3/4 ที่ทำนายโดยแบบจำลอง Flory และพบว่าใกล้เคียงกับ 0.68 ^{[ 9 ]}

รูปหลายเหลี่ยมที่หลีกเลี่ยงตัวเองในสามมิติอาจก่อให้เกิดปมได้บนโครงตาข่ายลูกบาศก์แบบง่ายรูปหลายเหลี่ยมที่หลีกเลี่ยงตัวเองที่สั้นที่สุดที่เกิดปมคือปมรูปใบไม้สามแฉกซึ่งครอบครองจุดยอด 24 จุด^{[ 10 ]} เมื่อพิจารณารูปหลายเหลี่ยมที่หลีกเลี่ยงตัวเองที่มีความยาวมากขึ้น ความน่าจะเป็นที่จะพบปมก็จะเพิ่มขึ้น มีการพิสูจน์แล้วว่าเมื่อความยาวของ SAP ที่เลือกแบบสุ่มเพิ่มขึ้น ความน่าจะเป็นที่จะพบ ปม ที่ไม่ เกิดปม จะลดลงแบบเลขชี้กำลังซึ่งหมายความว่าความน่าจะเป็นที่รูปหลายเหลี่ยมที่หลีกเลี่ยงตัวเองจะเกิดปมจะเข้าใกล้ 100% เมื่อความยาวเพิ่มขึ้น ความยาวของ SAP ที่ความน่าจะเป็นของการเกิดปมบนโครงตาข่ายลูกบาศก์แบบศูนย์กลางหน้าถึง 50% อยู่ที่ประมาณ 100,000 และอาจแตกต่างกันไปในโครงตาข่ายอื่นๆ^{[ 11 ]} การเดินที่หลีกเลี่ยงตัวเองซึ่งไม่ได้ปิดเป็นรูปหลายเหลี่ยมอาจก่อให้เกิดการพันกันซึ่งโดยทั่วไปเรียกว่าปม แต่สิ่งเหล่านี้จะไม่ถือว่าเป็นปมอย่างเป็นทางการในทฤษฎีปมเว้นแต่ปลายทั้งสองของการเดินจะเชื่อมต่อกันในบางวิธี

การเดินแบบหลีกเลี่ยงตัวเองยังได้รับการศึกษาในบริบทของทฤษฎีเครือข่ายด้วย^{[ 12 ]}ในบริบทนี้ เป็นเรื่องปกติที่จะถือว่า SAW เป็นกระบวนการแบบไดนามิก โดยที่ในแต่ละขั้นตอนเวลา ผู้เดินจะกระโดดแบบสุ่มระหว่างโหนดที่อยู่ติดกันของเครือข่าย การเดินจะสิ้นสุดลงเมื่อผู้เดินไปถึงสถานะทางตัน ซึ่งจะไม่สามารถไปยังโหนดที่ยังไม่ได้เยี่ยมชมใหม่ได้อีกต่อไป เมื่อเร็วๆ นี้พบว่าบน เครือข่าย Erdős–Rényiการกระจายความยาวเส้นทางของ SAW ที่เติบโตแบบไดนามิกดังกล่าวสามารถคำนวณได้ทางวิเคราะห์ และเป็นไปตามการกระจายแบบ Gompertz [ ^{13 ] สำหรับ}เครือข่ายใดๆ การกระจายความยาวเส้นทางของการเดินการกระจายระดับของเครือข่ายที่ยังไม่ได้เยี่ยมชม และ การกระจาย เวลาการชนครั้งแรกไปยังโหนด สามารถหาได้โดยการแก้ชุดสมการเวียนเกิดที่เชื่อมโยงกัน^{[ 14 ]}

พิจารณาการวัดแบบเอกรูปบนการเดินแบบหลีกเลี่ยงตัวเองn ขั้นในระนาบเต็ม ปัจจุบันยังไม่ทราบแน่ชัดว่าลิมิตของการวัดแบบเอกรูปเมื่อ n → ∞จะเหนี่ยวนำให้เกิดการวัดบนการเดินแบบอนันต์ในระนาบเต็มหรือไม่ อย่างไรก็ตามแฮร์รี่ เคสเทนได้แสดงให้เห็นว่าการวัดดังกล่าวมีอยู่สำหรับการเดินแบบหลีกเลี่ยงตัวเองในระนาบครึ่ง หนึ่งในคำถามสำคัญที่เกี่ยวข้องกับการเดินแบบหลีกเลี่ยงตัวเองคือ การมีอยู่และความไม่แปรเปลี่ยนเชิงคอนฟอร์มัล ของลิมิตการปรับ ขนาด นั่นคือ ลิมิตเมื่อความยาวของการเดินเข้าสู่ค่าอนันต์และตาข่ายของแลตทิซเข้าสู่ศูนย์ ลิมิตการปรับขนาดของการเดินแบบหลีกเลี่ยงตัวเองนั้นคาดการณ์ว่าสามารถอธิบายได้ด้วยวิวัฒนาการของ Schramm–Loewnerโดยมีพารามิเตอร์κ = ⁠8/3⁠ .

• ปรากฏการณ์วิกฤต  – ฟิสิกส์ที่เกี่ยวข้องกับจุดวิกฤต
• เส้นทางแฮมิลโทเนียน  – เส้นทางในกราฟที่ผ่านจุดยอดแต่ละจุดเพียงครั้งเดียวเท่านั้น
• การเดินของอัศวิน  – ชุดโจทย์ปัญหาทางคณิตศาสตร์บนกระดานหมากรุก
• การเดินแบบสุ่ม  – กระบวนการสร้างเส้นทางจากก้าวเดินแบบสุ่มจำนวนมาก
• งู  – ประเภทเกมวิดีโอ
• ความเป็นสากล  – แนวคิดในกลศาสตร์เชิงสถิติ
• เส้นโค้งที่เติมเต็มพื้นที่ – ทั้งหมดเป็นเส้นโค้งที่ไม่ทับซ้อนกันเอง

• ลำดับ OEIS A007764 (จำนวนเส้นทางเดินของหมากรุกที่ไม่ตัดกัน (หรือหลีกเลี่ยงตัวเอง) ที่เชื่อมมุมตรงข้ามของตาราง n x n) — จำนวนเส้นทางเดินที่หลีกเลี่ยงตัวเองที่เชื่อมมุมตรงข้ามของ ตาราง N × NสำหรับNตั้งแต่ 0 ถึง 12 รวมถึงรายการเพิ่มเติมจนถึงN = 21 ด้วย
• ไวส์สไตน์, เอริค ดับเบิลยู. "การเดินที่หลีกเลี่ยงตัวเอง" . MathWorld .
• แอปเพล็ต Java สำหรับการเดินแบบหลีกเลี่ยงสิ่งกีดขวางใน 2 มิติ
• การใช้งาน Python ทั่วไปเพื่อจำลอง SAW และการขยาย FiberWalk บนโครงข่ายสี่เหลี่ยมจัตุรัสในมิติ n
• ซอฟต์แวร์ Norrisสำหรับสร้างคลื่นเสียงพื้นผิว (SAW) บนลูกบาศก์เพชร