هل استخدمت خوارزمية البائع المتجول لحل مشكلة ما؟

https://stackoverflow.com/questions/264050

06-07-2019
|

سؤال

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

هل تستخدمه؟ما هي التطبيقات العملية الأخرى التي يمتلكها TSA؟

المحلول

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

لقد كانت طريقة رائعة للجمع بين فصولي النظرية والعالم الحقيقي.

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

نصائح أخرى

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

وفعلت حل المشكلة في النهاية على الرغم من:

وكان لا علاقة لي طريقة ناجحة لTSP ولكن لالغريب سألخص ما يلي:

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

وطبعا هذا ينتج مسارا الزاوي (التي كانت مقبولة) ولكن من السهل لتحويل الزوايا إلى أقواس على نحو سلس.

ونعم أنا لم تبقي رمز.

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

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

http://en.wikipedia.org/wiki/CONCORDE يكشف عن أن :

<اقتباس فقرة>

تم تطبيقها كونكورد للمشاكل من خارطة جينية، [1] وظيفة البروتين التنبؤ، [2] توجيه السيارة، [3] تحويل الصور النقطية إلى رسومات خط متواصل، [4] جدولة تحركات السفن للزلازل الدراسات الاستقصائية، [5] وفي دراسة خصائص القياس من اندماجي مشاكل الأمثل. [6]

نعم أنا استخدامها في تطبيق غيوكاشينغ للتخطيط الطريق.

ويستخدم حاليا على مسافة خط مستقيم بين النقاط ولكن يجب بشكل صحيح (عندما التفاف على ذلك) استخدام الطرق المؤدية الى احسب المسافات بين نقاط.

http://code.google.com/p/gpsturbo/

ومعظم الوقت كنت لا تريد استخدام خوارزمية يحل مشكلة NP-كاملة / الصلب. كنت ترغب فقط خوارزمية وهذا هو "جيدة بما فيه الكفاية". عادة ما تستند هذه على الاستدلال وإعطاء تقديرات تقريبية معقولة.

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

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

TSP هو مرحبا بالعالم من NP مشاكل كاملة.في شكلها القانوني النقي، لن تجدها في البرية كثيرًا (العروض التوضيحية مثل هذه غير متضمنة)، ولكن هناك مجموعة فرعية ضخمة من مشكلات NP الكاملة مرتبطة أو حتى تعتمد على TSP، مثل:

توجيه السيارة (يشمل توجيه شاحنة الإمداد)
توجيه شركة الطيران/الرحلة
توجيه القطار
توجيه آلة محراث منحدر التزلج

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

ومشاكل قليلة في الحياة الحقيقية تطابق الاشياء كنت تعلم الرياضيات في الصف. يتم تبسيط المشاكل والمستخرجة بحيث يمكنك رؤية الرياضيات ولا يشتت التفاصيل. على سبيل المثال أفضل في الحياة الحقيقية TSPs كبيرة، كما ذكرت، لا تنطوي في الواقع أي بائع السفر: أنها تنطوي على آلات جدولة أن لديهم وظائف لأداء مع <لأ href = "http://books.google.com/books؟ معرف = EkpDak9kEs0C وخريج = PA84 وغاز البترول المسال = PA84 وDQ = آلة + جدولة + تسلسل + الإعداد + يعتمد + ملعقة صغيرة + makespan ومصدر = شبكة الإنترنت ومحطة تكرير النفط = GLaEPtLPrd وسيج = uPg85BQACVRWa0K3B_5pxX04134 "يختلط =" نوفولو noreferrer "> مرات الإعداد التي تعتمد على تسلسل . التي تشمل آلات حيث يتحرك ذراع أداة حول مواقع مختلفة، وأيضا بعض التطبيقات اللوحة (الأحمر-> أورانج> الأصفر هو أسهل من الأحمر-> yellow-> برتقالي). وهناك أيضا بعض التطبيقات في الأشعة السينية البلورات حيث لديك لتوجيه بعض عينة من الكريستال في عدة زوايا مختلفة.

واستند هذه الشركة على تحسين خوارزمية TSP.

http://www.pointserve.com/

وانهم كابل طريق التركيب TV ومصلحي حول NYC بين مشاكل أخرى.

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

ومواقع السفر طيران تستخدم نسخة المتخصصة للمشكلة TSP عندما تظهر لك قائمة من شركات الطيران وأسعار لكل مسار. والفرق هو بدلا من المسافة، وتحسين للتكلفة، وبالتأكيد ليس هناك شرط لزيارة كل مدينة مرة واحدة! يقول كنت تريد أن تطير من LGA إلى LAX. هناك حوالي 1/2 عشرات الطرق المباشرة، وعدد لا حصر له من الطرق الأخرى. قد توحي LGA-> ORD-> LAX أو LGA-> DWF-> LAX. البشر، الذين يمكن يدويا طرق السعر يمكن أن تجد في بعض الأحيان الأسعار أقل من تلك التي بحث عنها من قبل مواقع السفر. عادة، الناس لا يريدون أكثر من اتصالين، ولكن ليس هناك حد أقصى لعدد الاتصالات لرحلة معينة.

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

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

ولن خرائط جوجل (وغيرها من كل خريطة البرمجيات التوجيه القائم) تستخدم نوعا من السفر بائع لحل اتجاهات القيادة؟

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

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow