درخت جست وجوی AND - OR
درخت جست وجوی AND - OR
در جست وجو با فعالیتهای غیر قطعی، این که "چگونه میتوان جوابهای احتمالی مربوط به مسئله های غیر واقعی را به دست آورد" مسئله مهمی است. در اینجا درختها کاراکتر متفاوتی دارند. در محیط قطعی، تنها انشعاب، ناشی از انتخاب های خود عامل در هر حالت است. این گره ها را گره های OR می نامیم. در محیط غیرقطعی، انشعاب ناشی از انتخابی است که محیط از نتیجه ی هر فعالیت انجام میدهد. این گره ها را گره های AND می نامیم.
جواب مسئله جست وجوی AND – OR زیر درختی است که :
(1) در هر برگ دارای یک گره هدف است.
(2) در هر گره OR خود یک فعالیت را مشخص میکند.
(3) هر انشعاب حاصل را در هر گره AND خود قرار میدهد.
به آسانی میتوان "عامل اصلی حل مسئله " را تغییر داد تا نوع جوابهای احتمالی را اجرا کند. یک روش دیگر، استفاده از برنامه ریزی متفاوت دیگر برای عامل است، که در آن عامل قبل از یافتن یک برنامه ریزی تضمینی عمل کند، و بعضی از احتمالات را در صورتی اداره کند که در اثنای اجرا به وقوع بپیوندند. انجام جست وجو و اجرا در بین یکدیگر، برای مسئله های اکتشافی و بازی کامپیوتری نیز مفید است.
در ادامه یک الگوریتم عمقی بازگشتی را برای جست وجوی گراف AND – OR نشان خواهیم داد. یک جنبه مهم این الگوریتم روش اداره کردن چرخه هاست، که غالبا در مسئله های غیرقطعی به وجود می آید (مثلا، اگر فعالیتی گاهی هیچ اثری نداشته باشد، یا اثر ناخواسته بتواند درست شود). اگر حالت فعلی برابر با یک حالت در مسیری از ریشه باشد، آنگاه با خطا خاتمه پیدا میکند. معنایش این نیست که جوابی از حالت فعلی وجود ندارد، بلکه به معنای این است که اگر یک جواب غیر چرخه ای وجود داشته باشد، باید از نمونه قبلی حالت فعلی قابل دسترس باشد و در نتیجه نمونه ی جدید حالت فعلی میتواند حذف شود. با این بررسی مطمئن میشویم که الگوریتم در هر فضای حالت متناهی خاتمه می یابد، زیرا هر مسیر باید به یک هدف، به یک بن بست، یا یک حالت تکراری برسد. توجه کنید که این الگوریتم بررسی نمیکند که آیا حالت فعلی، تکرار یک حالت در مسیر دیگری از ریشه هست یا خیر. این بررسی برای کارایی مهم است.
گراف های AND – OR نیز میتوانند به روش های عرضی یا "اول - بهترین" بررسی شوند. مفهوم تابع ابتکاری باید اصلاح شوند تا هزینه جواب احتمالی را به جای یک دنباله برآورد کند، اما مفهوم "قابل قبول بودن" برقرار نیست و شبیه الگوریتم A* برای یافتن جوابها بهینه است.
شبه کد الگوریتم جست وجوی AND -OR
function AND – OR – GRAPH – SEARCH (problem) returns a conditional plan , or failure
OR – SEARCH (problem.INITIAL- STATE, problem, [])
function OR – SEARCH (state, problem, path) returns a conditional plan , or failure
if problem.GOAL- TEST(state) then return the empty plan
if state is on path then return failure
for each action in problem. ACTIONS(state) do
plan <-- AND – SEARCH(RESULTS(state, action), problem, [state | path])
if plan != failure then return [action | plan]
return failure
function AND- SEARCH (state, problem, path) returns a conditional plan, or failure
for each si in state do
plani <-- OR – SEARCH (si, problem, path)
if plani = failure then return failure
return [if s1 then plan1 else if s2 then plan2 else … if sn-1 then plann-1 else plann]
.gif)
