تعيين مجموعة من النقاط ثلاثية الأبعاد لمجموعة أخرى مع الحد الأدنى من المسافات

Question

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

يوجد حل قوي لهذه المشكلة، لكن نظرًا لأن عدد النقاط قد يكون كبيرًا، فهو غير ممكن.سمعت أن هذه المشكلة سهلة في الوضع ثنائي الأبعاد بأحجام متساوية، لكن للأسف لم يتم توفير هذه الشروط المسبقة هنا.

أنا مهتم بكل من التقديرات التقريبية والحلول الدقيقة.

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

Answer 1

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

والشبكة الفضاء وفرز مجموعات إلى خلايا المكانية.

وحل O (NM) مشكلة داخل كل خلية، ثم داخل الأحياء الخلية، وهلم جرا، للحصول على مطابقة المحاكمة.

وأخيرا، قم بتشغيل الكثير من دورات محاكاة الصلب، والتي يمكنك تغيير عشوائيا المباريات، وذلك لاستكشاف الفضاء القريب.

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

Answer 2

واحدة الطريقة التي يمكن التعامل مع هذه المشكلة لعلاج كما هو المشكلة المهمة الكلاسيكية: HTTP: // en.wikipedia.org/wiki/Assignment_problem

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

weight(A, B) = bigNumber- distance(A,B)

وحيث bigNumber هو أكبر من أطول مسافة الخاص بك.

ومن الواضح أن ينتهي بك الأمر مع رسم بياني ثنائي. ثم يمكنك استخدام واحدة من خوارزميات القياسية لأكبر قدر من مطابقة ثنائي المرجح (الكثير من الموارد على شبكة الإنترنت، على سبيل المثال <لأ href = "http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/ 27_matchings_notes.pdf "يختلط =" نوفولو noreferrer "> http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/27_matchings_notes.pdf أو ويكيبيديا لمحة عامة: <أ href = ل "http://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings" يختلط = "noreferrer نوفولو"> http://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings ) وبهذه الطريقة سوف النهائيين حتى مع O (NM ماكس (N، M)) algoritms، حيث N و M هي أحجام مجموعات بك من النقاط.

Answer 3

على الرغم من أنني لا أملك إجابة حقيقية لسؤالك، إلا أنني أستطيع أن أقترح النظر في المواضيع التالية.(لا أعرف سوى القليل جدًا عن هذا الأمر، لكنني واجهته سابقًا في Stack Overflow.)

• أقرب بحث الجار
• كد-شجرة

آمل أن يساعد هذا قليلا.