پرش به محتوا

الگوریتم sss*

از ویکی‌پدیا، دانشنامهٔ آزاد

الگوریتم *sss به شرح زیر است.

مقدمه

[ویرایش]

مبنا *sss مفهوم درخت راه حل است. یک درخت راه حل می‌تواند از هر درخت بازی که به وسیلهٔ هرس تعدادی راس در هر یک از راس بیشینه به یک، حالت بگیرد. چنین درختی نشان دهنده یک استراتژی کامل برای بیشینه است که آن مشخص می‌کند دقیقاً یک حالت بیشینه برای هر حرکت توالی ممکن، ممکن است توسط حریف ساخته شود. با توجه به یک درخت بازی، جستجو *SSS از طریق فضای جزئی درختان راه حل، به تدریج تجزیه و تحلیل زیر درختان بزرگتر و بزرگتر، سرانجام یک درخت راه حل تنها با همان ریشه و ارزش مینیماکس به عنوان درخت بازی اصلی تولید می‌شود. *SSS هرگز به بررسی یک گره که هرس آلفا بتا باید آن را هرس کند، و ممکن است شعب‌هایی که آلفا بتا نباید هرس کند را هرس می‌کند. استکمن بر این باور است که *SSS ممکن است یک الگوریتم کلی بهتر از آلفا بتا باشد اما، استیو روزن و جوده آ پیرل نشان داده‌اند که صرفه جویی در تعداد موقعیت‌های که *SSS ارزیابی می‌کند نسبت به آلفا / بتا محدود است و به‌طور کلی به اندازه کافی نیست برای جبران افزایش در منابع دیگر (مانند ذخیره و مرتب کردن آرایه‌ای از راس‌ها که ساخته شده‌اند به وسیلهٔ الگوریتم بهترین-اولین).

الگوریتم

[ویرایش]

در اینجا یک صف اولویت دار بنام OPEN است که حالت‌های یا راس‌ها را ذخیره می‌کند، جایی که J مشخص‌کننده راس،حالتی که راس J (راس زنده است، به این معنا که هنوز حل نشده‌است و S راس ای است که حل شده است)،ارزش حل شدن یک راس است. آیتم در OPEN نزولی مرتب شده‌اند به وسیلهٔ ارزش H. اگر بیشتر از یک راس دارای ارزش H باشند، a چپترین راس در این درخت انتخاب می‌شود.

کد سودو

[ویرایش]
 }(OPEN := { (e,L,inf
 while (true)   // repeat until stopped
 pop an element p=(J,s,h) from the head of the OPEN queue
 if J == e and s == S
 STOP the algorithm and return h as a result
 else
 apply Gamma operator for p

operator for is defined in the following way: 

 if s == L
 if J is a terminal node
 (1.) add (J,S,min(h,value(J))) to OPEN
 else if J is a MIN node
 (2.) add (J.1,L,h) to OPEN
 else
 (3.) for j=1..number_of_children(J) add (J.j,L,h) to OPEN
 else
 if J is a MIN node
 (4.) add (parent(J),S,h) to OPEN
 remove from OPEN all the states that are associated with the children of parent(J)
 else if is_last_child(J)   // if J is the last child of parent(J)
 (5.) add (parent(J),S,h) to OPEN
 else
 (6.) add (parent(J). (k+1),L,h) to OPEN   // add state associated with the next child of parent(J) to OPEN

کد به زبان c

[ویرایش]
}(int SSS* (node n; int bound
   ;(push (n, LIVE, bound
   }(while ( true
      ;(pop (node
      }(switch ( node.status
      :case LIVE
          (if (node == LEAF
             ;((insert (node, SOLVED, min(eval(node),h
          (if (node == MIN_NODE
             ;(push (node.1, LIVE, h
          (if (node == MAX_NODE
             (--for (j=w; j; j
                ;(push (node.j, LIVE, h
          ;break
      :case SOLVED
          (if (node == ROOT_NODE
             ;(return (h
          }(if (node == MIN_NODE
              ;((purge (parent(node
              ;(push (parent(node), SOLVED, h
          {
          }(if (node == MAX_NODE
             (if (node has an unexamined brother
                ;(push (brother(node), LIVE, h
             else
                ;(push (parent(node), SOLVED, h
          {
          ;break
      {
   {
{

منابع

[ویرایش]

پیوند به بیرون

[ویرایش]
برگرفته از «https://fa.wikipedia.org/w/index.php?title=الگوریتم_sss*&oldid=30978235»