Gegeben sind zwei Sätze von dreidimensionalen Punkten, eine Quelle und eine Zielmenge. Die Anzahl der Punkte in jedem Satz ist beliebig (kann Null sein). Die Aufgabe besteht darin, jedem Zielpunkt einen oder keinen Quellpunkt zuzuweisen, so dass die Summe aller Entfernungen minimal ist. Wenn es mehr Quell- als Zielpunkte gibt, werden die zusätzlichen Punkte ignoriert.
Es gibt eine Brute-Force-Lösung für dieses Problem, aber da die Anzahl der Punkte groß sein kann, ist es nicht machbar. Ich habe gehört, dass dieses Problem in 2D mit gleichen Größenordnungen einfach ist, aber leider sind diese Voraussetzungen hier nicht gegeben.
Ich bin an Annäherungen und genauen Lösungen interessiert.
Edit: Haha, ja, ich nehme an, es hört sich nach Hausaufgaben an. Eigentlich ist es nicht. Ich schreibe ein Programm, das Positionen von einer großen Anzahl von Autos erhält, und ich versuche, sie ihren jeweiligen Parkzellen zuzuordnen. :)
Von meinem Kopf weg, räumliche Sortierung gefolgt von simulierter Ausheilung.
Gitter den Raum & Amp; sortiere die Sätze in räumliche Zellen.
Löse das O (NM) -Problem innerhalb jeder Zelle, dann innerhalb von Zellennachbarschaften und so weiter, um eine Testübereinstimmung zu erhalten.
Führen Sie abschließend viele Simulationsglühzyklen durch, in denen Sie die Treffer zufällig ändern, um den nahegelegenen Raum zu erkunden.
Dies ist eine Heuristik, die Ihnen eine gute Antwort liefert, aber nicht unbedingt die beste, und sie sollte aufgrund der anfänglichen Gittersortierung ziemlich effizient sein.
Eine Möglichkeit, wie Sie dieses Problem angehen könnten, ist die Behandlung als klassisches Aufgabe-Problem: Ссылка
Sie behandeln die Punkte als die Scheitelpunkte des Graphen, und die Gewichte der Kanten sind die Entfernung zwischen den Punkten. Da die schnellsten Algorithmen davon ausgehen, dass Sie nach maximalem Matching suchen (und nicht nach Minimum wie in Ihrem Fall) und dass die Gewichte nicht negativ sind, können Sie Gewichte neu definieren, z. B .:
%Vor% Dabei ist bigNumber größer als Ihre längste Entfernung.
Offensichtlich haben Sie einen zweiteiligen Graphen. Dann verwenden Sie einen der Standardalgorithmen für den maximalen gewichteten zweiteiligen Matching (viele Ressourcen im Web, zB Ссылка oder Wikipedia für die Übersicht: Ссылка ) Auf diese Weise werden Sie am Ende landen mit einem O (NM max (N, M)) - Algorithmus, wobei N und M die Größe Ihrer Punkte sind.
Obwohl ich keine Antwort auf Ihre Frage habe, kann ich vorschlagen, die folgenden Themen zu untersuchen. (Ich weiß sehr wenig darüber, aber ich habe es vorher auf Stack Overflow gesehen.)
Hoffe, das hilft ein bisschen.
Gegeben sind zwei Sätze von dreidimensionalen Punkten, eine Quelle und eine Zielmenge. Die Anzahl der Punkte in jedem Satz ist beliebig (kann Null sein). Die Aufgabe besteht darin, jedem Zielpunkt einen oder keinen Quellpunkt zuzuweisen, so dass die Summe aller Entfernungen minimal ist. Wenn es mehr Quell- als Zielpunkte gibt, werden die zusätzlichen Punkte ignoriert.
Es gibt eine Brute-Force-Lösung für dieses Problem, aber da die Anzahl der Punkte groß sein kann, ist es nicht machbar. Ich habe gehört, dass dieses Problem in 2D mit gleichen Größenordnungen einfach ist, aber leider sind diese Voraussetzungen hier nicht gegeben.
Ich bin an Annäherungen und genauen Lösungen interessiert.
Edit: Haha, ja, ich nehme an, es hört sich nach Hausaufgaben an. Eigentlich ist es nicht. Ich schreibe ein Programm, das Positionen von einer großen Anzahl von Autos erhält, und ich versuche, sie ihren jeweiligen Parkzellen zuzuordnen. :)
Von meinem Kopf weg, räumliche Sortierung gefolgt von simulierter Ausheilung.
Gitter den Raum & Amp; sortiere die Sätze in räumliche Zellen.
Löse das O (NM) -Problem innerhalb jeder Zelle, dann innerhalb von Zellennachbarschaften und so weiter, um eine Testübereinstimmung zu erhalten.
Führen Sie abschließend viele Simulationsglühzyklen durch, in denen Sie die Treffer zufällig ändern, um den nahegelegenen Raum zu erkunden.
Dies ist eine Heuristik, die Ihnen eine gute Antwort liefert, aber nicht unbedingt die beste, und sie sollte aufgrund der anfänglichen Gittersortierung ziemlich effizient sein.
Eine Möglichkeit, wie Sie dieses Problem angehen könnten, ist die Behandlung als klassisches Aufgabe-Problem: Ссылка
Sie behandeln die Punkte als die Scheitelpunkte des Graphen, und die Gewichte der Kanten sind die Entfernung zwischen den Punkten. Da die schnellsten Algorithmen davon ausgehen, dass Sie nach maximalem Matching suchen (und nicht nach Minimum wie in Ihrem Fall) und dass die Gewichte nicht negativ sind, können Sie Gewichte neu definieren, z. B .:
%Vor%Dabei ist %code% größer als Ihre längste Entfernung.
Offensichtlich haben Sie einen zweiteiligen Graphen. Dann verwenden Sie einen der Standardalgorithmen für den maximalen gewichteten zweiteiligen Matching (viele Ressourcen im Web, zB Ссылка oder Wikipedia für die Übersicht: Ссылка ) Auf diese Weise werden Sie am Ende landen mit einem O (NM max (N, M)) - Algorithmus, wobei N und M die Größe Ihrer Punkte sind.
Tags und Links algorithm math mapping mathematical-optimization