Welche Zuweisungsmethode passt zu meinem Fall?

Question

Ich habe eine große Reihe von Geräten mit jeweils zwei spezifischen Parametern. Innerhalb dieses Sets möchte ich Geräte mit möglichst ähnlichen Geräten erstellen. Dies wird durch eine euklidische Norm erfolgen. Aber ich bin mir nicht sicher, welches Zuordnungsproblem bzw. welche Methode dafür zu meinem Fall passt. Soweit ich darauf eingehe bin ich auf der Suche nach einem maximalen Matching, nicht perfekt oder maximal passend. So sind zwei Aspekte wichtig:

• Die Menge der erzeugten Paare so hoch wie möglich ist.
• Die Geräte der Paare selbst überschreiten eine bestimmte Toleranzgrenze nicht (dies ist kein Problem, da dies bereits durch Definition eines Kreises geschehen ist).

Zuerst wollte ich https://www.topcoder.com/community/data-science/data-science-tutorials/assignment-problem-and-hungarian-algorithm/# verwenden! um es zu realisieren, aber ich bin mir nicht sicher, ob das das Problem löst. Ich bin auf dem folgenden fest: Der ungarische Algorithmus basiert auf bipartite Graphen und diese verwenden zwei disjunkte Sätze. Aber ich habe nur einen Satz. Also muss ich Zuweisungen innerhalb dieses einen Satzes erstellen (obwohl der Algorithmus Elementen eines Satzes Elemente eines anderen Satzes zuweist), aber ich bin mir nicht sicher, ob dies machbar ist.

Meine Frage ist: Funktioniert das trotzdem? Oder welche Methode soll ich verwenden?

Answer 1

Sie können „Anpassen“ die ungarische Methode, um Ihren Fall auf folgende Weise:

1- Verwenden Sie die gleiche Menge (die Menge der Geräte) für die Zeilen (Ressourcen) und Spalten (Aufgaben).

2- Use „big M“ zu vermeiden, eine Vorrichtung zu sich selbst zuweisen: set Diagonalelemente bis zu einem gewissen großen Wert

3- Bei jedem Eintrag (i, j) der Kostenmatrix eine Kosten zuordnen, die einige widerspiegelt Maß der Unähnlichkeit

4- Run die ungarische Methode

5- wenn schließlich die Zuordnung vorgenommen wird, nehmen nur die Paare, die die Toleranzgrenze überschreiten (in anderen Worten nicht wirklich, die Paare entfernen, wie sie Kosten Sie die große Zahl oder Kosten, die Ihre "Toleranzgrenze überschreiten".