البحث الشامل

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
الموسوعة الحرة

في علوم الحاسوب ، يعد البحث بالقوة الغاشمة أو البحث الشامل ، والمعروف أيضًا باسم التوليد والاختبار ، أسلوبًا عامًا جدًا لحل المشكلات ونموذجًا خوارزميًا يتكون من التحقق بشكل منهجي من جميع المرشحين المحتملين لمعرفة ما إذا كان كل مرشح يفي ببيان المشكلة أم لا.

تعتمد خوارزمية البحث الشامل لإيجاد قواسم العدد الطبيعي n على تعداد جميع الأعداد الصحيحة من 1 إلى n، والتحقق مما إذا كان كل منها يقسم n بدون باقٍ. أما في حالة لغز الملكات الثماني ، فتعتمد خوارزمية البحث الشامل على فحص جميع الترتيبات الممكنة لثماني قطع على رقعة الشطرنج المكونة من 64 مربعًا، وفي كل ترتيب، يتم التحقق مما إذا كانت كل قطعة (ملكة) قادرة على مهاجمة أي قطعة أخرى. [ 1 ]

عند الشك، استخدم القوة الغاشمة.

— كين تومسون ، منسوب

على الرغم من سهولة تطبيق البحث الشامل، وقدرته على إيجاد حلٍّ إن وُجد، إلا أن تكاليف تنفيذه تتناسب طرديًا مع عدد الحلول المحتملة ، والذي يميل في كثير من المسائل العملية إلى النمو بسرعة كبيرة مع ازدياد حجم المسألة ( انظر: الانفجار التوافقي ). [ 2 ] لذا، يُستخدم البحث الشامل عادةً عندما يكون حجم المسألة محدودًا، أو عندما تتوفر طرق استدلالية خاصة بالمسألة يمكن استخدامها لتقليص مجموعة الحلول المحتملة إلى حجم يمكن التحكم فيه. كما تُستخدم هذه الطريقة أيضًا عندما تكون سهولة التنفيذ أهم من سرعة المعالجة. 

ينطبق هذا، على سبيل المثال، في التطبيقات الحساسة حيث قد تترتب على أي أخطاء في الخوارزمية عواقب وخيمة، أو عند استخدام الحاسوب لإثبات نظرية رياضية . يُعد البحث الشامل مفيدًا أيضًا كطريقة أساسية عند تقييم الخوارزميات الأخرى أو الطرق الاستدلالية . في الواقع، يمكن اعتبار البحث الشامل أبسط الطرق الاستدلالية. يجب عدم الخلط بين البحث الشامل والتراجع ، حيث يمكن استبعاد مجموعات كبيرة من الحلول دون حصرها صراحةً (كما في حل الحاسوب المذكور في كتاب "مسألة الملكات الثماني" أعلاه). تُسمى طريقة البحث الشامل للعثور على عنصر في جدول - أي فحص جميع مدخلات الجدول بالتسلسل - بالبحث الخطي .  

الخوارزمية الأساسية

لتطبيق البحث الشامل على فئة محددة من المسائل، يجب تنفيذ أربع إجراءات : first و next و valid و output . تأخذ هذه الإجراءات كمعامل البيانات P الخاصة بالمسألة المراد حلها، وتقوم بما يلي:

  1. أولاً ( P ): قم بتوليد حل مرشح أول لـ P.
  2. next ( P , c ): توليد المرشح التالي لـ P بعد المرشح الحالي c .
  3. valid ( P , c ): تحقق مما إذا كان المرشح c حلاً لـ P .
  4. output ( P , c ): استخدم الحل c لـ P حسب ما يناسب التطبيق.

يجب أن يحدد الإجراء التالي أيضًا متى لا يتبقى أي مرشحين للحالة P بعد المرشح الحالي c . إحدى الطرق الملائمة للقيام بذلك هي إرجاع "مرشح فارغ"، وهي قيمة بيانات تقليدية Λ تختلف عن أي مرشح حقيقي. وبالمثل، يجب أن يُرجع الإجراء الأول Λ إذا لم يكن هناك أي مرشحين على الإطلاق للحالة P. ثم تُعبّر الخوارزمية عن طريقة البحث الشامل.

c ← first ( P ) while c ≠ Λ do if valid ( P , c ) then output ( P , c ) c ← next ( P , c ) end while

على سبيل المثال، عند البحث عن قواسم العدد الصحيح n ، فإن بيانات الحالة P هي العدد n . يجب أن تُرجع الدالة first ( n ) العدد الصحيح 1 إذا كان n ≥ 1، أو Λ خلاف ذلك؛ ويجب أن تُرجع الدالة next ( n , c ) قيمة c + 1 إذا كان c < n ، وΛ خلاف ذلك؛ ويجب أن تُرجع الدالة valid ( n , c ) القيمة true إذا وفقط إذا كان c قاسمًا للعدد n . (في الواقع، إذا اخترنا Λ لتكون n + 1، فإن الاختبارين n ≥ 1 و c < n يصبحان غير ضروريين). ستُخرج خوارزمية البحث الشامل المذكورة أعلاه كل مرشح يُمثل حلاً للحالة P المُعطاة . يُمكن تعديل الخوارزمية بسهولة للتوقف بعد إيجاد الحل الأول، أو عدد مُحدد من الحلول؛ أو بعد اختبار عدد مُحدد من المرشحين، أو بعد استهلاك قدر مُحدد من وقت وحدة المعالجة المركزية .

الانفجار التوافقي

تتمثل العيوب الرئيسية لطريقة البحث الشامل في أن عدد الاحتمالات الطبيعية يكون هائلاً للغاية في العديد من المشكلات الواقعية. على سبيل المثال، إذا بحثنا عن قواسم عدد ما كما هو موضح أعلاه، فسيكون عدد الاحتمالات المختبرة هو العدد المعطى n . فإذا كان n يحتوي على ستة عشر رقمًا عشريًا، على سبيل المثال، فسيتطلب البحث تنفيذ ما لا يقل عن 10^ 15 تعليمة حاسوبية، وهو ما سيستغرق عدة أيام على جهاز كمبيوتر عادي . أما إذا كان n عددًا طبيعيًا عشوائيًا مكونًا من 64 بت ، ويحتوي على حوالي 19 رقمًا عشريًا في المتوسط، فسيستغرق البحث حوالي 10 سنوات. ويحدث هذا النمو السريع في عدد الاحتمالات، مع ازدياد حجم البيانات، في جميع أنواع المشكلات. فعلى سبيل المثال، إذا كنا نبحث عن إعادة ترتيب معينة لعشرة أحرف، فسيكون لدينا 10! = 3,628,800 احتمالًا للنظر فيها، وهو عدد يمكن لجهاز كمبيوتر عادي توليده واختباره في أقل من ثانية واحدة. مع ذلك، فإن إضافة حرف واحد فقط - وهو ما يمثل زيادة بنسبة 10% في حجم البيانات - ستضاعف عدد المرشحين 11 مرة، أي بزيادة قدرها 1000%. بالنسبة لعشرين حرفًا، يصبح عدد المرشحين 20!، أي ما يقارب 2.4 × 10^ 18 أو 2.4 كوينتيليون ؛ وسيستغرق البحث حوالي عشر سنوات. تُعرف هذه الظاهرة غير المرغوب فيها باسم الانفجار التوافقي ، أو لعنة الأبعاد .  

من الأمثلة على الحالات التي يؤدي فيها التعقيد التوافقي إلى حدّ قابلية الحل، حلّ مسائل الشطرنج . فالشطرنج ليست لعبة محلولة . في عام ٢٠٠٥، تم حلّ جميع نهايات مباريات الشطرنج بست قطع أو أقل، مما أظهر نتيجة كل وضعية في حال لعبها بشكل مثالي. استغرق الأمر عشر سنوات أخرى لإكمال قاعدة البيانات بإضافة قطعة شطرنج واحدة، وبذلك اكتملت قاعدة بيانات من سبع قطع. تُعتبر إضافة قطعة أخرى إلى نهاية لعبة شطرنج (وبالتالي إنشاء قاعدة بيانات من ثماني قطع) غير قابلة للحل نظرًا للتعقيد التوافقي الإضافي. [ ٣ ] [ ٤ ] [ ٥ ]

تسريع عمليات البحث الشامل

إحدى طرق تسريع خوارزمية البحث الشامل هي تقليل مساحة البحث، أي مجموعة الحلول المرشحة، باستخدام أساليب استدلالية خاصة بنوع المسألة. على سبيل المثال، في مسألة الملكات الثماني، يكمن التحدي في وضع ثماني ملكات على رقعة شطرنج قياسية بحيث لا تهاجم أي ملكة الأخرى. بما أنه يمكن وضع كل ملكة في أي من المربعات الـ 64، فمن حيث المبدأ، هناك 64 ÷ 8 = 281,474,976,710,656 احتمالًا للنظر فيها. مع ذلك، ولأن الملكات متشابهة، ولا يمكن وضع ملكتين في المربع نفسه، فإن الحلول المرشحة هي جميع الطرق الممكنة لاختيار 8 مربعات من بين جميع المربعات الـ 64؛ مما يعني أن 64 ÷ 8 = 64!/(56!*8!) = 4,426,165,368 حلًا مرشحًا - أي ما يقارب 1/60,000 من التقدير السابق. علاوة على ذلك، لا يمكن لأي ترتيب يضم ملكتين في نفس الصف أو العمود أن يكون حلاً. لذا، يمكننا حصر مجموعة المرشحين في هذه الترتيبات فقط. 

كما يوضح هذا المثال، فإن القليل من التحليل غالباً ما يؤدي إلى انخفاضات كبيرة في عدد الحلول المرشحة، وقد يحول مشكلة مستعصية إلى مشكلة تافهة.

في بعض الحالات، قد يُختزل التحليل المرشحين إلى مجموعة الحلول الصحيحة؛ أي أنه قد يُنتج خوارزمية تُحصي جميع الحلول المطلوبة مباشرةً (أو تجد حلاً واحداً، حسب الاقتضاء)، دون إضاعة الوقت في الاختبارات وتوليد مرشحين غير صالحين. على سبيل المثال، بالنسبة لمسألة "إيجاد جميع الأعداد الصحيحة بين 1 و1,000,000 التي تقبل القسمة على 417"، فإن الحل البسيط القائم على التجربة والخطأ سيُولد جميع الأعداد الصحيحة في النطاق، ويختبر قابلية كل منها للقسمة. مع ذلك، يُمكن حل هذه المسألة بكفاءة أكبر بكثير بالبدء من 417 وإضافة 417 بشكل متكرر حتى يتجاوز العدد 1,000,000 ، وهو ما يتطلب 2398 خطوة فقط (1,000,000 ÷ 417)، ودون الحاجة إلى أي اختبارات. 

إعادة ترتيب مساحة البحث

في التطبيقات التي تتطلب حلاً واحداً فقط، بدلاً من جميع الحلول، يعتمد وقت التشغيل المتوقع للبحث الشامل غالباً على ترتيب اختبار الحلول المرشحة. وكقاعدة عامة، ينبغي اختبار الحلول المرشحة الأكثر جدوى أولاً. على سبيل المثال، عند البحث عن قاسم مناسب لعدد عشوائي n ، من الأفضل ترقيم القواسم المرشحة بترتيب تصاعدي، من 2 إلى n - 1 ، بدلاً من العكس ، لأن احتمال أن يكون n قابلاً للقسمة على c هو 1/ c . علاوة على ذلك، غالباً ما يتأثر احتمال صحة الحل المرشح بالمحاولات الفاشلة السابقة. على سبيل المثال، لنفترض مشكلة إيجاد بت 1 في سلسلة P مكونة من 1000 بت . في هذه الحالة، تكون الحلول المرشحة هي المؤشرات من 1 إلى 1000، ويكون الحل المرشح c صالحاً إذا كان P [ c ] = 1. الآن، لنفترض أن البت الأول من P له احتمال متساوٍ أن يكون 0 أو 1 ، ولكن كل بت بعد ذلك يساوي البت السابق باحتمال 90%. إذا تم ترقيم المرشحين تصاعديًا من 1 إلى 1000، فإن عدد المرشحين الذين يتم فحصهم قبل الوصول إلى الحل الناجح ( t) سيكون حوالي 6 في المتوسط. من ناحية أخرى، إذا تم ترقيم المرشحين بالترتيب 1، 11، 21، 31... 991، 2، 12، 22، 32 وهكذا، فإن القيمة المتوقعة لـ t ستكون أكثر بقليل من 2. بشكل عام، يجب ترقيم فضاء البحث بطريقة تجعل المرشح التالي هو الأرجح أن يكون صالحًا، بافتراض أن المحاولات السابقة لم تكن كذلك . لذا، إذا كان من المرجح أن تكون الحلول الصالحة "متجمعة" بمعنى ما، فيجب أن يكون كل مرشح جديد بعيدًا قدر الإمكان عن المرشحين السابقين، بنفس المعنى. وينطبق العكس بالطبع، إذا كان من المرجح أن تكون الحلول موزعة بشكل أكثر انتظامًا مما هو متوقع بالصدفة. 

توجد العديد من طرق البحث الأخرى، أو ما يُعرف بالأساليب فوق الحدسية، المصممة للاستفادة من أنواع مختلفة من المعرفة الجزئية التي قد يمتلكها الباحث حول الحل. كما يمكن استخدام الأساليب الحدسية لاستبعاد أجزاء من البحث في وقت مبكر. ومن الأمثلة على ذلك مبدأ المينيماكس للبحث في أشجار الألعاب، الذي يُزيل العديد من الأشجار الفرعية في مرحلة مبكرة من البحث. في بعض المجالات، مثل تحليل اللغة، يمكن لتقنيات مثل تحليل المخططات استغلال القيود في المسألة لتقليل تعقيد المسألة الأسي إلى تعقيد متعدد الحدود. في كثير من الحالات، كما هو الحال في مسائل إرضاء القيود ، يمكن تقليص مساحة البحث بشكل كبير باستخدام نشر القيود ، الذي يُنفذ بكفاءة في لغات برمجة القيود . كما يمكن تقليص مساحة البحث للمسائل باستبدال المسألة الكاملة بنسخة مبسطة منها. على سبيل المثال، في لعبة الشطرنج الحاسوبية ، بدلاً من حساب شجرة minimax الكاملة لجميع الحركات الممكنة لبقية اللعبة، يتم حساب شجرة أكثر محدودية من احتمالات minimax، حيث يتم تقليم الشجرة عند عدد معين من الحركات، ويتم تقريب الجزء المتبقي من الشجرة بواسطة دالة تقييم ثابتة .

في علم التشفير

في علم التشفير ، يتضمن هجوم القوة الغاشمة فحص جميع المفاتيح الممكنة بشكل منهجي حتى يتم العثور على المفتاح الصحيح. [ 6 ] من الناحية النظرية، يمكن استخدام هذه الاستراتيجية ضد أي بيانات مشفرة [ 7 ] (باستثناء مفتاح التشفير لمرة واحدة ) من قبل مهاجم غير قادر على استغلال أي ثغرة في نظام التشفير من شأنها أن تسهل مهمته.

يُحدد طول المفتاح المستخدم في التشفير مدى جدوى تنفيذ هجوم القوة الغاشمة، حيث يصعب اختراق المفاتيح الأطول بشكل كبير مقارنةً بالمفاتيح الأقصر. ويمكن الحد من فعالية هجمات القوة الغاشمة عن طريق إخفاء البيانات المراد تشفيرها، مما يُصعّب على المهاجم اكتشاف اختراقه للرمز. ومن مقاييس قوة نظام التشفير المدة الزمنية التي قد يستغرقها المهاجم نظريًا لتنفيذ هجوم قوة غاشمة ناجح ضده.

مراجع

  1. ↑ "شرح خوارزميات القوة الغاشمة" . freeCodeCamp.org . 2020-01-06 . تم الاطلاع عليه بتاريخ 2021-04-11 .
  2. ↑ "تعقيد البحث بالقوة الغاشمة" . كورسيرا . تم الاطلاع عليه بتاريخ 14 يونيو 2018 .
  3. ↑ "هل يوجد جدول لعب مجاني متاح عبر الإنترنت لسبع قطع للعبة Endgame؟" . Stack Exchange .
  4. ↑ "قواعد بيانات نهايات لعبة لومونوسوف" . ChessOK . مؤرشف من الأصل في 6 أبريل 2019.
  5. ↑ دي مان، رونالد. "ما هي أفضل طريقة للحصول على قواعد طاولة الشطرنج المكونة من 7 قطع؟ - الصفحة 3 - TalkChess.com" . talkchess.com . تاريخ الاسترجاع: 9 نوفمبر 2022 .{{cite web}}: CS1 maint: deprecated archiveal service ( link )
  6. ↑ مارك بورنيت، "صد هجمات القوة الغاشمة"، مؤرشف بتاريخ 3 ديسمبر 2016 في أرشيف الإنترنت ، قسم علوم الحاسوب بجامعة فرجينيا ، 2007
  7. ↑ كريستوف بار؛ يان بيلزل؛ بارت برينيل (2010). فهم التشفير: كتاب دراسي للطلاب والممارسين . سبرينغر. ص 7. ISBN  978-3-642-04100-6.

انظر أيضاً