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 :/

Okay, jetzt versteh ich garnichts mehr.. Was ist eine Adjazenzmatrix oder Liste?? Und warum brauche ich eine Matrix? Und was meinst du mit Modellieren?

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

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.

Ja, das ist bekannt, die Kästen stehen immer in der reihenfolge 1,2,...,n Also, das ist kein Problem, das Volumen ist egal und eine Reihenfolge muss nicht beachtet werden.

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?

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.