اكتشف 8 أنواع من الخوارزميات لحل المشكلات بكفاءة

This post is also available in: English (الإنجليزية) हिन्दी (الهندية)

ما هي الخوارزمية؟

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

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

في هذه المقالة ، سنناقش حوالي 8 أنواع من الخوارزميات.

صفات الخوارزميات الجيدة

يجب أن تتمتع الخوارزمية الجيدة بالصفات التالية:

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

مثال على الخوارزمية – إيجاد أكبر من بين ثلاثة أرقام

Step 1: Start
Step 2: Declare variables a, b and c
Step 3: Read variables a, b and c.
Step 4: If a > b
		If a > c 
				Display a is the largest number
		Else
				Display c is the largest number
	Else
		If b > c
			Display b is the largest number
		Else
			Display c is the largest number
Step 5: Stop

أنواع الخوارزميات

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

بناءً على مبدأ العمل ، يتم تصنيف الخوارزميات إلى 8 أنواع مختلفة.

• خوارزميات عودية بسيطة
• خوارزميات التراجع
• خوارزميات فرق تسد
• خوارزميات البرمجة الديناميكية
• الخوارزميات الجشعة
• خوارزميات الفرع والربط
• خوارزميات القوة الغاشمة
• الخوارزميات العشوائية

خوارزميات تكرارية بسيطة

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

الخوارزمية العودية هي خوارزمية تستدعي نفسها بقيم إدخال “أصغر (أو أبسط)” ، وتحصل على نتيجة الإدخال الحالي من خلال تطبيق عمليات بسيطة على القيمة التي يتم إرجاعها للمدخلات الأصغر (أو الأبسط). بشكل عام ، إذا كان من الممكن حل مشكلة باستخدام حلول لإصدارات أصغر من نفس المشكلة ، وتقليل الإصدارات الأصغر إلى حالات قابلة للحل بسهولة ، فيمكن عندئذٍ استخدام خوارزمية تكرارية لحل هذه المشكلة. على سبيل المثال ، يمكن الحصول على عناصر مجموعة محددة بشكل متكرر ، أو قيمة دالة محددة بشكل متكرر بواسطة خوارزمية تكرارية.

تتوافق الخطوات الأولية للخوارزمية العودية مع البند الأساسي للتعريف العودي وهي تحدد العناصر الأساسية. ثم يتم اتباعها بخطوات تتوافق مع البند الاستقرائي ، والتي تقلل من حساب عنصر من جيل إلى حساب عناصر الجيل السابق مباشرة.

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

دعونا نفكر في مشكلة أن على المبرمج تحديد مجموع أول n من الأعداد الطبيعية ، هناك عدة طرق للقيام بذلك ولكن أبسط طريقة هي ببساطة إضافة الأرقام التي تبدأ من 1 إلى n. لذا تبدو الوظيفة ببساطة ، ببساطة إضافة واحدة تلو الأخرى – f (n) 1 2 3 …

في النهج العودي ، يصبح:

f(n) = 1,       		n = 1;
f(n) = n + f(n - 1),	        n > 1;

هناك فرق بسيط بين الأسلوب الأول والنهج الثاني وهو أنه في الطريقة الثانية يتم استدعاء الوظيفة “f ()” نفسها داخل الوظيفة ، لذلك يتم تسمية هذه الظاهرة باسم العودية والوظيفة التي تحتوي على العودية هي تسمى الوظيفة العودية ، في النهاية ، هذه أداة رائعة في يد المبرمجين لترميز بعض المشاكل بطريقة أسهل بكثير وفعالة.

خوارزميات التراجع

التراجع هو خوارزمية عامة لإيجاد كل (أو بعض) الحلول لبعض المشاكل الحسابية ، مثل مشاكل الرضا عن القيود ، التي تبني بشكل تدريجي المرشحين للحلول ، وتتخلى عن مرشح (“التراجع”) بمجرد أن تحدد أن المرشح لا يستطيع من المحتمل أن تكتمل إلى حل صالح.

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

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

يعد التراجع أداة مهمة لحل مشاكل الرضا عن القيود ، مثل الكلمات المتقاطعة والحساب اللفظي و Sudokuوالعديد من الألغاز الأخرى. غالبًا ما يكون الأسلوب الأكثر ملاءمة (إن لم يكن الأكثر فاعلية) للتحليل ومشكلة حقيبة الظهر ومشكلات التحسين التوافقية الأخرى. وهو أيضًا أساس ما يسمى لغات البرمجة المنطقية مثل Icon و Planner و Prolog.

التراجع هو أسلوب يعتمد على الخوارزميات لحل المشكلات. يستخدم استدعاء متكرر لإيجاد الحل من خلال بناء قيم متزايدة خطوة بخطوة مع مرور الوقت. إنه يزيل الحلول التي لا تؤدي إلى حل المشكلة بناءً على القيود المعطاة لحل المشكلة.

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

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

دعونا نستخدم مشكلة التراجع هذه لإيجاد حل لمشكلة N-Queen.

في مسألة N-Queen ، حصلنا على رقعة شطرنج N × N وعلينا وضع n ملكات على السبورة بطريقة لا تهاجم فيها ملكتان بعضهما البعض. ستهاجم الملكة ملكة أخرى إذا تم وضعها في نقاط أفقية أو رأسية أو قطرية في طريقها. هنا ، سنفعل مشكلة 4 ملكة.

هنا الحل –

الناتج الثنائي لـ n مشكلة ملكة مع 1s كملكات إلى المواقف الموضوعة.

{0 , 1 , 0 , 0}

{0 , 0 , 0 , 1}

{1 , 0 , 0 , 0}

{0 , 0 , 1 , 0}

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

خوارزمية لحل مشكلة n-Queen:

Step 1 − Start from 1st position in the array.

Step 2 − Place queens on the board and check. Do,

Step 2.1 − After placing the queen, mark the position as a part of the solution and then recursively check if this will lead to a solution.

Step 2.2 − Now, if placing the queen doesn’t lead to a solution and trackback and go to step (a) and place queens to other rows.

Step 2.3 − If placing the queen returns a lead to solution return TRUE.

Step 3 − If all queens are placed return TRUE.

Step 4 − If all rows are tried and no solution is found, return FALSE.

خوارزميات فرق تسد

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

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

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

يمكن تقسيم هذه التقنية إلى الأجزاء الثلاثة التالية:

1. قسمة: يتضمن ذلك تقسيم المشكلة إلى مشكلة فرعية.
2. قهر: مشكلة فرعية عن طريق الاتصال بشكل متكرر حتى يتم حل المشكلة الفرعية.
3. اجمع: تم حل المشكلة الفرعية حتى نجد حلًا للمشكلة.

فيما يلي بعض الخوارزميات القياسية التي تتبع خوارزمية فرق تسد.

1. البحث الثنائي هو خوارزمية بحث. في كل خطوة ، تقارن الخوارزمية عنصر الإدخال x بقيمة العنصر الأوسط في المصفوفة. إذا تطابقت القيمتان ، فقم بإرجاع فهرس الوسط. خلاف ذلك ، إذا كان x أقل من العنصر الأوسط ، فإن الخوارزمية تتكرر للجانب الأيسر من العنصر الأوسط ، وإلا تتكرر للجانب الأيمن من العنصر الأوسط.
2. Quicksort هو خوارزمية الفرز. تختار الخوارزمية عنصرًا محوريًا ، وتعيد ترتيب عناصر المصفوفة بحيث تنتقل جميع العناصر الأصغر من العنصر المحوري المختار إلى الجانب الأيسر من المحور ، وتتحرك جميع العناصر الأكبر إلى الجانب الأيمن. أخيرًا ، تقوم الخوارزمية بفرز المصفوفات الفرعية على يسار ويمين العنصر المحوري بشكل متكرر.
3. دمج الفرز هو أيضًا خوارزمية الفرز. تقسم الخوارزمية المصفوفة إلى نصفين ، ثم تقوم بفرزها بشكل متكرر ، ثم تقوم أخيرًا بدمج النصفين المصنفين.
4. يعتبر أقرب زوج من النقاط مشكلة للعثور على أقرب زوج من النقاط في مجموعة من النقاط في المستوى x-y. يمكن حل المشكلة في زمن O (n ^ 2) عن طريق حساب مسافات كل زوج من النقاط ومقارنة المسافات لإيجاد الحد الأدنى. تحل خوارزمية Divide and Conquer المشكلة في وقت O (N log N).

خوارزميات البرمجة الديناميكية

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

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

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

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

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

لذلك يمكننا أن نقول ذلك –

• يجب أن تكون المشكلة قابلة للتقسيم إلى مشكلة فرعية متداخلة أصغر.
• يمكن تحقيق الحل الأمثل باستخدام الحل الأمثل للمشاكل الفرعية الأصغر.
• تستخدم الخوارزميات الديناميكية Memoization.

يمكن حل مشاكل الكمبيوتر التالية باستخدام نهج البرمجة الديناميكية –

• سلسلة أرقام فيبوناتشي
• مشكلة حقيبة الظهر
• برج هانوي
• أقصر طريق من قبل فلويد وارسال
• أقصر طريق لديجكسترا
• جدولة المشروع

يمكن استخدام البرمجة الديناميكية بأسلوب تنازلي ومن أسفل إلى أعلى. وبالطبع ، في معظم الأحيان ، تكون الإشارة إلى ناتج الحل السابق أرخص من إعادة الحساب من حيث دورات وحدة المعالجة المركزية.

الخوارزميات الجشعة

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

على سبيل المثال ، الاستراتيجية الجشعة لمشكلة البائع المتجول (والتي تتسم بدرجة عالية من التعقيد الحسابي) هي الطريقة التجريبية التالية: “في كل خطوة من الرحلة ، قم بزيارة أقرب مدينة لم تتم زيارتها”. لا يهدف هذا الاستدلال إلى إيجاد أفضل حل ، لكنه ينتهي بعدد معقول من الخطوات ؛ عادة ما يتطلب إيجاد حل أمثل لمثل هذه المشكلة المعقدة خطوات كثيرة بشكل غير معقول. في التحسين الرياضي ، تحل الخوارزميات الجشعة على النحو الأمثل المشكلات التجميعية التي لها خصائص matroids ، وتعطي تقديرات تقريبية للعامل الثابت لمشاكل التحسين في البنية شبه المعيارية.

تستخدم معظم خوارزميات الشبكات النهج الجشع. فيما يلي قائمة بالقليل منهم –

• مشكلة بائع متجول
• خوارزمية شجرة الامتداد الدنيا من Prim
• الحد الأدنى من خوارزمية Kruskal الممتدة لشجرة الامتداد
• خوارزمية Dijkstra’s Minimal Spanning Tree Algorithm
• الرسم البياني – خريطة التلوين
• رسم بياني – غطاء Vertex
• مشكلة حقيبة الظهر
• مشكلة جدولة العمل

خوارزميات الفرع والربط

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

تعتمد الخوارزمية على التقدير الفعال للحدود الدنيا والعليا للمناطق / الفروع في مساحة البحث. إذا لم تكن هناك حدود متاحة ، فإن الخوارزمية تتدهور إلى بحث شامل.

تم اقتراح الطريقة لأول مرة من قبل Ailsa Land و Alison Doig أثناء إجراء بحث في كلية لندن للاقتصاد برعاية شركة British Petroleum في عام 1960 من أجل البرمجة المنفصلة ، وأصبحت الأداة الأكثر استخدامًا لحل مشكلات تحسين NP-hard. فرع ومقيد “حدث لأول مرة في عمل ليتل وآخرون. على مشكلة بائع متجول.

دعونا نرى نهج الفرع والربط لحل مشكلة حقيبة الظهر 0/1: يمكن تحسين حل التراجع إذا عرفنا ارتباطًا بأفضل حل ممكن للشجرة الفرعية مع كل عقدة. إذا كان الأفضل في الشجرة الفرعية أسوأ من الأفضل الحالي ، فيمكننا ببساطة تجاهل هذه العقدة والأشجار الفرعية الخاصة بها. لذلك نحسب الحد (أفضل حل) لكل عقدة ونقارن الحد مع أفضل حل حالي قبل استكشاف العقدة.

الحدود النموذجية المستخدمة في الرسم البياني أدناه هي ، A down يمكن أن يعطي 315 دولارًا ، B down يمكن أن يعطي 275 دولارًا ، C down يمكن 225 دولارًا ، D down يمكن أن يكون 125 دولارًا ، E down يمكن أن يكون 30 دولارًا.

خوارزميات القوة الغاشمة

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

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

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

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

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

لذا ، تعيد تعيين جميع الأرقام إلى 0 وتجربها واحدة تلو الأخرى: 0001 ، 0002 ، 0003 ، وهكذا حتى تفتح. في أسوأ السيناريوهات ، قد يستغرق الأمر 104 أو 10000 محاولة للعثور على مجموعتك.

من الأمثلة الكلاسيكية في علوم الكمبيوتر مشكلة البائع المتجول (TSP). افترض أن بائعًا يحتاج إلى زيارة 10 مدن في جميع أنحاء البلاد. كيف يمكن تحديد الترتيب الذي يجب أن تتم زيارة هذه المدن به بحيث يتم تقليل إجمالي المسافة المقطوعة؟

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

الخوارزميات العشوائية

الخوارزمية العشوائية هي خوارزمية تستخدم درجة من العشوائية كجزء من منطقها. تستخدم الخوارزمية عادةً بتات عشوائية منتظمة كمدخل مساعد لتوجيه سلوكها ، على أمل تحقيق أداء جيد في “الحالة المتوسطة” على جميع الخيارات الممكنة للعشوائية التي تحددها البتات العشوائية ؛ وبالتالي فإما أن يكون وقت التشغيل أو الإخراج (أو كليهما) متغيرات عشوائية.

على المرء أن يميز بين الخوارزميات التي تستخدم الإدخال العشوائي بحيث تنتهي دائمًا بالإجابة الصحيحة ، ولكن عندما يكون وقت التشغيل المتوقع محدودًا (خوارزمية Las Vegas ، على سبيل المثال ، Quicksort) ، والخوارزميات التي لديها فرصة لإنتاج نتيجة غير صحيحة (خوارزمية مونت كارلو ، على سبيل المثال ، خوارزمية مونت كارلو لمشكلة MFAS) أو تفشل في إنتاج نتيجة إما عن طريق الإشارة إلى الفشل أو الفشل في الإنهاء. في بعض الحالات ، تكون الخوارزميات الاحتمالية هي الوسيلة العملية الوحيدة لحل مشكلة ما.

في الممارسة الشائعة ، يتم تقريب الخوارزميات العشوائية باستخدام مولد رقم شبه عشوائي بدلاً من مصدر حقيقي للبتات العشوائية ؛ قد ينحرف مثل هذا التنفيذ عن السلوك النظري المتوقع.