ما أخبث طريقة تشكل هذه المشكلة ؟

https://stackoverflow.com/questions/643594

22-07-2019
|

سؤال

بلدي أفضل فرصة حتى الآن:

تسليم السيارة يحتاج إلى إجراء سلسلة من عمليات التسليم (د₁d₂, د..._n), و يمكن القيام بذلك في أي أمر-أو بعبارة أخرى ، كل التباديل الممكنة من مجموعة د = {د₁d₂, د..._n} صالحة حلول ولكن الحل خاصة يجب أن تحدد قبل أن يغادر المحطة الأساسية في واحدة من نهاية الطريق (تخيل أن الحزم تحتاج إلى تحميلها في السيارة LIFO ، على سبيل المثال).

كذلك تكلفة التباديل المختلفة ليس هو نفسه.ويمكن أن يحسب مجموع المربعات من سافر المسافة بين d_{أنا -1} و د_أنا, حيث d₀ هو أن تكون قاعدة محطة, مع التحذير من أن أي الجزء الذي ينطوي على تغيير الاتجاه التكاليف 3 أضعاف (تخيل أن هذا يحدث على السكك الحديدية أو هوائي أنبوب, والنسخ الاحتياطي يعطل حركة المرور الأخرى).

بالنظر إلى مجموعة من الولادات D ممثلة المسافة من محطة قاعدة (إذا abs(d_أنا-d_ي) هي المسافة بين الشحنتين) و مكرر permutations(D) والتي سوف تنتج كل التقليب في الخلافة ، تجد التقليب التكلفة أقل من أو يساوي ذلك من أي التقليب.

الآن التنفيذ المباشر من هذا الوصف قد يؤدي إلى رمز مثل هذا:

function Cost(D) ...

function Best_order(D)
    for D1 in permutations(D)
        Found = true
        for D2 in permutations(D)
            Found = false if cost(D2) > cost(D1)
        return D1 if Found

التي O(n*n!^2) مثلافظيعة جدا--لا سيما بالمقارنة مع O(n log(n)) شخص مع فكرة أن تجد ببساطة عن طريق الفرز D.

سؤالي:يمكنك الخروج مع المعقول وصف المشكلة التي سوف يؤدي بطبيعة الحال غافلين في أسوأ (أو بطريقة فظيعة) تنفيذ خوارزمية الفرز?

المحلول

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

[هذا الافتراض غير صحيح - MarkusQ]

وأنت تعطي الكثير من المعلومات.

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

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

وأود أن إزالة عقوبة لتغيير الاتجاهات، فإنه من الكثير من العطاء بعيدا.

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

وأود أن العبارة على النحو التالي:
<اقتباس فقرة>
وبالنظر إلى قائمة بجميع ممكن   التباديل من المواقع تسليم ن،   حيث كل التقليب من الولادات   (د <الفرعية> 1 ، د <الفرعية> 2 ، ...،   د <الفرعية> ن ) لديه التكلفة التي تحددها:



عودة التقليب P بحيث   تكلفة P أقل من أو تساوي أي   التقليب آخرين.

وكل ما يحتاج حقا إلى أن يتم قراءة في التقليب الأول وترتيب هذا الامر.

إذا كانت بناء حلقة واحدة لمقارنة التكاليف نطلب منهم ما هو كبير س وقت من خوارزمية حيث n هو عدد من المواقع تسليم (فخ آخر).

نصائح أخرى

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

هل د <الفرعية> <ط / الفرعية> السماح للسلبية؟ إذا كان الأمر كذلك، والفرز وحده لا يكفي، بقدر ما أستطيع أن أرى.

وعلى سبيل المثال:

وd <الفرعية> 0 = 0

وdeliveries = (-1,1,1,2)

ويبدو أن الطريق الأمثل في هذه الحالة أن 1 > 2 > 1 > -1.

وتحرير: وهذا قد لا يكون في الواقع الطريق الأمثل، لكنه يوضح هذه النقطة

هل يمكن صياغتها، وبعد أول جدت الحل الأمثل، و

و"أعطني دليلا على أن convination التالية هو الأكثر الأمثل للمجموعة التالية من القواعد، حيث يعني الأمثل أصغر نتائج عدد من مجموع كل التكاليف المرحلة، مع الأخذ بعين الاعتبار أن (A..Z) جميع مراحل تحتاج إلى أن تكون موجودة مرة واحدة ومرة واحدة فقط.

وConvination:

A->C->D->Y->P->...->N

وتكاليف المرحلة:

A->B = 5, B->A = 3, A->C = 2, C->A = 4, ... ... ... Y->Z = 7, Z->Y = 24."

وهذا يجب أن تبقي شخص مشغول لفترة من الوقت.

هذا يذكرني حقيبة المشكلة, أكثر من بائع السفر.ولكن حقيبة أيضا NP-Hard المشكلة, لذلك قد تكون قادرة على خداع الناس إلى التفكير أكثر تعقيدا الحل باستخدام البرمجة الديناميكية إذا كانت ترتبط مشكلتك مع حقيبة.حيث إن المشكلة الأساسية هي:

أن قيمة على الأقل V يتحقق دون تجاوز الوزن W?

المشكلة الآن هي جيدة إلى حد ما الحل يمكن العثور عليه عندما الخامس فريدة من نوعها ، المسافات ، على هذا النحو:

حقيبة المشكلة مع كل نوع من البند ي وجود قيمة متميزة في وحدة الوزن (vj = pj/wj) ، تعتبر واحدة من أسهل NP-complete المشاكل.في الواقع التجريبي التعقيد هو من أجل من يا((سجل ن)2) و المشاكل كبيرة جدا يمكن حلها بسرعة جدا, على سبيل المثالفي عام 2003 متوسط الوقت اللازم لحل الحالات مع n = 10,000 أقل من 14 ميلي ثانية باستخدام السلع الشخصية أجهزة الكمبيوتر1.

لذلك قد ترغب الدولة أن عدة محطات/حزم قد تشترك في نفس vj, دعوة الناس إلى التفكير بجد الحل:

ومع ذلك في تتدهور حالة من عناصر متعددة تقاسم نفس القيمة vj يصبح أكثر صعوبة بالغة حالة vj = مستمرة كونها فرعية مبلغ مشكلة مع تعقيد O(2N/2N).

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

وليس هذا فقط (NP-الصلب) مسألة البائع المتجول ؟ لا يبدو من المرجح أن كنت تريد الذهاب لجعل الأمر أكثر صعوبة بكثير.

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

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

وراجع للشغل، ما هو الغرض من هذا - هذا يبدو وكأنه القصد من ذلك هو تعذيب مقابلتهم.

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

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

كم هو عظيم حكمة الحكماء ، إذا كانت تصغي لا الأنا الأكاذيب ؟

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

لا تنتمي إلى StackOverflow