Minimale Anzahl an Operationen herausfinden

[Orolhawion]

Hallo zusammen,

ich hätte folgende Frage an die Mathematiker unter Euch:

Ich habe zwei Listen, eine Ursprungsliste und eine veränderte Ursprungsliste. Veränderungen können sein:
INSERT (neue Elemente sind hinzugekommen)
REMOVE (Elemente sind von der Liste gelöscht worden)
MOVE (ein Element wird von Stelle x an Stelle y verschoben)
SWITCH (Element a tauscht mit Element b die Plätze)

Jetzt würde ich gerne die minimale Anzahl an Operationen ermitteln. Damit möchte ich dann die Ursprungsliste so manipulieren, dass die veränderte Ursprungsliste am Ende entsteht.

Meine Frage ist nun die nach der Ausführungsreihenfolge der Operationen: Ich habe bisher zuerst die REMOVEs ausgeführt, dann die MOVES und SWITCHES (natürlich unter Berücksichtigung der noch kommenden INSERTS) und zum Schluss die INSERTS. Würde die Ausführungsreihenfolge überhaupt etwas an der Anzahl der benötigten Operationen verändern und wenn ja, welche Reihenfolge ist die, die letzendlich die kleinste Menge an Operationen benötigt?

 

[SlaterB]

mindestens einer der Befehle, MOVE, ist doch stark vom exakten Zustand der Liste zuvor abhängig,
wenn von Index 3 auf Index 10 verschoben werden soll und die anderen Befehle unter anderem das Entfernen der Elemente 7 und 8 beinhalten,
dann kann man diese Befehle doch alle nicht beliebig vertauschen, sonst ist das Element an Index 3 später weiter vorne oder weiter hinten in der Liste

-----

ist jeder Schritt für sich genau eine Operation, sehe ich (edit: es fehlte: keine) Änderung der Anzahl an Operationen,

geht es dagegen um den realen Arbeitsaufwand, kann es sparsam sein, erst die removes auszuführen, um die Liste kleiner zu machen,
was in einer ArrayList weniger Umherkopieren bedeutet,

noch schlauer wäre vielleicht, falls es ursprünglich überhaupt eine ArrayList war, einmalig alles in eine LinkedList zu überführen,
das macht REMOVE deutlicher performanter, SWITCH dagegen wird eher erschwert, hmm..,
na um solche 'Operationen' gehts vielleicht gar nicht, dann eh egal

------

wenn man extrem mathematisch arbeitet, kann man vielleicht wirklich direkt Operationen sparen,
INSERT A, REMOVE A wird zu NIX
REMOVE A, REMOVE B, INSERT A, INSERT B wird zu SWITCH A, B je nach Position usw.,
aber das wäre ja extremer Untersuchungsaufwand, und lohnt sich vielleicht erst bei mehr Änderungen als es überhaupt Listenplätze und unterschiedliche Elemente gibt

 

[Marco13]

Ja, ein paar mehr Informationen über die Randbedingungen wären hilfreich (d.h. inwieweit die Reihenfolge der Operationen eine Rolle spielt).

Theoretisch ist das ganz einfach: Der Ursprüngliche Zustand ist ein Knoten eines Graphen. Dann wendet man auf diesen Zustand ALLE möglichen Operationen an, und erzeugt damit Folgezuständen (also Nachbarknoten im Graphen). Auf alle diese Folgezustände wendet man jeweils wieder alle Operationen an. Das entspricht einer Breitensuche. Wenn man einen Zustand erreicht, der dem gewünschten Endzustand entspricht, hat man die minimale Operationsfolge gefunden. In der Praxis wäre das aber kaum praktikabel, je nachdem, wie groß die Listen sind, und welchen Aufwand man dafür betreiben will.

 

[Orolhawion]

Ja, ein paar mehr Informationen über die Randbedingungen wären hilfreich (d.h. inwieweit die Reihenfolge der Operationen eine Rolle spielt).

nun, das möchte ich ja gerne von euch wissen. zusätzliche informationen wären, dass alle objekte auf der ursprungsliste unterschiedlich sind, d.h. es gibt keine doppelten elemente auf der ursprungsliste (und auch nicht auf der veränderten ursprungsliste). bisher mache ich es folgendermaßen:

1. ermitteln der REMOVEs
2. Ausführen der REMOVEs
3. ermitteln der INSERTs
4. ermitteln der MOVEs/SWITCHes (unter berücksichtigung der bereits bekannten INSERTs)
5. Ausführen der MOVEs/SWITCHes
6. Ausführen der INSERTS (was letztendlich dafür sorgt, dass die MOVEd/SWITCHed elemente hinterher an der richtigen stelle stehen).

die frage ist nun: benötige ich z.b. bei folgender reihenfolge weniger operationen?

1. ermitteln der REMOVEs
2. ausführen der REMOVEs
3. ermitteln der INSERTs
4. ausführen der INSERTs
5. ermitteln der MOVEs/SWITCHes
6. ausführen der MOVEs/SWITCHes

 

[SlaterB]

was ist eine Operation?
was läßt dich auf dieser Welt vermuten, dass die Anzahl der Operationen variabel ist, verringert werden kann?

wenn man 5 Autos kaufen muss und 3 Tomaten, dann muss man 8x in die Stadt laufen,
aus welchem hier noch nicht genannten Grund könnte die Reihenfolge irgendeine Art von Auswirkung darauf haben?


------

worin unterscheidet sich
> 4. ermitteln der MOVEs/SWITCHes (unter berücksichtigung der bereits bekannten INSERTs)
von
> 4. ausführen der INSERTs
> 5. ermitteln der MOVEs/SWITCHes

was exakt gibt es da zu ermitteln, wie wirkt sich das ganz konkret konkret konkret aus?
Beispiele helfen vielleicht wie überall und immer

 

[Gonzo17]

Ohne jetzt einen genauen Lösungsansatz zu haben. Schreib es doch einfach als Code auf. Mach eine Klasse, die deine Liste bzw veränderte Liste darstellt, mach die Befehle und zähle die Befehle mit. Dann kannst du dir ein paar Testfälle machen, implementierst verschiedene Algorithmen und lässt sie mit den Testfällen durchlaufen. Dann siehst du ja, wieviele Schritte welcher Lösungsansatz braucht.

 

[Orolhawion]

was ist eine Operation?
was läßt dich auf dieser Welt vermuten, dass die Anzahl der Operationen variabel ist, verringert werden kann?

I Ursprungsliste: e,a,b,c,d
II veränderte Ursprungsliste: a,b,c,d,e

du kommst von I nach II entweder mit:
1. SWITCH(0,1)
2. SWITCH(1,2)
3. SWITCH(2,3)
4. SWITCH(3,4)

das entspricht vier operationen.

oder du kommst von I nach II mit:
1. MOVE(0,4)

das entspricht einer operation, also deutlich weniger.

worin unterscheidet sich
> 4. ermitteln der MOVEs/SWITCHes (unter berücksichtigung der bereits bekannten INSERTs)

die MOVE operation stellt ein element nicht an die eigentliche zielstelle, sondern an die zielstelle-n wobei n für anzahl von INSERTs steht, die links vom zu verschiebenden element später dazukommen.

> 4. ausführen der INSERTs
> 5. ermitteln der MOVEs/SWITCHes

wenn ich die INSERTs vor den MOVEs/SWITCHes ausführe, kann ich mir das berechnen von zielstelle-n pro MOVE sparen, ABER dann verschiebt sich ggf. durch MOVEs/SWITCHes ein vorher eingefügtes element, das eigentlich schon an der richtigen stelle stand, was dazu führt, dass ich nochmal ein MOVE/SWITCH machen muss, oder?

 

[SlaterB]

langsam wird das Bild klarer,
als erstes möchte ich auf den letzten Abschnitt meiner ersten Antwort + Marco13' Antwort danach verweisen,
das betrifft doch diese Optimierungen,
ob schon der Weisheit letzter Schluss oder ob es einfacher geht ist natürlich nicht unbedingt erwiesen
(*)

----

die Frage nach den Randbedingungen, die du frech zurückgegeben hast, beantwortest du nun teilweise aber ist noch weiter zu klären,
Reihenfolge der Liste spielt offensichtlich eine Rolle, aber wie ist das mit den Operationen oder sind die überhaupt nicht vorgegeben sondern eher nur der neue Endstand?

deine letzten Zeilen sind ja auch zu dieser Problematik, sei die Ausgangsliste a, b, c
die Operationen
INSERT(d, 1, also hinter dem a) +
MOVE(0,2, also a an die Stelle von c)

je nachdem in welcher Reihenfolge man die Operationen ausführt erhält man erste
a, d, b, c und dann d, b, a, c (INSERT vor MOVE) oder
b, c, a und dann b, d, c, a

woran soll man erkennen, was das Ziel der beiden ursprünglichen Anweisungen war? es sei denn sie standen in Reihenfolge
oder wie gesagt es ist überhaupt nur ein gegebener Endzustand interssant, z.B. b, d, c, a und die Operationen werden daraus gebildet,

also die Probleme sind da, ob du sie beschreibst oder jemand anders,
beantworten bzw. ergänzen musst du sie aber erstmal, nämlich genau die Randbedingungen, alle benötigten Informationen beitragen,
erst dann kann man über Umsetzung nachdenken wobei schwer etwas über das bei (*) genannte hinaus zusammenkommt