ولگشت خود پرهیز

الگوریتم

خلاصه :

ولگشت خود پرهیز یا قدم زدن بدون قطع کردن خود به توالی ای از حرکات می‌گویند که از یک نقطه بیش از یک بار عبور نکند.

ویژگی های ولگشت خودپرهیز

در فیزیک محاسباتی، ولگشت خودپرهیز، مسیر زنجیر مانندی در $R^2$ و $R^{3}$ با تعداد مشخصی از نقاط و طول معمولاً مشخص است که مقید شده‌است که خودش یا ولگشت دیگری را قطع نکند. یک سیستم ولگشت خودپرهیز شرایط حجم مستثنی را ارضا می‌کند. پیش‌بینی می‌شود که در ابعاد بالاتر، ولگشت خودپرهیز بیشتر شبیه به ولگشت ساده رفتار کند. ولگشت خودپرهیز و چند ضلعی خودپرهیز نقشی اساسی در مدل کردن توپولوژیکال و رفتار نظریه گره مولکول‌های خطی و حلقوی شکل بازی می‌کنند. ولگشت‌های خودپرهیز فراکتال هستند.

خصوصیات ولگشت‌های خودپرهیز را نمی‌توان از محاسبات تحلیلی بدست آورد، بنابراین برای این امر از شبیه‌سازی‌های عددی استفاده می‌شود. الگوریتم پیووت روشی مرسوم برای شبیه‌سازی زنجیره مارکوف مونت کارلو برای اندازه‌گیری یکنواخت یک ولگشت خودپرهیز با طول $n$ است. محاسبهٔ تعداد گام‌های خودپرهیز در یک شبکهٔ مشخص یکی از مسائل محاسباتی مرسوم است. اگرچه هیچ فرمولی شناخته شده‌ای برای محاسبهٔ تعداد گام‌های خودپرهیز وجود ندارد، اما روش‌هایی برای تخمین آن وجود دارد. حدس زده می‌شود که تعداد این مسیرها یک مسئلهٔ ان پی سخت باشد. در یک شبکهٔ $m\times n$ برای رسیدن از یک گوشه به گوشهٔ مقابل، تعداد:

${m+n \choose m,n}$

پلیمر ها

ولگشت‌های خودپرهیز گاهی برای مدل کردن پلیمرهای خطی استفاده می‌شوند. پلیمرهای خطی، مولکول‌هایی هستند که از واحدهای ساده ای به نام مونومر‌ها به صورت زنجیری تشکیل می‌شوند. این زنجیره‌ها می‌توانند خیلی طولانی شوند بطوریکه گاهی بعضی از آن‌ها شامل 105 $10^{5}$ مونومر می‌شوند. یکی از سوالاتی که برای محققان حوزهٔ پلیمر مهم است، این است که یک زنجیر n-مونومری چند ساختار مختلف می‌تواند به خود بگیرد و همچنین نقطهٔ پایانی در چه فاصله ای از نقطهٔ شروع قرار دارد. این سؤال‌ها را می‌توان به زبان ولگشت‌های خودپرهیز ترجمه کرد و پلیمرها را همان ولگشت‌های خودپرهیزی در نظر گرفت که هر گام برابر یک مونومر باشد و محدودیت خودپرهیزی، حجم مستثنی را مدل می‌کند: «هیچ دو مونومری نمی‌توانند یک نقطه از فضا را اشغال کنند.»

برای پلیمرها عموماً $n$ عدد خیلی بزرگی است، بنابراین طبیعی است که رفتار ولگشت‌های خودپرهیز به ازای حد $n\rightarrow \infty$ برای ما در تحلیل پلیمرها مهم باشد. اگرچه پلیمرها در فضای پیوسته هستند و نه در یک شبکهٔ گسسته، اما مشاهده می‌شود که برای تعداد زیادی از مسائل تخمین گسسته بودن فضا با توجه به بزرگ بودن $n$ ، تخمین خوبی است.

برای پلیمرها مرتبط‌ترین بعد $d=3$ است اما ولگشت‌های خودپرهیز ۲ بعدی هم برای تحلیل پلیمرهایی که بین دو صفحهٔ موازی نزدیک به هم قرار دارند، مهم هستند. اینکه ابعاد ۴ و بالاتر چه ارتباطی با پلیمرها دارند هنوز نامشخص است اما با این حال بررسی رفتار مدل به ازای ابعاد بالاتر می‌تواند مفید باشد.

در ارتباطات

ولگشت‌های خود پرهیز همچنین در نظریه ی شبکه مورد استفاده قرار می‌گیرند. در این مورد معمولاً ولگشت خودپرهیز را یک فرایند پویا (داینامیک) در نظر می‌گیرند به طوریکه در هر گام زمانی، گام بعدی باید از بین یکی از نقاط همسایه انتخاب شود. گام‌ها زمانی به پایان می‌رسند که به یک نقطهٔ بن‌بست برسیم، یعنی جایی که دیگر هیچ‌کدام از نقاط اطراف آزاد نباشند. اخیراً بدست آمده که در مدل اردیش-رنیی، توزیع تعداد گام‌های مسیرهای ولگشت خودپرهیز پویای یاد شده به صورت تحلیلی قابل مقایسه است و از توزیع گمپرتز پیروی می‌کند.