بحث شعاعي

في علوم الحاسوب ، يُعدّ بحث الشعاع خوارزمية بحث استدلالية تستكشف الرسم البياني بتوسيع نطاق العقدة الأكثر جدوى ضمن مجموعة محدودة. يُعتبر بحث الشعاع تعديلًا لبحث الأفضل أولًا، مما يقلل من متطلبات الذاكرة. بحث الأفضل أولًا هو بحث في الرسم البياني يُرتب جميع الحلول الجزئية (الحالات) وفقًا لقاعدة استدلالية معينة. أما في بحث الشعاع، فيتم الاحتفاظ بعدد محدد مسبقًا من أفضل الحلول الجزئية كمرشحين. ^{[ 1 ]} ولذلك، فهو خوارزمية جشعة .

تستخدم خوارزمية البحث الشعاعي البحث بالعرض أولاً لبناء شجرة البحث الخاصة بها . في كل مستوى من مستويات الشجرة، تُولّد جميع الحالات اللاحقة للحالات الموجودة في المستوى الحالي، مع ترتيبها تصاعديًا حسب التكلفة الاستدلالية. ^{[ 2 ]} ومع ذلك، فهي تخزن عددًا محددًا مسبقًا فقط.${\displaystyle \beta }$يُحدد عرض الحزمة أفضل الحالات في كل مستوى. تُوسّع هذه الحالات فقط في المرحلة التالية. كلما زاد عرض الحزمة، قلّ عدد الحالات التي تُحذف. مع عرض حزمة لانهائي، لا تُحذف أي حالات، ويكون بحث الحزمة مطابقًا لبحث الأفضل أولًا . ^{[ 3 ]} في المقابل، يتوافق عرض حزمة يساوي 1 مع خوارزمية تسلق التلال . ^{[ 3 ]} يُحدد عرض الحزمة الذاكرة المطلوبة لإجراء البحث. بما أن حالة الهدف قد تُحذف، فإن بحث الحزمة يُضحي بالشمولية (ضمان انتهاء الخوارزمية بحل، إن وُجد). بحث الحزمة ليس مثاليًا (أي لا يوجد ضمان بأنه سيجد أفضل حل).

يُستخدم البحث الشعاعي غالبًا للحفاظ على سهولة المعالجة في الأنظمة الكبيرة ذات الذاكرة غير الكافية لتخزين شجرة البحث بأكملها. ^{[ 4 ]} على سبيل المثال، استُخدم في العديد من أنظمة الترجمة الآلية . ^{[ 5 ]} (تعتمد أحدث التقنيات حاليًا بشكل أساسي على أساليب الترجمة الآلية العصبية ، لا سيما نماذج اللغة الكبيرة ). لاختيار أفضل ترجمة، تتم معالجة كل جزء، فتظهر طرق عديدة لترجمة الكلمات. تُحفظ أفضل الترجمات وفقًا لبنية جملها، وتُستبعد البقية. ثم يُقيّم المترجم الترجمات وفقًا لمعيار مُحدد، ويختار الترجمة التي تُحقق الأهداف على أفضل وجه.

كان نظام هاربي للتعرف على الكلام (الذي طُرح في أطروحة عام 1976 ^{[ 6 ]} ) أول استخدام لما سيُعرف لاحقًا باسم البحث الشعاعي. ^{[ 7 ]} في حين أن الإجراء كان يُشار إليه في الأصل باسم "نموذج البحث الموضعي"، إلا أن مصطلح "البحث الشعاعي" كان مستخدمًا بالفعل بحلول عام 1977. ^{[ 8 ]}

تم تطوير خوارزمية البحث الشعاعي بدمجها مع خوارزمية البحث العميق أولاً ، مما أدى إلى ظهور خوارزمية البحث الشعاعي المكدس ^{[ 9 ]} وخوارزمية البحث الشعاعي العميق أولاً ^{[ 4 ]،} ومع خوارزمية البحث بالتباين المحدود ^{[ 4 ]} ، مما أدى إلى ظهور خوارزمية البحث الشعاعي باستخدام التراجع بالتباين المحدود ^{[ 4 ]} (BULB). تُعدّ خوارزميات البحث الناتجة خوارزميات فعّالة في أي وقت، حيث تجد حلولاً جيدة ولكنها غالباً ما تكون دون المستوى الأمثل بسرعة، مثل خوارزمية البحث الشعاعي، ثم تتراجع وتستمر في البحث عن حلول محسّنة حتى الوصول إلى الحل الأمثل.

في سياق البحث المحلي ، نطلق على البحث الشعاعي المحلي اسم خوارزمية محددة تبدأ في اختيار${\displaystyle \beta }$يتم توليد الحالات عشوائيًا، ثم يتم دائمًا مراعاة كل مستوى من مستويات شجرة البحث.${\displaystyle \beta }$إنشاء دول جديدة من بين جميع الدول المحتملة التي ستخلف الدول الحالية، حتى تصل إلى هدف محدد. ^{[ 10 ] [ 11 ]}

بما أن البحث عن الحزمة المحلية غالباً ما ينتهي عند القيم القصوى المحلية، فإن الحل الشائع هو اختيار التالي${\displaystyle \beta }$يتم تحديد الحالات بطريقة عشوائية، باحتمالية تعتمد على التقييم الاستدلالي للحالات. يُطلق على هذا النوع من البحث اسم البحث الشعاعي العشوائي . ^{[ 12 ]}

ومن المتغيرات الأخرى البحث المرن عن الشعاع والبحث عن شعاع الاستعادة . ^{[ 11 ]}