مساله ی گام برداری تصادفی

[arash69]

مساله ی گام برداری تصادفی
تعداد زیادی برنامه وجود دارد که مجموعا تحت مسایل " گام برداری تصادفی " شناخته می شوند و از مسایل مورد علاقه ی دانشمندان ریاضی بوده است.حل تمام و حتی ساده ترین این مسایل تا حد زیادی مشکل بوده و اکثر آنها غیر قابل حل باقی مانده اند.
یکی از این مسایل می تواند به صورت زیر مطرح گردد:
" یک مورچه در یک چهارگوشه و در موزاییک وسط کف یک اتاق مستطیلی به اندازه ی n*m موزاییک قرار
دارد.این مورچه به صورت تصادفی از یک خانه به خانه ی دیگر (احتمالا به دنبال دانه) سرگردان است.فرض نمایید
که این مورچه بتواند از خانه ی فعلی خود به هریک از هشت خانه ی مجاور با احتمال مساوی حرکت کند (مگر به
دیوار برخورد نماید). چه مدت طول خواهد کشید که این مورچه از روی تمام موزاییک های کف اتاق حداقل یک مرتبه عبور نماید؟ "


مشکلات مساله ای مانند این مساله در حل آن با روش های نظریه ی احتمالات است.پاسخ به این مساله به وسیله ی
کامپیوتر بسیار آسان می باشد. روش انجام این کار " شبیه سازی " نامیده می شود. این روش به میزان زیادی در
صنایع،مسایل ترافیکی و کنترل موجودی انبار و غیره به کار می رود.


مسئله را می توان با استفاده از روش زیر شبیه سازی کرد: در مساله از یک آرایه ی n*m به نام count برای نمایش
تعداد دفعاتی که مورچه به هر موزاییک روی کف می رسد،استفاده می شود.تمام خانه های این آرایه در ابتدا صفر
فرض می شوند.وضعیت مورچه بر روی کف به وسیله ی مختصات (ibug,jbug) مشخص می گردد.هشت حرکت
ممکن مورچه به وسیله موزاییک های واقع شده در (ibug + imove[k] , jbug + jmove[k]) (اگر 0<=k<=7
باشد)،نشان داده می شود:


imove[0]= -1 jmove[0]= 1



imove[1]= 0 jmove[1]= 1



imove[2]= 1 jmove[2]= 1



imove[3]= 1 jmove[3]= 0



imove[4]= 1 jmove[4]= -1



imove[5]= 0 jmove[5]= -1



imove[6]= -1 jmove[6]= -1



imove[7]= -1 jmove[7]= 0



یک گام برداری تصادفی به یکی از هشت مربع با تولید یک مقدار تصادفی بین 0 و 7 برای k که شبیه سازی می
شود. البته مورچه نمی تواند خارج از چهار گوشه حرکت نماید و بنابراین مختصاتی که نشان دهنده ی دیوار هستند باید

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

برنامه ای بنویسید که آزمایش فوق را شبیه سازی نماید.برنامه ی شما باید دارای شرایط زیر باشد:
(الف) برای تمام مقادیر n و m ، 2<n<=40 و 2<m<=20 درست کار کند.
(ب)برنامه را برای
(1) n=15 و m=15 و نقطه ی شروع (9,9)
(2) n=39 و m=19 و نقطه ی شروع (0,0)
اجرا کنید.
(پ) تعداد تکرار یعنی حداکثر تعداد موزاییک هایی که مورچه می تواند وارد شود ، محدود است(این کار باعث اجتناب از قفل کردن در یک حلقه ی نامحدود می شود)،برای این تمرین حد تکرار برابر با حد اکثر 50000 بار کافی است.
(ت) در هر بار آزمایش
(1) تعداد کل حرکت های مجازی که مورچه انجام می دهد
(2) آرایه ی نهایی count (این آرایه چگالی مسیر یعنی تعداد دفعاتی که هر موزاییک کف در طی آزمایش طی می شود را نشان می دهد) را چاپ کنید.
این تمرین توسط استیو السون (Steve Olson) مطرح شده است.


این در واقع یه مساله ای توی درس ساختمان داده هست،راستش من نمی دونم واقعا بایستی از کجا شروع کنم و چیکار کنم، اگه میشه راهنماییم کنید.