تحتاج أفضل خوارزمية إيجاد رسم الخرائط بين 2 مجموعات من النقاط مع الحد الأدنى من المسافة

Question

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

القوة الغاشمة: القوة الغاشمة نهج لحل هذه المشكلة ومن الواضح من السؤال منذ كنت لحساب المسافة الإجمالية من تعيينات الذي أعتقد أن هناك n!(حيث n هو عدد غير متداخلة بكسل في شكل واحد) مرات حساب من حساب المسافة لكل زوج من نقاط في رسم الخرائط ، ن ، وإعطاء ما مجموعه O( n * n!) أو شيئا من هذا القبيل.

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

هل هناك أي طريقة لحل هذه المشكلة معقولة التعقيد ؟

نلاحظ أيضا أن "واضحة" نهج ببساطة تعيين نقطة إلى أقرب مطابقة الجار لا تسفر دائما الحل الأمثل.

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

أي الأفكار هي موضع تقدير!!

Answer 1

هذا هو الحد الأدنى مطابقة المشكلة هو الصحيح أنه من الصعب المشكلة في العامة.ومع ذلك من أجل 2D الإقليدية مشطور الحد الأدنى مطابقة الحالة قابلة للحل في وثيقة O(n2) (انظر الرابط).

بسرعة تقريبية ، FryGuy على المسار الصحيح مع محاكاة التلدين.هذا هو نهج واحد.

أيضا أن تأخذ نظرة على تقريب خوارزميات ثنائية أو غير ثنائية مطابقة في الطائرة ل ا((ن/ه)^1.5*سجل^5(ن)) (1+ه)-العشوائية مخطط تقريبي.

Answer 2

كنت قد تنظر في محاكاة التلدين من أجل هذا.تبدأ من خلال تعيين[x] -> ب[y] لكل بكسل ، عشوائيا ، وحساب مجموع تربيع المسافات.ثم مبادلة زوج x<->ذ تعيينات بشكل عشوائي.ثم اختيار لقبول هذا مع احتمال Q حيث Q هو أعلى إذا كان رسم الخرائط الجديدة هو أفضل ، و يميل نحو الصفر مع مرور الوقت.انظر مقالة ويكيبيديا عن تفسير أفضل.

Answer 3

1. نوع بكسل في الشكل:من أجل زيادة 'x' ثم 'y' تنسق
2. نوع بكسل في الشكل ب:في خفض ترتيب 'x' ثم زيادة 'y'

خريطة بكسل في نفس الفهرس:في فرز قائمة أول بكسل في الخريطة الأولى بكسل في B.هذا رسم الخرائط تبحث عنه ؟