مسار التكلفة الأقل في صفيف فرز

Question

إعطاء صفيف فرز A على سبيل المثال {4,9,10,11,19}. تكلفة الانتقال من i->j هو abs(A[j]-A[i]). ابدأ من عنصر معين على سبيل المثال 10. اكتشف أقل مسار التكلفة دون زيارة نفس العنصر مرتين. لذلك في هذا المثال سيكون الحل 10->9->4->11->19 بمعنى آخر 1 + 5 + 7 + 8 = 21.

حاولت حل هذا باستخدام أقرب نهج الجار.

 i = start;
 While (array is not empty)
    ldiff = A[i] - A[i-1]
    rdiff = A[i+1] - A[i]
    (ldiff < rdiff) ? sum += ldiff : sum += rdiff
    remove A[i]

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

Answer 1

للحصول على قضيتك على الأقل تكلفة 21 ، انظر

10->9->4->11->19 ==>  1 + 5 + 7 + 8 = 21.

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

A[i]->A[i-1]-> ...->A[1] -> A[i+1] -> A[i+2] -> ...->A[n]  and

A[i]->A[i+1]-> ... ->A[n] ->A[i-1] ->A[i-2] -> ...->A[1]

Answer 2

قم بمعالجة إما العنصر الأصغر أو الأكبر ، اعتمادًا على أنه أقرب (في القيمة ، وليس الفهرس) إلى عنصر البداية ، ثم ببساطة معالجة العناصر المتبقية إلى اليمين أو إلى اليسار (اعتمادًا على ما إذا كنا نعالج أصغر أو أكبر عنصر ).

لذلك ، معطى 4,9,10,11,19 بدءا من 10:

المسافة من 10 إلى أصغر عنصر 4 هو 6 ، المسافة من 10 إلى أكبر عنصر 19 هو 9 ، لذا انتقل إلى 4.

ثم معالجة العناصر المتبقية في ترتيب فرز - 9, 11, 19.

هذا يعطينا 10 -> 4 -> 9 -> 11 -> 19, التي تكاليف 6 + 5 + 2 + 8 = 21.

يمكن القيام بذلك في O(n).

ملحوظة:

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

لهذا 10 -> 9 -> 4 -> 11 -> 19 يعطي أيضا 21.