Sortieralgorithmus mit möglichst wenigen "Bewegungen"

[YoCed]

Nun, um es mal Bildlich darzustellen, es geht darum, es gibt eine bestimmte Art von "Kästen", z.B. 5, und ebensoviele Objekte, wovon jeweils ein bestimmtes in einen Kasten muss.

Aber die Kästen stehen der Reihe nach nebeneinander, die Objekte stehen zufällig.

Also könnte man sich das z.B. so vorstellen:

Kästen: 1 - 2 - 3 - 4 - 5

Objekte: 4 - 1 - 2 - 5 - 3

Jetzt müssen die Objekte in die jeweiligen Kästen rein, also Sortiert werden. Das ist ja garnichtmal so schwer, aber es gibt ja noch beschränkungen.

Wenn man mal weiter Bildlich spricht, könnte man sagen, an der Position der ersten Box steht ein Roboter, der die Objekte sortiert. Der Roboter kann immer 2 Objekte gleichzeitig in der Hand halten, aber sich nur mit einem Bewegen. Außerdem, naja, sagen wir mal die Bahn, auf der sich der Roboter bewegt, verschleißt. Deswegen soll sich der Roboter möglichst wenig bewegen. Bei den Vergleichen oder dem Absetzen der Objekte verschleißt nichts, also ist das egal.

Und es gibt noch eine weitere Regel: Der Roboter muss sowohl am Anfang als auch am Ende an der ersten Position stehen.

Ich hab schon viel gegooglet und in anderen Foren geschaut, da hab ich aber nur die "normalen" Sortierverfahren wie z.B. Bubblesort und Quicksort gefunden, wo es ja nicht um die Strecke sondern eher um die Anzahl vergleiche und so geht.

Ich hoffe, dass hier endlich mein Problem gelöst wird.

Mfg, YoCed.

[flashpixx]

Das sind 2 unabhängige Probleme. D.h. Du musst einmal feststellen, welches Objekt in welchen Kasten muss. Das würde man hier wohl mit einem Bucketsort machen, der hat eine lineare Laufzeit (O(n))

Die Wegeoptimierung ist nicht trivial, weil um den kürzesten Weg zu bestimmen, müsstest Du alle möglichen Wege durchlaufen, was algorithmisch gesprochen mit der Anzahl Deiner Kästen exponentiell steigt. Man kann hier zu z.B. einen Greedy-Algorithmus verwenden. Speziell für Wegfindung gibt es A*-Algorithmus oder alternativ kann man Genetischer Algorithmus dafür verwenden

[YoCed]

Okay, ich denke nicht, dass Bucketsort hier hilft, das sortieren soll ja auch vom "Roboter" gemacht werden, und beim Bucketsort bewegt der sich da doch recht lange..

Und naja, die Algorithmen suchen ja immer die kurzesten Strecken, aber auch da glaub ich nicht, dass das so von nöten ist.. Ich bin aber auch nicht so ein Mega-Profi in dem Gebiet Algorithmen, ich brauch das recht wenig..

Gibts nicht irgendein Sortierverfahren, dass direkt auf einen sehr kleinen Weg achtet?

[flashpixx]

Gibts nicht irgendein Sortierverfahren, dass direkt auf einen sehr kleinen Weg achtet?

Du scheinst das Problem nicht verstanden zu haben!

Du musst einmal ermitteln welches Objekt in welchen Kasten soll, das kann man eben über sortieren machen, wenn die Kästen einer Ordnung folgen. Das zweite Problem ist, dass Du vom aktuellen Standpunkt des Roboters berechnen musst, welchen Weg er zu dem nächsten Kasten fahren muss, das ist das Problem der Wegfindung.

Und nein, es gibt dafür kein fertiges Sortierverfahren, denn das Problem ist weitaus komplexer.

[Klotzkopp]

Das Sortieren kann man sich sparen, es ist ein reines Problem des Findens des optimalen Weges. Da die Kästen und die Objekte schön durchnummeriert sind, steht ja von Anfang an fest, welches Objekt in welchen Kasten gehört.

[flashpixx]

Das Sortieren kann man sich sparen, es ist ein reines Problem des Findens des optimalen Weges.

Wenn man die Problematik allgemein formuliert, dann muss dies nicht zwingend so sein. Sobald die Kästen nicht sortiert bzw permutiert werden, ist das Problem da. Ein typischer Fall wäre das Rucksackproblem, wobei das hinzuzufügende Objekt nicht Teilbar (aus N) ist. In diesem Fall muss ich einen Kasten wählen, in dem mindesten bzw mehr Platz ist, als für mein Objekt nötig ist. Die Permutation der Kästen kann sich ergeben, wenn man die zu füllenden Kästen nur von links oder rechts anlegen kann, d.h. ist ein Kasten voll, fällt er aus der Reihe raus und links / rechts wird ein neuer angelegt. In diesem Fall muss dann die komplette Struktur reoptimiert werden, da hier nicht nur die Reihenfolge der Ziele sich verändert, sondern auch ggf die Weglänge.

Die zentrale Frage bleibt somit erhalten, ob dem Roboter bekannt ist, wo welcher Kasten mit welcher Nummer steht. Ist das bekannt und ist das konstant, dann ist es reine reine Wegfindung, die man aber bei diesen kleinen Datenmengen direkt berechnen kann und fest im System speichern kann (selbst mit einem naiven Algorithmus).

Ändert sich das Volumen der Kästen, deren Position oder muss beim Befüllen eine Reihenfolge beachtet werde (klassischer Fall in der Logistik z.B. bei Lebensmitteln muss die Lagertemperatur im LKW sichergestellt werden) ist das Problem wesentlich komplexer, so dass hier entsprechende Heuristiken Anwendung finden

Bearbeitet 26. März 2011 von flashpixx

[YoCed]

Die zentrale Frage bleibt somit erhalten, ob dem Roboter bekannt ist, wo welcher Kasten mit welcher Nummer steht

Ja, das ist bekannt, die Kästen stehen immer in der reihenfolge 1,2,...,n

Ändert sich das Volumen der Kästen, deren Position oder muss beim Befüllen eine Reihenfolge beachtet werde (klassischer Fall in der Logistik z.B. bei Lebensmitteln muss die Lagertemperatur im LKW sichergestellt werden) ist das Problem wesentlich komplexer, so dass hier entsprechende Heuristiken Anwendung finden

Also, das ist kein Problem, das Volumen ist egal und eine Reihenfolge muss nicht beachtet werden.

[flashpixx]

Dann muss der Roboter nur ein Objekt nehmen und in den richtigen Kasten sortieren. Da sich der Roboter nur auf einem Weg bewegen kann, wird hier wohl auch nicht viel zu optimieren sein, denn nach jedem abgelegten Objekt, muss der Roboter wieder an den Punkt fahren, an dem er ein neues Objekt erhält. Wenn der Roboter seinen Weg nicht frei wählen kann, dann kann man da auch nicht optimieren. Wenn der Roboter mehrere Objekte transportieren kann und die Aufnahmereihenfolge ändern kann, dann wäre es das Optimierungsziel die Objekte so auszuwählen, dass alle Wegstrecken gleich oft befahren werden, wobei dies natürlich auch abhängig von den Eingabedaten ist. Kann der Roboter aber nicht die Reihenfolge der Objekte beeinflussen, dann kann man hier auch nicht optimieren.

[YoCed]

Moment, ich glaube du hast da was falsch verstanden (oder ich bin zu doof), die verschiedenen Objekte stehen in zufälliger Reihenfolge gegenüber der Kästen, also etwa so:

Kästen -v

1 - 2 - 3 - 4 - 5

4 - 1 - 2 - 5 - 3

Objekte -^

Also es gibt keine "Stelle", wo der Roboter die Objekte bekommen, denn die Objekte liegen gegenüber der Kästen.

[flashpixx]

Entscheidend dabei ist aber, wie die Konzipierung des Roboters aussieht. Denn wenn der Roboter nur zu einem Objekt fahren kann, es sich anschaut und weiß dann wohin er es transportieren muss, dann kannst Du daran nichts ändern oder optimieren. Entscheidend zur Optimierung ist das Problem. Wenn der Roboter vor dem Start alle Objekte kennt (mit deren Wert und Position), dann kannst Du den Weg optimieren, denn Du würdest den kürzesten Pfad suchen um alle Elemente anzufahren. D.h. für die komplette Eingabereihenfolge musst Du eben den kürzesten Pfad berechnen, was letztendlich das Problem des Handlungsreisenden ist und man mit einer Heuristik gut durchführen kann. Da Du ja hier den Verschleiß minimal haben willst würde ich wohl zur Christofides-Heuristik greifen, da sie nur 1.5mal schlechter ist, als der optimale Weg. Evtl lässt sich der Weg auch mit A* berechnen, obwohl ich mir im Moment nicht sicher bin, denn A* berechnet nur den kürzesten Pfad, zwischen zwei Punkten. Du willst ja im Grunde eine "Rundreise" berechnen, die minimal / optimal ist.

Die Anwendung geht natürlich nur, wenn Du den Weg vorberechnen kannst, d.h. Weg berechnen und dann muss der Roboter den Weg nur abfahren. Wenn der Roboter eben erst jedes Objekt anschauen muss, um fest zu stellen, welches Objekt vorliegt und er sich nur genau dieses eine Objekt merken kann, dann kannst Du nicht optimieren, Du hast ja dann keine Information welche Objekte noch vorhanden sind bzw. welche schon einsortiert wurden.

Bearbeitet 26. März 2011 von flashpixx

[YoCed]

Der Roboter weiß, welche Objekte wo stehen.

Okay, ich schau mir dann mal die Christofides-Heusterik an, wenns Probleme gibt melde ich mich,

Danke für alles schon mal

[flashpixx]

Zur Datenstruktur würde hier wohl eine Adjazenzmatrix / -liste notwendig werden und Du hättest bei einer Matrix bei n Objekten (2n)^2 Einträge. Ich würde einmal das Objekt als Knoten und einmal die Zielbox als Knoten modellieren. Wenn man in einem Knoten ist, der ein Objekt ist, dann gibt es nur einen einen gültigen Eintrag in der Zeile / Spalte. Wenn Du an einer Box stehst, dann kannst Du alle Objektelemente anfahren, die nicht Box sind und nicht die Box selbst, an der Du stehst. Wenn Du ggf noch irgendwelche Wegekosten dann hättest, kannst Du das einfach an die Kanten des Graphen hinzufügen.

[YoCed]

Okay, jetzt versteh ich garnichts mehr..

Was ist eine Adjazenzmatrix oder Liste??

Und warum brauche ich eine Matrix?

Und was meinst du mit Modellieren?

[flashpixx]

Du musst das Problem erst als Graphenproblem betrachten, damit Du mit der Heuristik überhaupt arbeiten kannst. Du musst somit Deine Daten passend repräsentieren und für Graphen nimmt man i Allgm. Adjazenzstrukturen, siehe Repräsentation von Graphen im Computer

Aufgrund dessen musst Du im ersten Schritt der Christofides-Heuristik einen minimalen Spannbaum erzeugen, wobei Du dazu den Algorithmus von Prim (alternativ ginge auch Algorithmus von Kruskal) verwenden kannst und dazu als Datenstruktur einen Fibonacci-Heap benötigst. Dann schaust Du Dir die Knoten mit ungeraden Knotengrad an und versuchst diese passend zu matchen. Daraus ergibt sich ein neuer Graph, in dem Du dann den Eulerkreis bestimmst, wobei das in linearer Zeit mit Algorithmus von Hierholzer möglich ist.

Bearbeitet 26. März 2011 von flashpixx

[YoCed]

Wie sähe denn die Adjazenzmatrix zu z.B.

1-2-3-4-5

4-1-5-3-2

aus?

Und: Wie komm ich überhaupt zu der Grafik?

Vielleicht sollte ich mich nochmal verbessern.. Ich bin nicht nur Neuling in Sachen Algorithmik, man könnte sagen, ich bin noch dazu ein Neuling in der Informatik.. Ich hab zwar in manchen Sprachen schon was programmiert, aber immer nur kleinere sehr leichte Sachen :/

[flashpixx]

Wie sähe denn die Adjazenzmatrix zu z.B.

1-2-3-4-5

4-1-5-3-2

aus?

Schau Dir das Beispiel auf der Wikipedia-Seite an.

Und: Wie komm ich überhaupt zu der Grafik?

Die visuelle Darstellung ist unabhängig von der Adjazenzmatrix.

Vielleicht sollte ich mich nochmal verbessern.. Ich bin nicht nur Neuling in Sachen Algorithmik, man könnte sagen, ich bin noch dazu ein Neuling in der Informatik.. Ich hab zwar in manchen Sprachen schon was programmiert, aber immer nur kleinere sehr leichte Sachen :/

In diesem Fall solltest Du Dich erst einmal mit den genannten Datenstrukturen und deren konkrete Umsetzung beschäftigen. Grade das Erzeugen der passenden Adjazenzstrukturen ist Grundlage der Problemlösung

[erik123]

Hallo,

wenn du möchtest, kann ich dir am 28. April 2011, also nach dem Einsendeschluss für die 2. Runde des Bundeswettbewerb Informatik's, die grundsätzliche Lösungsidee für diese Aufgabe mitteilen. Da mich die von dir formulierte Aufgabenstellung sehr an die Aufgabe mit den Containern ( http://bwinf.de/fileadmin/templates/bwinf/aufgaben/bwinf29/aufgaben292.pdf ) erinnert, bitte ich dich um Verständnis, dass ich keine Aussagen hierzu vor dem offizellem Einsendeschluss machen werde. Wenn dich die Fragestellung aber wirklich interessiert, PM an mich, und am 28. können wir gerne darüber reden! Die Aufgabe ist definitiv lösbar!

Bearbeitet 17. April 2011 von erik123