تقليل وظيفة في وحدات متجاورة من مجموعة

Question

ولدي مجموعة (arr) من العناصر، وظيفة (f) التي تأخذ 2 عناصر وإرجاع الرقم.

وانا بحاجة الى التقليب من مجموعة، بحيث f(arr[i], arr[i+1]) هو أقل قدر ممكن لكل i في arr. (وأنه ينبغي حلقة، أي. ينبغي أيضا تقليل f(arr[arr.length - 1], arr[0]))

وأيضا، f يعمل نوع من مثل المسافة، لذلك f(a,b) == f(b,a)

وأنا لست بحاجة إلى الحل الأمثل لو كان غير فعال جدا، ولكن واحدة أن يعمل بشكل جيد معقول وسريع منذ أن كنت بحاجة لحساب لهم الى حد كبير في الوقت الحقيقي (وأنا لا أعرف ما هو طول arr، لكنني أعتقد أنه يمكن أن يكون شيئا حول 30)

Answer 1

وماذا تعني عبارة "مثل أن f (آر [أنا]، وصول [ط + 1]) هو أقل قدر ممكن لكل ط في آر" يعني؟ هل تريد تقليل <م> المبلغ ؟ هل ترغب في تقليل أكبر من تلك؟ هل ترغب في تقليل و (آر [0]، آر [1]) أولا، ثم بين كل الحلول التي تقلل من ذلك، اختيار واحد ان يقلل و (آر [1]، آر [2]) وغيرها، وذلك على؟

إذا كنت ترغب في تقليل <م> المبلغ ، وهذا هو بالضبط بائع مشكلة السفر في عموميته كاملة (حسنا، "TSP متري"، ربما، إذا و لديك بالفعل تشكيل متري). هناك تحسينات ذكية في حل ساذج من شأنها أن تعطيك بالضبط الأمثل وتشغيل في وقت معقول لمدة ن = 30؛ هل يمكن استخدام واحدة من تلك، أو واحد من الاستدلال التي تعطيك تقريبية.

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

إذا كنت تريد تصغيره <م> lexiocographically ، انها تافهة: اختيار الزوج أقصر مسافة ووضعها كما آر [0]، آر [1]، ثم اختيار آر [ 2] وهذا هو الأقرب إلى ARR [1]، وهلم جرا.

واعتمادا على المكان الخاص بك و (،) الصورة تأتي من، وهذا قد يكون مشكلة أسهل بكثير من TSP. سيكون من المفيد لك أن أذكر ذلك أيضا.

Answer 2

وأنت ليس من الواضح تماما ما كنت الأمثل - مجموع و (أ [ط]، وهو [ط + 1]) القيم والحد الأقصى منها، أو أي شيء آخر

في أي حال، مع قيود السرعة الخاصة بك، والجشع هو على الارجح أفضل رهان - اختيار عنصر لجعل [0] (لا يهم الذي يرجع إلى ملفوف)، ثم اختيار كل عنصر على التوالي ل[ط + 1] لتكون واحدة أن يقلل و (أ [ط]، وهو [ط + 1]).

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

Answer 3

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

ودعونا بدلا من ذلك تحديد ن fcns g_i: التجاعيد -> الريالات

g_i(p) = f(a^p[i], a^p[i+1]), and wrap around when i+1 > n

لنفرض أنك تريد تقليل <م> و على كل التباديل يعني حقا يمكنك اختيار قيمة <م> أنا وتقليل <م> g_i على كل التباديل، ولكن لأي ص مما يقلل <م> g_i ، وهي ذات صلة ولكن مختلفة يقلل permatation <م> g_j (فقط تصريف التقليب). وبالتالي فإنه لا معنى للحديث التقليل و على التباديل لكل <م> <ط / م>.

Answer 4

وإذا لم نعرف شيئا أكثر عن هيكل و (س، ص) وهذا هو مشكلة NP-الصعبة. بالنظر إلى الرسم البياني G وأي القمم س، ص السماح و (س، ص) أن يكون 1 إذا لم يكن هناك حافة و 0 إذا كان هناك على الحافة. ما يسأل المشكلة هو ترتيب القمم بحيث القصوى و (آر [أنا]، وصول [ط + 1]) تم تصغير قيمة. منذ لهذه المهمة يمكن أن يكون فقط 0 أو 1، والعودة بنتيجة 0 ما يعادل إيجاد مسار هاميلتون في G و 1 يقول أن أي مسار من هذا القبيل موجودا.

وسيكون على وظيفة أن يكون نوعا من الهيكل الذي يرفض هذا المثال ليكون لين العريكة.