algorithms in python

الخوارزميات في بيثون

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

محتوى:

• 1.0 - تقسيم وقهر
  • 1.1 - مشكلة الضرب بينغر
  • 1.2 - دمج فرز (وفرز الإدراج)
  • 1.3 - انقلابات العد
  • 1.4 - الحد الأقصى
• 2.0 - خوارزميات عشوائية
  • 2.1 - النوع السريع
  • 2.2 - خوارزمية كارجر
• 3.0 - هياكل البيانات
  • 3.1 - قائمة انتظار واتساع أول بحث
  • 3.2 - المكدس والعمق الأول
  • 3.3 - كومة ومتوسط ​​الصيانة المتوسطة
  • 3.4 - مكون متصل بقوة
  • 3.5 - مفككة و SCC
• 4.0 - خوارزميات الجشع
  • 4.1 - أنشطة السقوط
  • 4.2 - اختيار النشاط
  • 4.3 - ترميز هوفمان
  • 4.4 - خوارزمية ديجكسترا
  • 4.5 - خوارزمية بريم
  • 4.6 - خوارزمية كروسكال ومشكلة التجميع
• 5.0 - البرمجة الديناميكية
  • 5.1 - قطع قضيب
  • 5.2 - مضاعفة سلسلة المصفوفة
  • 5.3 - أطول وقت شائع
  • 5.4 - خوارزمية فلويد وارشال
• 6.0 - خوارزميات التقريب لـ NPC
  • 6.1 - غطاء الرأس
  • 6.2 - مشكلة بائع السفر
  • 6.3 - مشكلة الرضا المنطقية

1.0 - تقسيم وقهر

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

1.1 - مشكلة الضرب بينغر

• رابط مفيد
  

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

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

• وقت التشغيل:
  Back to Top

1.2 - دمج فرز (وفرز الإدراج)

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

أسوأ وقت تشغيل لهذه الخوارزمية هو.
توضح GIF أعلاه كيف يعمل Serge Sort:

الفكرة الرئيسية
قسّم القائمة غير المصنفة إلى قوائم فرعية N ، كل عنصر يحتوي على عنصر واحد (يتم اعتبار قائمة عنصر واحد مرتبة) ودمج القواعد الفرعية مرارًا وتكرارًا لإنتاج القواعد الفرعية المصنفة الجديدة حتى لا يتبقى سوى أحد القاتمين الفرعيين. ستكون هذه هي القائمة المرتبة.
ملكيات

• وقت التشغيل:
  Back to Top

1.3 - انقلابات العد

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

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

• وقت التشغيل:
  Back to Top

1.4 - الحد الأقصى

• رابط مفيد
  تكمن مشكلة السوس الفرعية القصوى في مهمة العثور على المساعد الفرعي المتجاورة ضمن صفيف أحادي البعد ، A [1 ... n] ، للأرقام التي لها أكبر مبلغ.
  الفكرة الرئيسية
  إذا استخدمنا استراتيجية الفجوة والقهر ، إذا كانت الصفيف [منخفضة .. عالية] ويتم تمثيل النقطة الوسطى على أنها منتصف. [i..j] هو ما نريد حسابه. يجب أن تكون [i..j] واحدة من الحالات الثلاث:
  

• A [i..j] ينتمي إلى [منخفضة .. mid]
• A [i..j] ينتمي إلى [منتصف+1.. عالي]
• أنا <= mid <j
  لذلك ، تتمثل مهمتنا في العثور على أكبر مجموعة فرعية تعبر النقطة المتوسطة واختيار أكبرها من بين هذه الخوارزميات الثلاثة.

ملكيات

• وقت التشغيل:
  Back to Top

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

سأتحدث عن هذا القسم عن خوارزميات استخدمت متغيرًا عشوائيًا في الداخل.

2.1 - النوع السريع

• رابط مفيد
  

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

• أسوأ أداء للأداء o (n^2)
• أفضل أداء لحالة O (n log n) أو o (n) مع قسم ثلاثي الاتجاه
• متوسط ​​أداء الحالة o (n log n)
  Back to Top

2.2 - خوارزمية كارجر

• رابط مفيد
  تعتمد فكرة الخوارزمية على مفهوم تقلص الحافة (U ، V) في رسم بياني غير موجه G = (V ، E). من الناحية غير الرسمية ، فإن تقلص الحافة يدمج العقد U و V في واحدة ، مما يقلل من العدد الإجمالي للعقد الرسم البياني بمقدار واحد. يوضح الشكل أدناه كيف يعمل الانكماش. في الرقم الفرعي اليسار ، يتم دمج عقدتين سوداء غامقان في واحد (الشكل الفرعي في اليمين).

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

• باحتمال كبير يمكننا العثور على جميع التخفيضات في وقت تشغيل
• عدم العثور على احتمال قطع دقيقة هو الأوقات.
  Back to Top

3.0 - هياكل البيانات

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

3.1 - قائمة انتظار واتساع أول بحث

• Link1 مفيدة
  إن قائمة الانتظار ، المعروفة أيضًا باسم FIFO ، هي اختصار لـ First In ، أولاً ، طريقة لتنظيم ومعالجة المخزن المؤقت للبيانات ، حيث تتم معالجة أقدم إدخال (أول) ، أو "رأس" في قائمة الانتظار ، أولاً.

الفكرة الرئيسية
يستخدم BFS لحساب العقد القابلة للوصول من عقدة مصدر في رسم بياني غير موجه أو موجه. تتم طباعة العقد القابلة للوصول بالترتيب الموجود. يتم استخدام قائمة انتظار لتخزين العقد الرمادية الملونة (انظر GIF أدناه). مصطلح "اتساع" في BFS يعني إيجاد عقدة يمكن الوصول إليها مع أقصر طول. يمتد اتساع الحدود بين العقد التي تمت زيارتها والعقد غير المكتشفة.

ملكيات

• وقت التشغيل: t (n) = o (v+e) ، v هو عدد القمم ، e هو عدد الحواف
  Back to Top

3.2 - المكدس والعمق الأول

• Link1 مفيدة
  Stack ، المعروف أيضًا باسم Lifo ، لديه خاصية Last In ، أولاً.
  

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

ملكيات

• وقت التشغيل: t (n) = o (v+e) ، v هو عدد القمم ، e هو عدد الحواف
  Back to Top

3.3 - كومة ومتوسط ​​الصيانة المتوسطة

• Link1 مفيدة
  الكومة هي بنية بيانات متخصصة قائمة على الأشجار تفي بخاصية الكومة: إذا كانت P هي عقدة الوالدين لـ C ، فإن المفتاح (القيمة) P هو إما أكبر من أو يساوي (في كومة أقصى) أو أقل من أو يساوي (في كومة دقيقة) مفتاح C. [1] تسمى العقدة في "الجزء العلوي" للكومة (مع عدم وجود آباء) عقدة الجذر.

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

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

ملكيات

• وقت التشغيل:
  Back to Top

3.4 - مكون متصل بقوة

• رابط مفيد
  يسمى الرسم البياني الموجه بشكل قوي إذا كان هناك مسار في كل اتجاه بين كل زوج من رؤوس الرسم البياني. في رسم بياني موجه G الذي قد لا يكون نفسه متصلاً بقوة ، يُقال إن زوجًا من الرؤوس U و V مرتبطان بقوة ببعضهما البعض إذا كان هناك مسار في كل اتجاه بينهما.

الفكرة الرئيسية
من خلال الملاحظة البسيطة ، اكتشفنا أن Tranpose of Graph لديه نفس SCCs مثل الرسم البياني الأصلي. ندير DFS مرتين. لأول مرة ، نقوم بتشغيله على G وحساب وقت التشطيب لكل قمة. وبعد ذلك ، نقوم بتشغيل DFS على g^t ولكن في الحلقة الرئيسية من DFS ، فكر في الرؤوس من أجل انخفاض وقت التشطيب.
ملكيات

• وقت التشغيل: ، الخامس هو عدد الرؤوس ، e هو عدد الحواف
  Back to Top

3.5 - مفككة و SCC

• رابط مفيد
  هي بنية بيانات مفككة ، تسمى أيضًا بنية بيانات الاتحاد أو مجموعة الدمج ، هي بنية بيانات تتبع مجموعة من العناصر المقسمة إلى عدد من مجموعات فرعية مفصول (غير متداخلة).
  للحصول على مجموعة ساذجة ، يدعم عمليتين رئيسيتين ، Make و Union. جعل مجموعة جعل كل قمة الرأس مجموعة مستقلة. يضع الاتحاد رؤوستين في مجموعة واحدة.

الفكرة الرئيسية
في رسم بياني غير موجه ، يمكننا استخدام بنية البيانات هذه لمعرفة عدد SCCs. يوضح الشكل أدناه كيف يعمل.

ملكيات

• يمكننا استخدام مجريات الاتجاه الموزون لتوفير الوقت عند استدعاء Find_set
• يمكن أن يحسن ضغط المسار بشكل كبير كفاءة الوقت للعثور على الاتحاد
  Back to Top

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

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

4.1 - أنشطة السقوط

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

كما هو موضح أعلاه ، فإننا نعتبر التكلفة الناجمة عن نشاطين تراوحت بشكل مختلف في ترتيبين (I ، J). اكتشفنا أن التكلفة في الخوارزمية الجشع أصغر من الهيكل الأمثل من خلال قيمة wi*lj - wj*li ، والتي هي أكبر من أو تساوي 0.

ملكيات

• يهيمن على وقت التشغيل بالفرز
  Back to Top

4.2 - اختيار النشاط

• رابط مفيد
  في هذه المشكلة ، كل نشاط له وقت البدء الخاص به ووقت الانتهاء. هدفنا هو اختيار مجموعة فرعية ذات الطول ، حيث تكون الوظائف متوافقة.
  

الفكرة الرئيسية
قمنا بفرز المصفوفة وفقًا لوقت النهاية. وضعت الخوارزمية أول وظيفة لها وقت بدء أكبر من وقت الانتهاء من الوظيفة الأخيرة.
ملكيات

• وقت تشغيل اختيار النشاط المتكرر
  Back to Top

4.3 - ترميز هوفمان

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

طريقة واحدة لترميز هذا الكتاب هي استخدام ترميز الطول الثابت. كما هو موضح أدناه:

أما بالنسبة لترميز هوفمان ، فإن بنية الأشجار الفعلية تبدو مثل هذا:

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

ملكيات

• الإجراء ينتج Huffman رمز بادئة مثالي
  Back to Top

4.4 - خوارزمية ديجكسترا

• رابط مفيد
  

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

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

ملكيات

• وقت التشغيل بناءً على قائمة انتظار ذات أولوية دقيقة تنفذها كومة فيبوناتشي
  Back to Top

4.5 - خوارزمية بريم

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

الفكرة الرئيسية
يمكن وصف الخوارزمية بشكل غير رسمي بأنها تنفيذ الخطوات التالية:

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

ملكيات

• وقت التشغيل

• مصفوفة مجاورة ، البحث
• كومة ثنائية وقائمة المجاورة
• كومة فيبوناتشي وقائمة المجاورة
  Back to Top

4.6 - خوارزمية كروسكال ومشكلة التجميع

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

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

ملكيات

• وقت التشغيل O (ELOGV)
  Back to Top

5.0 - البرمجة الديناميكية

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

5.1 - قطع قضيب

• رابط مفيد
  بالنظر إلى قضيب بطول N بوصة ومجموعة من الأسعار التي تحتوي على أسعار جميع أجزاء من الحجم أصغر من n. تحديد الحد الأقصى للقيمة التي يمكن الحصول عليها عن طريق قطع قضيب وبيع القطع.
  يوضح الجدول التالي العلاقة بين السعر والطول.

لذلك ، إذا كان طول القضيب هو 8 وقيم القطع المختلفة على النحو التالي ، فإن القيمة القصوى التي يمكن الحصول عليها هي 22 (عن طريق قطع قطعتين من الطويتين 2 و 6).

الفكرة الرئيسية
ننظر إلى التحلل الذي يتكون من قطعة أولى من الطول ، لقد قطعت الطرف الأيسر ، ثم بقية اليد اليمنى من الطول n-i. لذلك ، يشبه الرمز الكاذب:

تبدو شجرة العودية التي تظهر المكالمات العودية الناتجة عن مكالمة cut_rod (p ، n):

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

ملكيات

• التعقيد الزمني للتنفيذ أعلاه هو O (n^2)
  Back to Top

5.2 - مضاعفة سلسلة المصفوفة

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

الفكرة الرئيسية
الهيكل الأمثل:

ملكيات

• تعقيد الوقت للتنفيذ أعلاه
  Back to Top

5.3 - أطول وقت شائع

• رابط مفيد
  أطول مشكلة الشائعة (LCS) هي مشكلة إيجاد أطول فترة شائعة لجميع التسلسلات في مجموعة من التسلسلات (غالبًا ما يكونان مجرد تسلسلان).

الفكرة الرئيسية
من CLRs ، الهيكل الأمثل لهذه المشكلة هو:

ملكيات

• تعقيد الوقت للتنفيذ أعلاه $ theta (mn) $
  Back to Top

5.4 - خوارزمية فلويد وارشال

• رابط مفيد
  خوارزمية Floyd -Warshall هي خوارزمية للعثور على أقصر مسارات في رسم بياني مرجح مع أوزان إيجابية أو سلبية (ولكن بدون دورات سلبية).

الفكرة الرئيسية
تستند هذه الخوارزمية إلى ملاحظة بديهية للغاية. لنفترض أن لدينا مجموعة فرعية {1 ، 2 ، 3 ، 4 ، ... ، k} (تشير إلى V (k)) لمجموعة القمم الأصلية {1 ، 2 ، 3 ، ... ، n}. إذا كان P هو أقصر مسار من I إلى J في V (K) ، فلدينا حالتان. أولاً ، إذا لم يكن K في P ، فيجب أن يكون P مسارًا أقصر في V (K-1). ثانياً ، إذا كان K في P ، فيمكننا فصل المسار إلى قسمين ، P1: i K ، P2: K. ي. ويجب أن يكون P1 أقصر مسار من I إلى K مع V (K-1) ، يجب أن يكون P2 هو أقصر مسار من K إلى J مع V (K-1).

ملكيات

• تعقيد الوقت للتنفيذ أعلاه
  Back to Top

6.0 - خوارزميات التقريب لـ NPC

من ويكيبيديا ، فإن مشكلة القرار المكتملة NP هي مشكلة تابعة لكل من فئات التعقيد NP و NP-Hard. في هذا السياق ، تعني NP "وقت متعدد الحدود غير المحدود". غالبًا ما يتم الإشارة إلى مجموعة المشكلات NP-Complete بواسطة NP-C أو NPC.

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

6.1 - غطاء الرأس

• رابط مفيد
  غطاء قمة الرأس (غلاف العقدة في بعض الأحيان) من الرسم البياني هو مجموعة من الرؤوس بحيث تكون كل حافة من الرسم البياني حادثة على الأقل قمة واحدة من المجموعة. يوضح الشكل أدناه غطاء قمة الحد الأدنى (حيث يجب أن تحتوي مجموعة الغطاء على اثنين على الأقل من vertice ، صفر والآخر لن يساعد).

الفكرة الرئيسية
من الصعب للغاية العثور على غطاء قمة الحد الأدنى ، لكن يمكننا العثور على غطاء تقريبي مع مرتين على الأكثر في وقت متعدد الحدود.

ملكيات

• المتدرب-Vertex-cover هو خوارزمية قرب من وقت الحدود 2.
  Back to Top

6.2 - مشكلة بائع السفر

• رابط مفيد
  تسأل مشكلة البائع المتجول (TSP) السؤال التالي: "بالنظر إلى قائمة بالمدن والمسافات بين كل زوج من المدن ، ما هو أقصر مسار ممكن يزور كل مدينة ويعود إلى مدينة الأصلية؟" GIF يظهر القوة الغاشمة لـ TSP.

الفكرة الرئيسية
خوارزمية التقريب لـ TSP هي خوارزمية جشع (CLRS P1114). هنا ، أريد أيضًا تقديم خوارزمية دقيقة لـ TSP باستخدام البرمجة الديناميكية.

subproblem: لكل وجهة j ∈ {1،2 ، ... ، n} ، كل مجموعة فرعية S ⊆ {1،2 ، ... ، n} التي تحتوي على 1 و j ، اسمح LS ، J = الحد الأدنى للمسار من 1 إلى J الذي يزور بالضبط رؤوس S [بالضبط مرة واحدة]. لذلك ، تكرار المقابل:

ملكيات

• وقت التشغيل للخوارزمية الدقيقة:
  Back to Top

6.3 - مشكلة الرضا المنطقية

• رابط مفيد
  مشكلة الرضا المنطقية (تسمى أحيانًا مشكلة الرضا المقترحة والاختصار عليها كرضا أو SAT) هي مشكلة تحديد ما إذا كان هناك تفسير يلبي صيغة منطقية معينة.

3-SAT هي واحدة من مشكلات KARP 21 NP-COMPLETE ، ويستخدم كنقطة انطلاق لإثبات أن المشكلات الأخرى هي أيضًا NP-HARD.

هنا ، أقدم خوارزمية باباديميتريو من أجل 2-سات (هذه خوارزمية مثيرة للغاية للغاية ، لذلك قررت تقديمها على الرغم من أن 2-SAT ليست NPC).

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

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

ملكيات

• للحصول على مثيل 2-SAT للمرض مع متغيرات N ، تنتج خوارزمية Papadimitriou مهمة مرضية مع احتمال ≥ 1-1/n
• يدير في وقت الحدود
• دائمًا ما يكون صحيحًا على مثيلات غير مرضية
  Back to Top