الگوریتم *B
درخت بی‌استار، یک نوع خاص از درخت بی‌پلاس است. درخت‌های بی، بی‌استار و بی‌پلاس در پایگاه داده‌ها و سیستم فایلها کاربرد زیادی دارند. الگوریتم بی استار(به انگلیسی: B*) یک الگوریتم جستجوی ابتدا بهترین در گراف است.
در این روش، کم‌هزینه‌ترین مسیر از یک گره به گرهٔ هدف در گراف محاسبه می‌شود(برای جستجو). این الگوریتم اولین بار در سال ۱۹۷۹ توسط هانس برلینر ارائه شد که با الگوریتم الگوریتم جستجوی آ* مرتبط است.
درخت *B
[ویرایش]درخت‌های بی، بی استار و بی پلاس در پایگاه داده‌ها و سیستم فایلها کاربرد زیادی دارند و در داده ساختارها و پایگاه‌داده‌ها به منظور شاخص بندی استفاده می‌شوند.
در علوم کامپیوتر، یک درخت بی یا بی‌تری (به انگلیسی: B-tree) داده‌ساختاری درختی است که داده‌ها را به صورت مرتب‌شده نگه می‌دارد و جستجو، درج و حذف را در زمان لگاریتمی میسر می‌سازد. بر خلاف درخت‌های جستجوی دودویی متوازن (به انگلیسی: Balanced binary search tree)، این داده‌ساختار برای سیستم‌هایی که بلاک‌های عظیم اطلاعات را خوانده و می‌نویسند بهینه‌سازی شده‌است. این داده‌ساختار معمولاً در پایگاه‌داده‌ها و سیستم پرونده استفاده می‌شود.
در درخت بی داده‌ها می‌توانند در برگ‌ها یا گره‌های میانی ذخیره شوند. اما در درخت بی‌پلاس، تمام داده‌ها در برگ‌ها ذخیره می‌شوند و یک گره توانایی نگهداری چند داده به جای یک داده هم دارد.
درخت *B نوع خاصی از درخت +B است که حداقل دو سوم از ظرفیت هر گره تکمیل باشد.
مقایسه با درخت‌های مشابه
[ویرایش]تفاوت اساسی که بین درخت بی‌استار و بی پلاس وجود دارد این است که در درخت بی‌پلاس، هر گره وقتی دارای یک گرهٔ فرزند خواهد شد که کامل باشد. داده‌ها در یک گرهٔ درخت بی پلاس، نصف ظرفیت آن هستند؛ که این مقدار در درخت بی‌استار، دو سوم ظرفیت آن است. پس درخت بی‌استار در مقایسه با بی‌پلاس متراکم تر است.
تفاوت‌های اصلی یک درخت دودویی و درخت بی استار عبارتند از:
- وجود داده‌های چند گانه در یک گره در درخت به استار به جای یک داده در درخت دودویی
- در درخت بی‌استار هر گره در کنار یک لیست از داده‌های مرتب شده، یک اشاره گر به گرهٔ بعدی هم دارد
- درخت بی‌استار متوازن است.
خلاصه
[ویرایش]این الگوریتم نشان می‌دهد که شروع از ریشه برای جستجو بهتر است. برای این کار، تلاش می‌کند گرهٔ بهتری را پید کند. در این الگوریتم، ترتیب بسط دادن گره‌ها تعیین می‌شود، و هر گرهٔ بسط داده شده دو مقدار به عنوان باند بالا و باند پایین دارد. اگر در طول الگوریتم این دو مقدار به یک عدد مشخص میل کنند و همگرا شوند، الگوریتم به سوی پایان یافتن است. تا وقتی که باندهای یک گره در درخت قابل بسط دادن توسط قوانین مربوطه هستند، الگوریتم به دنبال بهترین گره می‌گردد.
الگوریتم
[ویرایش]علت استفاده از الگوریتم *B
[ویرایش]در سایر الگوریتم‌های جستجو، برای انجام جستجوهای تکراری، یک راه طبیعی برای پایان جستجو وجود ندارد. همچنین با در نظر گرفتن محدودیت‌های مختلف این نکته که کدام عنصر باید ریشه واقع شود، چیز ثابتی نیست. برای غلبه بر این مشکلات از الگوریتم جستجوی بی استار استفاده می‌کنیم.
توضیح الگوریتم
[ویرایش]این الگوریتم، یک الگوریتم جستجوی ابتدا بهترین است؛ بدین معنا که تمام درخت در حافظه نگهداری می‌شود و همین‌طوری پایین می‌رود تا برگ را برای ادامهٔ الگوریتم بیابد.
برای ریشهٔ درخت، دو نوع الگوریتم می‌تواند اجرا شود. همان طور که در شکل1 معلوم است، گرهٔ سمت چپ شانس زیادی برای اینکه گرهٔ برگزیده باشد دارد. باید ذکر شود اگر در این مثال الگوریتم تنها روش خوشبینانه را پیش گیرد، جستجو در همین مرحله تمام می‌شد. پس جستجو یکی از دو راهکار زیر را در پیش می‌گیرد. در درخت بی‌استار هر گره دو ارزش دارد؛ یک ارزش خوشبینانه و دیگری بدبینانه. این کار باعث می‌شود مقادیری که احتمال می‌رود جواب ما باشند در زیر درخت مورد نظر یافت شوند. اکنون به شرح این دو روش می‌پردازیم:
- روش خوش بینانه(به انگلیسی: prove-best): می‌دانیم که هر گره می‌تواند چند مقدار را به‌طور مرتب شده را در خود نگه دارد. در اینجا گره‌ای انتخاب می‌شود که بیشترین مقدار باند بالا را دارد. هدف این است گره‌ای انتخاب شود که کمترین مقدار آن، از بیشترین مقدار سایر گره‌ها بیشتر باشد.
- روش بدبینانه(به انگلیسی: disprove-rest): در این روش گره‌ای انتخاب می‌شود که بیشترین مقدارش از دیگری کمتر است. هدف از این روش این است که در نهایت به گره‌ای برسیم که بیشترین مقدار آن، از کمترین مقدار بهترین گره، کمتر باشد.
در هر دو روش، الگوریتم منجر به ادامهٔ حرکت در درخت می‌شود طوری‌که نشان دهد موفقیت‌آمیز دارد حرکت می‌کند. همان طور که در شکل‌های دو و سه نشان داده شده است، عددهای هر گره، ترتیب حرکت را نشان می‌دهد.مقادیر درون پرانتز باندهای بالا و پایین اند و مقادیر مربوط به فرایند پشتیبانی بالای هر پرانتز نوشته شده‌است. در بدترین حالت، باند بالا یا پایین برابر با گرهٔ پدر دارد.
انتخاب روش
[ویرایش]اجرای روش بدبینانه تا وقتی که باند پایین گرهٔ فرزندی که بالاترین باند بالا را دارد، در میان سایر باندهای پایین، بزرگترین است، بیهوده است.
الگوریتم اصلی کمک بیشتری برای انتخاب روش به ما نمی‌کند.
روش انتخاب برای یک گرهٔ غیر ریشه
[ویرایش]وقتی که یک گرهٔ فرزند انتخاب شده باشد، با اجرای یکی از دو روش ذکر شده در بالا، به یک برگ می‌رسیم. وقتی که به برگ رسیدیم، الگوریتم گره‌های ترتیبی بعدی(به انگلیسی: successor nodes) را تولید می‌کند، سپس با استفاده از تابع سنجش، اختلاف فاصلهٔ هر گره به آن اختصاص داده شود. سپس تمامی این اختلافات ذخیره شده به وسیلهٔ یک فرایند پشتیبانی، مدیریت می‌شوند. وقتی که جابجایی و حرکت روی گره‌ها امکان پذیر است، فرایند پشتیبانی ممکن است نیاز داشته باشد مقدار گره‌هایی که در مسیر انتخابی نیستند تغییر دهد. در این حالت الگوریتم نیاز دارد که از هر فرزند هم به گرهٔ پدر یک اشاره گر وجود داشته باشد تا تغییرات بتواند منتشر شود. باید توجه داشت منتشر شدن وقتی اتفاق می‌افتد که فرایند پشتیبانی مقدار گرهٔ مورد نظر را تغییر نمی‌دهد.
فرایند پشتیبانی
[ویرایش]دقت داشته باشیم که در فرایند پشتیبانی باید باند بالای گرهٔ پدر، به عنوان باند بالای همهٔ باندهای بالای گره‌های فرزند در نظر گرفته می‌شود. باند پایین آن هم باید از باند پایین گره‌های فرزند بیشتر در نظر گرفته شود.
فرایند پشتیبانی وقتی رخ می‌دهد که یکی از سه رخداد زیر پیش آید:
۱-مقادیر خوشبینانه و بدبینانه به هم نزدیک شوند طوری‌که با هم برابر شوند.
۲-شاخه‌های مورد نیاز برای بررسی برای روش خوشبینانه بیشتر است.
۳- روش خوشبینانه و بدبینانه تا جایی پیش رفته باشند که وضعیت زیردرختی که به آن رسیدیم، معلوم شود.
در فرایند پشتیبانی، بهترین مقدار خوشبینانه جایگزین مقدار بدبینانهٔ آن می‌شود و بهترین مقدار بدبینانه، مقدار خوشبینانهٔ آن می‌شود. برای حالت بیشینه، مقادیر خوشبینانه از مقادیر بدبینانه بیشترند. در حالی که در حالت کمینه، مقادیر خوشبینانه کمتر از بدبینانه‌اند. فرایند پشتیبانه به‌طور مداوم تا وقتی که مقادیر جدیدی طبق سه قانون بالا باید پشتیبانی شوند وجود دارد، اجرا می‌شود.
پایان یافتن جستجو
[ویرایش]وقتی باند پایین یکی از فرزندان مستقیم ریشه، بزرگتر یا مساوی باند بالای سایر فرزندان ریشه باشد، الگوریتم *B باعث ایجاد جداسازی می‌شود. درختی که جداسازی در آن صورت می‌گیرد، نشان می‌دهد که فرزند ریشه حداقل به اندازهٔ سایر گره‌ها مناسب است؛ پس این الگوریتم پایان می‌یابد. البته در عمل، جستجوهای پیچیده، ممکن است در یک مدت زمان معقول تمام نشوند پس الگوریتم با یک پایان مصنوعی مانند تایم لیمیت یا مموری لیمیت تمام می‌شود.
مزایای الگوریتم
[ویرایش]دو نکتهٔ زیر می‌تواند الگوریتم *B را به عنوان یک الگوریتم ابندا-بهترین ساده متمایز سازد:
۱-الگوریتم *B، فرایند پشتیبانی را اجرا می‌کند هر گاه به جایی برسد که مقدار آن برای مسئلهٔ ما کافی است. در حالی که سایر الگوریتم‌های ابتدا-بهترین، تا مقدار نهایی را نیابند فرایند پشتیبانی را اجرا نمی‌کنند. یک نکتهٔ ظریف اینجا وجود دارد و آن این است که بی معنی ایت اگر حرکت را از یک گره ادامه بدهیم در حالی که گره موجود حاوی مقداری است که مناسب انتخاب شدن است. در حالی که سایر روش‌های ابتدا-بهترین این را نمی‌فهمند.
۲-الگوریتم می‌تواند یکی از دو روش را فقط وقتی روی ریشه است انتخاب کند. این باعث می‌شود ادامهٔ الگوریتم در مسیری حرکت کند که کم هزینه‌ترین حرکت‌ها مشخص شود.
شبه کد
[ویرایش]
1) DEPTH <- 0; CURNODE <- 0; BESTALT[-2] <- 0
2) if DEPTH <0 then EXIT.
3) if CURNODE has not been expanded yet then generate, name, and evaluate
successors, give each pointer to parent
4) BESTNODE <- name of successor with best OPTIM value;
ALTERN <- name of successor with second best OPTIM value;
MAXOPTIM <- 0PTIM[BESTN0DE];
MAXPESS <- VaJue of the best PESSIM value of all successors;
5) Back up MAXOPTIM and MAXPESS and far as necessary. If a change is made to
descendants of root, then (DEPTH <- 0; CURNODE <- 0; go to 4);
6) if MAXOPTIM = MAXPESS then go to 16;
7) BESTALT[DEPTH] <- BESTALT[DEPTH-2]
8) if DEPTH = 0 then decide STRATEGY,
if STRATEGY = DISPROVEREST then
(ASPIR <- MAXPESS ; BESTALT[0] <- MAXPESS ; BESTALT[-1] <- OPTIMf ALTERN]);
if STRATEGY = PROVEBEST then
(ASPIR <- OPTIM[ALTERN]j BESTALT[-1]<- MAXPESS; BESTALT[0] <- 0PTIM[ALTER
9) if MAXPESS> BESTALT[DEPTH-1 ] then goto 16;
10) if STRATEGY = PROVEBEST then
if MAXPESS> ASPIR then goto 16;
11) if MAXOPTIM <BESTALT[DEPTH] then goto 16;
12) if STRATEGY = DISPROVEREST then
if MAXOPTIM <ASPIR then goto 16;
13) if DEPTH != 0 then
if 0PTIM[ALTERN]> BESTALT[DEPTHJ then BESTALT[DEPTH] <- 0PTIM[ALTERN];
14) if (DEPTH = 0) and (STRATEGY = DISPROVEREST) then CURNODE <- ALTERN
else CURNODE <- BESTNODE;
15) DEPTH <-DEPTH+1;
go to 3.
16) DEPTH <-DEPTH-1;
if DEPTH <0 then ANSWER <- BESTNODE
else (CURNODE PARENT[CURNODE]; go to 2);
کاربرد الگوریتم
[ویرایش]اندرو پالای(به انگلیسی: Andrew Palay) توانست از این الگوریتم در شطرنج استفاده کند. نقطهٔ پایان ارزیابی، به وسیلهٔ جستجوهای پوچ شناخته می‌شود. گزارشی در دست نیست که این الگوریتم چگونه در برابر هرس آلفا بتا که روی سخت افزارهای مشابه کار می‌کند، عملکرد بهتری دارد.
همچنین الگوریتم *B استفاده می‌شود تا روش بهینه در بازی جمع (به انگلیسی: sum game) از یک مجموعه بازی‌های ترکیبی را محاسبه کند.
جستارهای وابسته
[ویرایش]منابع
[ویرایش]- Berliner, The best search algorithm: a best first proof procedure,Carnegie Mellon University
- Russell, S. J.; Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall. p. 188.