Guten Abend,
Kurz die Situation vorweg:
Ich muss verschiedene Strings nach ihrer Ähnlichkeit ordnen. Die Strings sind Arbeitsaufträge für eine “Paket-Zusammenstell“- Maschine, die mithilfe von Roboterarmen 4 verschiedene Süßigkeiten zusammensucht und dann ausgibt (als Versuch zur Industrie 4.0).
Ein Arbeitsauftrag wäre also z.b. „AABC“ oder ein anderer „AAAC“. Mehrere von diesen Aufträgen, möchte ich nach ihrer Ähnlichkeit ordnen, damit die Maschine insgesamt schneller arbeitet und sich nicht so oft umstellen muss.
Vom Levenshtein-Algorithmus habe ich schon die Werte der Ähnlichkeit, nur alles einzeln durchzurechnen und jeden Eintrag immer wieder zu überprüfen wird denke ich zu viel Rechenleistung meines Raspberry Pis verbrauchen, zumal das nicht der einzige laufende Prozess sein wird. Es reicht wenn die Liste alle 40 Sekunden aktualisiert wird.
Daher die Frage:
Gibt es eine elegantere und einfachere Möglichkeit, Strings nach ihrer Ähnlichkeit zu ordnen?
Vielen Dank schonmal im Vorraus!
LG fraulilly
Strings nach Ähnlichkeit ordnen
Also wenn du folgende Aufträge hast: ["AABC", "ABCC", "AAAC", "ABBC", "ACAB", "BACA", "CBAA"] sollen die so sortiert werden, dass ['AAAC', 'AABC', 'ABBC', 'ABCC', 'ACAB', 'BACA', 'CBAA'] heraus kommt? Also quasi alphabetisch sortiert? Mir würde es helfen wenn du zeigen würdest wie die Liste vorher aussieht und wie die Liste nachher aussehen soll.
Die Liste ändert sich halt mit jedem "Bestellvorgang" also z.b.
AABC
AAAD
Wenn jetzt eine Bestellung 'AABC' dazu kommt, wäre es effizienter, diese Bestellung vorzuziehen, weil dann die ersten beiden Punkte auf der Liste gleich sind und die Maschine nicht umgestellt werden muss, also so:
AABC
AABC
AAAD
AABC
AAAD
Wenn jetzt eine Bestellung 'AABC' dazu kommt, wäre es effizienter, diese Bestellung vorzuziehen, weil dann die ersten beiden Punkte auf der Liste gleich sind und die Maschine nicht umgestellt werden muss, also so:
AABC
AABC
AAAD
Was ist wenn die Liste vorher
AABC
AAAD
ist und dann
CBAA
bestellt wird?
Wenn die Buchstaben für Zutaten stehen, musst du entscheiden, ob ein Umbau für den Wechsel von AABC auf CBAA nötig ist. Sollte dem nicht so sein, sondern sich nur die Reihenfolge der Zugabe geben, könnte es reichen, die Zutaten in eine einheitliche Reihenfolge für die Sortierung zu bringen und sich die Reihenfolge der Zugabe für die tatsächliche Ausführung zu merken.
AABC
AAAD
ist und dann
CBAA
bestellt wird?
Wenn die Buchstaben für Zutaten stehen, musst du entscheiden, ob ein Umbau für den Wechsel von AABC auf CBAA nötig ist. Sollte dem nicht so sein, sondern sich nur die Reihenfolge der Zugabe geben, könnte es reichen, die Zutaten in eine einheitliche Reihenfolge für die Sortierung zu bringen und sich die Reihenfolge der Zugabe für die tatsächliche Ausführung zu merken.
Zuletzt geändert von sparrow am Freitag 5. Juni 2020, 07:43, insgesamt 1-mal geändert.
Das kommt halt drauf an, wie Du Ähnlichkeit definierst. In Wirklichkeit hast Du ja eine Wegoptimierung einer Queue mit Priorisierung, denn ein Paket darf ja nicht ewig liegen bleiben, nur weil es gerade immer ein bißchen schlechter ist, als das nächstoptimalere.
Also mußt Du erst genau definieren, was Deine Randbedingungen alle sind, und was die Meritfunktion ist, um vom aktuellen auf das nächste Paket zu kommen.
Also mußt Du erst genau definieren, was Deine Randbedingungen alle sind, und was die Meritfunktion ist, um vom aktuellen auf das nächste Paket zu kommen.
Die Reihenfolge spielt tatsächlich keine Rolle, 'AABC' wäre also das gleiche wie 'CBAA'. Im Code kommt also vorher noch was, was das ganze einheitlich macht.
Zum Thema ewig liegen bleiben: Nach einer bestimmten Zeit wird die optimale Lösung ignoriert und lange wartende Pakete einfach direkt nach oben geschoben und dann wird normal weiter die Liste durchgegangen.
Zum Thema ewig liegen bleiben: Nach einer bestimmten Zeit wird die optimale Lösung ignoriert und lange wartende Pakete einfach direkt nach oben geschoben und dann wird normal weiter die Liste durchgegangen.
Bei der Aufgabe scheint es sehr auf die Nebenbedingungen anzukommen. Nehmen wir an, ein Roboterarm bewegt sich sequentiell von einem Produkt zum nächsten und dies soll möglichst ökonomisch erfolgen. Dann ist der Wechsel von z.B. A->A preiswerter als von A->B. D.h. bei einer sequentiellen Bearbeitung wäre es günstig, wenn das letzte Element einer Sequenz dem ersten Element der Nachfolgesequenz entspricht: AACB -> BCAC -> CBBA usw. Die Sequenzen könnte man dann auch noch in sich optimieren, sofern das für das Produkt unerheblich ist, z.B.: BCAC -> BACC
Erfolgt die Abarbeitung aber parallel durch vier Roboterarme gleichzeitig (übrigens ein typisches Szenario aus der Verpackungsindustrie), dann wäre es sinnvoll, wenn die einzelnen Positionen innerhalb einer Sequenz möglichst wenig von den entsprechenden Positionen der Nachfolgesequenz abweichen. In der konkreten Übung könnte man als Ansatz nehmen, erst einmal die Summe der ascii-Werte der einzelnen Sequenzen zu betrachten und die Sequenzen dann so sortieren, dass die Summe der Differenzen aufeinanderfolgender Sequenzen minimiert wird. Eine rein alphabetische Sortierung der Sequenzen sollte in diesem Beispiel dafür schon ausreichen.
In der Praxis könnte man so etwas in Chargen machen, die in sich optimiert werden, so dass kein Auftrag zu lange warten muss.
Erfolgt die Abarbeitung aber parallel durch vier Roboterarme gleichzeitig (übrigens ein typisches Szenario aus der Verpackungsindustrie), dann wäre es sinnvoll, wenn die einzelnen Positionen innerhalb einer Sequenz möglichst wenig von den entsprechenden Positionen der Nachfolgesequenz abweichen. In der konkreten Übung könnte man als Ansatz nehmen, erst einmal die Summe der ascii-Werte der einzelnen Sequenzen zu betrachten und die Sequenzen dann so sortieren, dass die Summe der Differenzen aufeinanderfolgender Sequenzen minimiert wird. Eine rein alphabetische Sortierung der Sequenzen sollte in diesem Beispiel dafür schon ausreichen.
In der Praxis könnte man so etwas in Chargen machen, die in sich optimiert werden, so dass kein Auftrag zu lange warten muss.
Nebenbemerkung dazu: Zeichenketten-Distanzmaße wie die Levenshtein-Distanz oder der Hammingabstand (eignet sich für gleichlange Zeichenketten) sind, wie die anderen schon meinten, hier nicht das Mittel der Wahl. Zu deinen Sorgen was die Performance angeht ist aber zu sagen, dass man halt nicht auf die Idee kommen sollte, den klassischen Dynamic-Programming-Algorithmus für die Levenshtein-Distanz in reinem Python nachzuprogrammieren. Es gibt diverse optimierte Variante davon (oder auch Abwandlungen wie Levenshtein-Automaten für bestimmte sehr spezielle Anwendungszwecke), die man sich, wenn man über einen produktiven Einsatz nachdenkt, ansehen sollte. Aber ich denke, wie gesagt, dass du etwas anderes benötigst.fraulilly hat geschrieben: ↑Donnerstag 4. Juni 2020, 22:32 Vom Levenshtein-Algorithmus habe ich schon die Werte der Ähnlichkeit, nur alles einzeln durchzurechnen und jeden Eintrag immer wieder zu überprüfen wird denke ich zu viel Rechenleistung meines Raspberry Pis verbrauchen, zumal das nicht der einzige laufende Prozess sein wird.
Ja, die Produkte werden mit mehreren Roboterarmen geholt. Für den Anfang werde ich die alphabetische Sortierung nehmen und das mit den Chargen werde ich mir auch angucken.kbr hat geschrieben: ↑Freitag 5. Juni 2020, 09:48 Bei der Aufgabe scheint es sehr auf die Nebenbedingungen anzukommen. Nehmen wir an, ein Roboterarm bewegt sich sequentiell von einem Produkt zum nächsten und dies soll möglichst ökonomisch erfolgen. Dann ist der Wechsel von z.B. A->A preiswerter als von A->B. D.h. bei einer sequentiellen Bearbeitung wäre es günstig, wenn das letzte Element einer Sequenz dem ersten Element der Nachfolgesequenz entspricht: AACB -> BCAC -> CBBA usw. Die Sequenzen könnte man dann auch noch in sich optimieren, sofern das für das Produkt unerheblich ist, z.B.: BCAC -> BACC
Erfolgt die Abarbeitung aber parallel durch vier Roboterarme gleichzeitig (übrigens ein typisches Szenario aus der Verpackungsindustrie), dann wäre es sinnvoll, wenn die einzelnen Positionen innerhalb einer Sequenz möglichst wenig von den entsprechenden Positionen der Nachfolgesequenz abweichen. In der konkreten Übung könnte man als Ansatz nehmen, erst einmal die Summe der ascii-Werte der einzelnen Sequenzen zu betrachten und die Sequenzen dann so sortieren, dass die Summe der Differenzen aufeinanderfolgender Sequenzen minimiert wird. Eine rein alphabetische Sortierung der Sequenzen sollte in diesem Beispiel dafür schon ausreichen.
In der Praxis könnte man so etwas in Chargen machen, die in sich optimiert werden, so dass kein Auftrag zu lange warten muss.
Danke für deine Hilfe!
Habe ich im Laufe der Unterhaltung auch gemerkt, dass ich was anderes suchenezzcarth hat geschrieben: ↑Freitag 5. Juni 2020, 11:27Nebenbemerkung dazu: Zeichenketten-Distanzmaße wie die Levenshtein-Distanz oder der Hammingabstand (eignet sich für gleichlange Zeichenketten) sind, wie die anderen schon meinten, hier nicht das Mittel der Wahl. Zu deinen Sorgen was die Performance angeht ist aber zu sagen, dass man halt nicht auf die Idee kommen sollte, den klassischen Dynamic-Programming-Algorithmus für die Levenshtein-Distanz in reinem Python nachzuprogrammieren. Es gibt diverse optimierte Variante davon (oder auch Abwandlungen wie Levenshtein-Automaten für bestimmte sehr spezielle Anwendungszwecke), die man sich, wenn man über einen produktiven Einsatz nachdenkt, ansehen sollte. Aber ich denke, wie gesagt, dass du etwas anderes benötigst.fraulilly hat geschrieben: ↑Donnerstag 4. Juni 2020, 22:32 Vom Levenshtein-Algorithmus habe ich schon die Werte der Ähnlichkeit, nur alles einzeln durchzurechnen und jeden Eintrag immer wieder zu überprüfen wird denke ich zu viel Rechenleistung meines Raspberry Pis verbrauchen, zumal das nicht der einzige laufende Prozess sein wird.
Bin noch relativ neu hier und das war nunmal das erste was mir eingefallen ist, aber ich hab jetzt ja genug neue Ideen. Danke nochmals an euch alle