books rounding algorithms

If you do not find what you're looking for, you can use more accurate words.

# Analysis and design of algorithms # Explanation of linked list in algorithms # ranking algorithms # Basics of Algorithms and Flowcharts # Algorithms for beginners # Learn algorithms with schemas # Design and analysis of algorithms # Algorithms and data structures # Algorithms and data structure # Data structures and algorithms # Total Check Algorithms # Mathematical engineering algorithms # computer graphics algorithms # search algorithms # Cryptography algorithms # Classification Algorithms # Distribution Algorithms # memory management algorithms # Number Theory Algorithms # Integer operation algorithms

خوارزميات تقريب (Info)

وهي خوارزميات لا تعطي جواب دقيق ولكنها تعطينا جواب لنفرض انه S ونفرض انه *S هو الحل الأمثل حينها : ,هو البعد عن الجواب الأمثل . للاسف لمسألة البائع المتجول لا يوجد خوارزميات تقريب سريعة الا إذا NP=P , وهذا لانه إذا كان هناك واحدا كهذا فهو حتما سوف يحل مسألة المسار الدائري الهاملتوني، والأسوأ من هذا انه حتى إذا سينتج عن هذا ان NP=P ! بالرغم من هذا فان مسألة البائع المتجول مع خاصية متباينة المثلثات (أو مسألة البائع المتجول المترية) يوجد لها خوارزميات تقرب الإجابة المثلى لذا سوف ننظر اولا لم لا يمكن تقريب TSP بشكل عام ثم نقرب TSP مع خاصية متباينة المثلثات :

صعوبة تقريب TSP

نظرية : لكل دالة يمكن حسابها بوقت حدودي , مسألة البائع المتجول لا يمكن تقريبها بمعامل الا إذا NP=P .

برهان : لنفرض من اجل التناقض ان هناك خوارزمية حدودية تقرب TSP بمعامل سنسميه سوف نُري انه يمكن استخدام لكي نقرر مسألة المسار الدائري الهاملتوني ( حينها NP=P ) .

الفكرة المركزية هي اختصار مسألة المسار الهاملتوني الدائري لمسألة البائع المتجول اي انه باعطائنا G نريد بناء مخطط كامل مع اوزان "G بحيث أنَّ:

1- إذا G يوجد فيه مسار دائري هاملتوني حينها في "G وزن حل مسألة البائع المتجول الأمثل هو n .

2- إذا G لا يوجد فيه مسار دائري هاملتوني حينها في "G وزن حل مسألة البائع المتجول الأمثل هو أكثر من

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

والاختصار هو كالتالي : لكل ضلع من اضلاع G ضع وزن 1 , وكل الأضلاع ليست اضلاع ل-G وزنها هو وهذا سوف يكون "G .

يمكن ان نرى انه إذا في G يوجد مسار دائري هاملتوني حينها وزن TSP في "G هو n , اما إذا G لم يحوِ مسار دائري هاملتوني فعليه استخدام ضلع واحدة على الاقل وزنها لذا فان وزن TSP يكون أكثر من

تقريب مسألة البائع المتجول المترية

الخوارزمية :

جد الشجرة الممتدة ذات الحد الأدنى (MST) ولنسمها T .
ضاعف كل ضلع في T واحصل على مخطط اويلراني
جد مسار اويلراني
اخرج المسار الذي رؤوس G حسب ترتيب ظهورها في . فلنسم المسائر الدائري الناتج C .

يمكن البرهنة بأن معامل هذه الخوارزمية هو 2 . يمكن تحسين هذه النتيجة ل- باستخدام مسألة التلائم في المخططات والخوارزمية الناتجة تكون جدا مشابهة للموصفة اعلاه.

Source: wikipedia.org