الگوریتم های جستوجوی آنلاین

الگوریتم های جستوجوی آنلاین
الگوریتم های جست وجوی آفلاین قبل از ورود به دنیای واقعی، جواب را محاسبه میکنند و سپس آن جواب را اجرا میکنند. بر عکس، در جست وجوی آنلاین، عامل با یک در میان کردن محاسبات و فعالیت کارش را انجام میدهد، یعنی ابتدا فعالیتی را انجام میدهد، سپس محیط را مشاهده میکند و فعالیت بعدی را محاسبه میکند. جست وجوی آنلاین در محیط های پویا و نیمه پویا مفید است. برای محیط های غیر قطعی نیز مفید است زیرا اجازه میدهد که عامل محاسبات خود را بر روی احتمالاتی متمرکز کند که واقعا رخ خواهند داد.
الگوریتم های جست وجوی آنلاین برای محیط های ناشناخته ضروری هستند که در این محیط ها عامل نمیداند چه حالتهایی وجود دارد و فعالیتش چه کاری انجام میدهد. در این محیط ناشناخته عامل با مسئله اکتشاف مواجه است و باید فعالیت خود را به عنوان تجربه به کار گیرد تا نتیجه بگیرد که چه کای باید انجام دهد.
مسئله جستوجوی آنلاین به جای فرآیندهای محاسباتی محض باید با استفاده از عامل مجری فعالیتها حل شوند. فرض کنیم عامل فقط موارد زیر را میداند:
► ACTION(s) که لیستی از فعالیت های مجاز در حالت s را برمیگرداند.
► تابع هزینه مرحله ای c(s , a , s’) ، این تابع وقتی مورد استفاده قرار میگیرد که عامل بداند s’ نتیجه است.
► (GOAL – TEST(s
توجه کنید که عامل نمیتواند RESULT(s, a) را تعیین کند مگر اینکه در s باشد و در حال انجام a باشد. این درجه از بی خبری را میتوان در بعضی از کاربردها کاهش داد.
معمولا منظور عامل، رسیدن به حالت هدف، همراه با کمترین هزینه است (منظور دیگر عامل ممکن است اکتشاف یا مرور کل محیط باشد). منظور از هزینه، کل هزینه مسیری است که عامل طی میکند. معمولا متداول است که این هزینه با هزینه مسیری مقایسه می شود که اگر عامل از قبل فضای حالت را میشناخت، طی میکرد (یعنی کوتاهترین مسیر واقعی یا کوتاهترین اکتشاف کامل). در اصطلاح الگوریتم های آنلاین، آن را نسبت رقابتی مینامند. باید ای هزینه به حداقل برسد.
گرچه ممکن است این درخواست منطقی به نظر برسد، به آسانی میتوان دید که در بعضی از موارد، بهترین نسبت رقابتی قابل دستیبابی، نامتناهی است. برای مثال، اگر بعضی از فعالیت ها برگشت ناپذیر باشند، جست وجوی آنلاین ممکن است بطور تصادفی به حالت بن بست برسد که از آن نمیتوان به هیچ حالت هدفی رسید.ادعا میکنیم که هیچ الگوریتمی نمیتواند در تمام فضاهای حالت، وارد بن بست نشود.
بن بست مشکل عمده ای برای اکتشاف روبایت است. برای ادامه کار فرض میکنیم، که فضای حالت، با امنیت قابل اکتشاف است، یعنی از هر حالت قابل دسترس میتوان به حالت هدف رسید . فضاهای حالت همراه با فعالیت های برگشت پذیر، را میتوان بصورت گرافهای بدون جهت دانست که اکتشاف در آنها با امنیت انجام میشود. متداول است که کارایی الگوریتم های جست وجوی آنلاین بر حسب اندازه کل فضای حالت بیان شود، نه برحسب عمق عمیق ترین هدف.
عامل های جست وجوی آنلاین
پس از هر فعالیت، عامل ادراکی را دریافت میکند که به آن میگوید به کدام حالت رسیده است. عامل با استفاده از این اطلاعات میتواند نقشه ی محیط خود را ارتقا دهد. نقشه فعلی به او میگوید که در مرحله بعد باید به کجا برود. یک در میان کردن برنامه ریزی و فعالیت، به معنای این است که الگوریتم های جست وجوی آنلاین کاملا ومتفاوت از الگوریتم های جست وجوی آفلاین هستند. الگوریتم های آنلاین میتوانند پسین ها را فقط برای گره ای کشف کنند که بطور فیزیکی آن را اشغال کرده است. برای جلوگیری از پیمایش کل درخت برای بسط گرره بعدی به نظر میرسد بهتر باشد که گره ها به ترتیب محلی بسط داده شوند.
در شبه کد زیر یک عامل جست وجوی عمقی آنلاین را مشاهده میکنید که از اکتشاف عمقی استفاده میکند. این عامل فقط در فضای حالتی عمل میکند که در آن، هر فعالیت میتواند توسط فعالیت دیگری خنثی شود. هر وقت فعالیتی از حالت فعلی بررسی نشده باشد، عامل آن فعالیت را اجرا میکند. مشکل وقتی پیش می آید که عامل تمام فعالیتهای موجود در یک حالت را اجرا کرده است. در جست وجوی عمقی آفلاین، این حالت از صف حذف میشود، در جست وجوی عمقی آنلاین، عامل باید بطور فیزیکی به عقب برگردد. یعنی به حالتی برگردیم که عامل از آن طریق به حالت فعلی رسیده است. الگوریتم ONLINE - DFS – AGENT فقط در فضاهای حالتی کار میکند که فعالیت ها برگشت پذیر باشند.
شبه کد عامل های جست وجوی آنلاین
functuin ONLINE – DFS – AGENT (s’) returns an action
inputs : s’ , a percept that identifies the current state
persistent : result , a table indexed by state and action, initially empty
untried, a table that lists, for each state, the actions not yet tried
unbacktracked, a table that lists, for each state, the backtracks not yet tried
s, a, the previous state and action, initially null
if GOAL- TEST (s’) then return stop
if s’ is a new state (not in untried) then untried [s’] <-- ACTIONS(s’)
if s is not null then
result[ s, a] <-- s’
add s to the front of unbacktracked [s’]
if untried [s’] is empty then
if unbacktracked [s’] is empty then return stop
else a <-- an action b such that result [s’ , b] = Pop (unbacktracked [s’] )
else a <-- Pop ( untried [s’] )
s <-- s’
return a
سلام و روز بخیرممنون بابت اطلاعات خوبتون.ولی من هیچی نفهمیدم.چون رشتم ریاضی گرایش گراف هست تعریف دقیق الگوریتم های آنلاین و آفلاین رو میخوام ولی در متن بالا تعریف خیلی از عباراتی رو که گفتین نمی دونم میشه لطف کنید یه منبع به من معرفی کنید؟؟؟سپاس