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

خوارزمية التقريب

1٬864 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: في علوم الكمبيوتر وبحوث العمليات، تعد خوارزميات التقريب خوارزميات فعالة تعمل على إيجاد حلول تقريبية لمشاكل التحسين (وخاصة مشاكل مسائل NP صعبة) مع ضمانات قابلة للإثبات على مسافة الحل المرتجع إلى الحل الأمثل. تتناول المقالة 11 قسماً، منها «ضمانات الأداء»، «العملية» و«,».
المحتويات
  1. ضمانات الأداء
  2. العملية
  3. ,
  4. تقنيات تصميم الخوارزميات
  5. مصطلحات إبسيلون
  6. تركيب مزدوج
  7. صلابة التقريب
  8. بنية خوارزميات التقريب
  9. الضمانات اللاحقة
  10. مقدمة
  11. البحث المحلي

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

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

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

ضمانات الأداء

من جانب آخر، حيث f (y) هي قيمة/تكلفة الحل y للمثال x. من الواضح أن ضمان الأداء أكبر من أو يساوي 1 ويساوي 1 فقط إذا كان y هو الحل الأمثل. إذا ضمنت الخوارزمية A إرجاع الحلول بضمان أداء لا يتجاوز r (n)، فيُقال أن A هي خوارزمية تقريب r (n) ولها نسبة تقريب r (n). على نحو مماثل، يُقال إن المشكلة التي تحتوي على خوارزمية تقريب r (n) قابلة للتقريب r (n) أو لها نسبة تقريب r (n).

من جهة ثانية، وهذا يعني أن هو أكبر حد لنسبة التقريب، r، الذي نراه في جميع الحالات المحتملة للمشكلة. وبالمثل، نسبة الأداء المقاربة يكون:

وفي هذا الصدد، بالنسبة لبعض خوارزميات التقريب، من الممكن إثبات خصائص معينة حول تقريب النتيجة المثلى. مثلًا، يتم تعريف خوارزمية التقريب ρ A على أنها خوارزمية تم إثبات أن القيمة/التكلفة، f (x)، للحل التقريبي A (x) لحالة x لن تكون أكثر (أو أقل، اعتمادًا على الموقف) من عامل ρ مضروبًا في القيمة، OPT، للحل الأمثل.

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

وفي السياق ذاته، يُطلق على العامل ρ اسم ضمان الأداء النسبي. تتمتع خوارزمية التقريب بضمان أداء مطلق أو خطأ محدود c، إذا تم إثبات ذلك لكل حالة x

ومن جهة أخرى، ضمان الأداء المطلق لبعض خوارزميات التقريب A، حيث يشير x إلى حالة من المشكلة، وحيث هل ضمان أداء A على x (أي ρ لحالة المشكلة x) هو:

وفي هذا الصدد، بالنسبة لمشاكل التقليل، توفر الضمانتان المختلفتان نفس النتيجة، وبالنسبة لمشاكل التعظيم، فإن ضمان الأداء النسبي لـ ρ يعادل ضمان الأداء لـ . في الأدبيات، كلا التعريفين شائعان ولكن من الواضح أي تعريف يتم استخدامه، لأنه بالنسبة لمشاكل التعظيم، حيث ρ ≤ 1 بينما r ≥ 1.

من جانب آخر، وبالمثل، يتم تعريف ضمان الأداء، R (x,y)، لحل y لمثيل x على النحو التالي

العملية

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

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

,

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

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

علاوةً على ذلك، أعطيت حلا قابلا للتنفيذ ، مع ، نريد ضمانًا لجودة الحل، وهو الأداء الذي يجب ضمانه (عامل التقريب).

وفي هذا الصدد، على وجه التحديد، وجود ، تحتوي الخوارزمية على عامل تقريب (أو نسبة تقريب) لو ، لدينا:

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

تقنيات تصميم الخوارزميات

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

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

مصطلحات إبسيلون

من جانب آخر، في الأدبيات، تعني نسبة التقريب لمشكلة التعظيم (التقليل) لـ c - ϵ (الحد الأدنى: c + ϵ) أن الخوارزمية لها نسبة تقريب لـ c ∓ ϵ لـ ϵ > 0 التعسفية ولكن النسبة لم يتم إظهارها (أو لا يمكن إظهارها) لـ ϵ = 0. ومن الأمثلة على ذلك النسبة المثلى لعدم إمكانية التقريب — عدم وجود تقريب - وهي 7 / 8 + ϵ لحالات القابلة للإرضاء بسبب . كما ذكرنا سابقًا، عندما تكون c = 1، يُقال إن المشكلة لها .

الاستشهادات

من جهة ثانية، قد يظهر مصطلح ϵ عندما تقدم خوارزمية التقريب خطأ مضاعفًا وخطأ ثابتًا بينما يصل الحد الأدنى الأمثل لحالات الحجم n إلى ما لا نهاية كما يفعل n. في هذه الحالة، تكون نسبة التقريب c ∓ k / أو بي تي = c ∓ o(1) لبعض الثوابت c و k. إذا كانت قيمة ϵ > 0 عشوائية، فيمكن اختيار قيمة N كبيرة بما يكفي بحيث يكون الحد k / أو بي تي < ϵ لكل n ≥ N. لكل قيمة ϵ ثابتة، يمكن حل الحالات ذات الحجم n < N باستخدام القوة الغاشمة، مما يُظهر نسبة تقريب - وجود خوارزميات تقريب مضمونة - لـ c ∓ ϵ لكل ϵ > 0.

تركيب مزدوج

وفي هذا السياق، تضمين المشكلة في بعض المقاييس ثم حل المشكلة بناءً على هذا المقياس. يُعرف هذا كذلك بالتضمين المتري.

كذلك، - العينة العشوائية واستخدام العشوائية بشكل عام بالتزامن مع الأساليب المذكورة أعلاه.

صلابة التقريب

ومن جهة أخرى، ترتبط خوارزميات التقريب كمجال بحثي ارتباطًا وثيقًا ، حيث يتم إثبات عدم وجود خوارزميات فعالة بنسب تقريب معينة (بشرط فرضيات معروفة على نطاق واسع مثل تخمين P ≠ NP) عن طريق الاختزالات. في حالة مشكلة بائع السفر المتري، فإن أفضل نتيجة معروفة لعدم القدرة على التقريب تستبعد الخوارزميات التي تحتوي على نسبة تقريب أقل من 123/122 ≈ 1.008196 ما لم يكن P = NP، كاربينسكي، لامبيس، شميد. عندما يقترن هذا بمعرفة وجود خوارزمية التقريب 1.5 لكريستوفيدس، فإن هذا يخبرنا أن عتبة التقريب لبائع السفر المتري (إن وجدت) تقع في مكان ما بين 123/122 و1.5.

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

بنية خوارزميات التقريب

نظرا لمشكلة التحسين:

ومجموعة الحلول الممكنة:

كذلك، أين هي مشكلة تقريبية، مجموعة المدخلات و مجموعة الحلول، يمكننا تعريف دالة التكلفة:

إيجاد الحل الأفضل لمشكلة التعظيم أو التصغير:

الضمانات اللاحقة

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

مقدمة

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

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

البحث المحلي

من جانب آخر، الترقيم والبرمجة الديناميكية (والتي تُستعمل كذلك في كثير من الأحيان )

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

  • استرخاءات البرمجة الخطية
  • استرخاءات
  • الطرق الثنائية البدائية

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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