ولگشت خودپرهیز (قدم زدن بدون قطع کردن خود)
From Wikipedia, the free encyclopedia
الگو:شبیهسازی مونت کارلو {{[1]|تاریخ=دسامبر ۲۰۱۸}}
در ریاضیات، ولگشت خود پرهیز یا قدم زدن بدون قطع کردن خود (به انگلیسی: Self Avoiding Walk یا SAW) به توالی ای از حرکات در توری میگویند که از یک نقطه بیش از یک بار عبور نکند. این حالت یکی از حالات نظریه گراف از مسیر (نظریه گراف) است. از دیدگاه ریاضیات به سختی میتوان اطلاعاتی دربارهٔ ولگشت خودپرهیز بدست آورد در حالی که فیزیکدانها موفق شدهاند تعداد زیادی تخمین بدست آورند. این تخمینها با توجه به شبیهسازیهای عددی، به نظر تا حد خوبی قابل قبول هستند.
در فیزیک محاسباتی، ولگشت خودپرهیز، مسیر زنجیر مانندی در و با تعداد مشخصی از نقاط و طول معمولاً مشخص است که مقید شدهاست که خودش یا ولگشت دیگری را قطع نکند. یک سیستم ولگشت خودپرهیز شرایط حجم مستثنی را ارضا میکند. پیشبینی میشود که در ابعاد بالاتر، ولگشت خودپرهیز بیشتر شبیه به ولگشت ساده رفتار کند. ولگشت خودپرهیز و چند ضلعی خودپرهیز نقشی اساسی در مدل کردن توپولوژیکال و رفتار نظریه گره مولکولهای خطی و حلقوی شکل بازی میکنند. ولگشتهای خودپرهیز فراکتال هستند.
خصوصیات ولگشتهای خودپرهیز را نمیتوان از محاسبات تحلیلی بدست آورد، بنابراین برای این امر از شبیهسازیهای عددی استفاده میشود. الگوریتم پیووت روشی مرسوم برای شبیهسازی زنجیره مارکوف مونت کارلو برای اندازهگیری یکنواخت یک ولگشت خودپرهیز با طول است. محاسبهٔ تعداد گامهای خودپرهیز در یک شبکهٔ مشخص یکی از مسائل محاسباتی مرسوم است. اگرچه هیچ فرمولی شناخته شدهای برای محاسبهٔ تعداد گامهای خودپرهیز وجود ندارد، اما روشهایی برای تخمین آن وجود دارد. حدس زده میشود که تعداد این مسیرها یک مسئلهٔ ان پی سخت باشد. در یک شبکهٔ برای رسیدن از یک گوشه به گوشهٔ مقابل، تعداد:
مسیر وجود دارد.