الگوریتم جستجوی پرتو محلی

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

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

الگوریتم بیم برای اینکه در حافظه صرفه‌جویی کند یک تابع 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
    }
  }
}

منابع

• الگوریتم جستجوی بیم (انگلیسی)
• [۱]

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

• [۲]