الگوریتم جستجوی بیم

در علوم کامپیوتر یکی از الگوریتم های فراابتکاری، الگوریتم جستجوی بیم است که گراف را با استفاده از راس‌هایی که در یک مجموعه خاص احتمال وجود بیشتری دارند می‌پیماید. در واقع این جستجو حالت بهینه‌ی الگوریتم جستجوی اول سطح است که در آن حافظه مورد نیاز را کاهش می‌دهد. الگوریتم جستجوی اول سطح پیدا کردن کمترین فاصله بین راس شروع و پایان را در گراف بی‌وزن تضمین می‌کند ولی برای جستجو در فضاهای بزرگ این کار تقریبا غیر عملی است چرا که حافظه‌ی بسیار زیادی مصرف می‌کند ممکن است قبل از این‌که به جواب برسد حافظه پر بشود.

چگونه کار می‌کند؟

الگوریتم بیم برای اینکه در حافظه صرفه‌جویی کند یک تابع h برای پیش‌‌بینی هزینه‌ی رسیدن به راس موردنظر از راس داده‌شده.همچنین از یک پارامتر به نام ‌‌‌‌B(عرض بیم) استفاده می‌کند که نشان‌دهنده‌ی تعداد راس‌هایی است که در هر مرحله از الگوریتم جستجوی اول سطح ذخیره شده‌است. بنابراین زمانی که الگوریتم جستجوی اول سطح همه‌ی راس‌های مرزی ( راس‌هایی که با نزدیک‌ترین راس ارتباط دارند)را ذخیره می‌کند الگوریتم بیم فقط راس‌های ‌‌‌‌B با بهترین مقدار در هر مرحله از جستجو را ذخیره می‌کند. ایده اصلی این است که تابع h به الگوریتم اجازه می‌دهد که راس‌هایی انتخاب شوند که مسیر را به سمت راس مقصد راهنمایی کنند و پارامتر B باعث می‌شود که الگوریتم فقط این راس‌های مهم را ذخیره کند و از پر شدن حافظه قبل از رسیدن به هدف جلوگیری می‌کند.برخلاف الگوریتم جستجوی اول سطح که از یک لیست(open list)استفاده می‌‌کند این الگوریتم راس‌هایی را که در حلقه‌ی بعد الگوریتم بسط داده می‌شود رادر(BEAM)ذخیره می‌کند؛ همچنین از یک جدول‌هش برای ذخیره‌ی راس‌هایی که دیده شده‌اند استفاده می‌کند شبیه(close list)درالگوریتم جستجوی اول سطح. الگوریتم بیم در ابتدا راس شروع را به BEAM وجدول‌هش اضافه می‌کند سپس در هر مرحله از حلقه‌ی اصلی از الگوریتم، راس‌های همسایه‌ باراس‌های BEAM را به یک مجموعه‌ که شامل راس‌های جانشین(successor)است اضافه می‌کند و سپس راس‌های B با بهترین مقدار از مجموعه‌ی جانشین را به BEAM و جدول‌هش اضافه می‌کند. راس‌هایی که در حال حاضر در جدول‌هش قرار دارند به BEAM اضافه نمی‌شوند چرا که مسیر کوتاهتر برای آن راس پیدا شده.این فرآیند ادامه دارد تا زمانی که راس مقصد پیدا شود، جدول‌هش پر شود، یا BEAM بعد از حلقه‌ی اصلی خالی شود. در ادامه شبه کد الگوریتم آورده شده.

پیاده‌سازی الگوریتم

/* initialization */
 
g = 0;
 
hash_table = { start };
 
BEAM = { start };
 
/* main loop */
 
while(BEAM ≠ ∅){                             // loop until the BEAM contains no nodes
 
  SET = ∅;                                   // the empty set
 
  /* generate the SET nodes */
  for(each state in BEAM){
    for(each successor of state){
      if(successor == goal) return g + 1;
      SET = SET ∪ { successor };             // add successor to SET
    }
  }
 
  BEAM = ∅;                                  // the empty set
  g = g + 1;
 
  /* fill the BEAM for the next loop */
  while((SET ≠ ∅) AND (B > |BEAM|)){         // set is not empty and the number of nodes in BEAM is less than B
    state = successor in SET with smallest h value;
    SET = SET \ { state };                   // remove state from SET
    if(state ∉ hash_table){                  // state is not in the hash_table
      if(hash_table is full) return ∞;
      hash_table = hash_table ∪ { state };   // add state to hash_table
      BEAM = BEAM ∪ { state };               // add state to BEAM
    }
  }
}

منابع

• الگوریتم‌ جستجوی بیم (انگلیسی)

• [۱]

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

• [۲]