Logikfrage: Raster mit Marken
-
Hallo miteinander,
ich beschäftige mich zur Zeit mit folgendem Problem:
Gegeben sei ein Raster mit bekannter Höhe u. Breite.
Auf einigen Feldern des Rasters befinden sich Marken.Man startet links oben in der Ecke und möchte so viele der marken wie möglich einsammeln. Dabei kann man sich jedoch immer nur nach unten oder nach rechts bewegen.
Sprich in negative Y-Richtung oder in positive X-Richtung.Meine Herrangehensweise:
"Die Suche nach dem Nähesten": Vom akteullen Feld des Rasters sucht man immer nach dem am nähe gelegensten mit einer Marke. Sind zwei oder mehrere Felder mit Marken gleichnah, dann schaut man welche der Felder am nähesten zu anderen Marken sind usw.Scheitert leider nach einigen malen ausprobieren auf dem Papier...
Hat jemand vlt einen kleinen Denkanstoß bzw. Ansatz für das beschriebene Problem? Würde mir sehr weiterhelfen.
mfg, Mogunt
-
Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (alle ISO-Standards) in das Forum Mathematik und Physik verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
Füge jeder Marke eine Charakteristik hinzu. Diese ist 0, falls sich im gesamten Raster links über ihr keine anderen Marken befinden und ansonsten N+1, wobei N die Marke mit der größten Charakteristik im Raster links über ihr ist.
Der Pfad mit der höchsten Zahl sammelbarer Marken kann rückwärts konstruiert werden, indem man vom Endpunkt zur Marke mit der größten Charakteristik geht und von dort aus immer zu einer Marke mit Charakteristik N-1 geht, wobei N die Charakteristik der aktuellen Marke ist. Gibt es mehrere solcher Marken, so gibt es auch mehrere Pfade, die aber gleichwertig sind.
-
Hier eine Demo und ein möglicher Algorithmus zur Charakterisierung der Marken. Wobei es für letzteres sicherlich auch noch bessere Methoden gibt:
http://postimg.org/image/u4saoyjz7/
-
@SeppJ: im Prinzip ist das ein dynamisches Programm: der Eintrag für jeden Knoten ist das Maximum aller Einträge von Marken die links oberhalb von ihm liegen. Damit kann man die Tabelle relativ leicht ausfüllen.
Eine andere Möglichkeit (basiert letztlich auf derselben Idee) ist die folgende:
Du baust Dir einen Graphen wie folgt:
- ein Knoten pro Marke
- eine gerichtete Kante von Marke a zu Marke b wenn b von Kante a mit einem gültigen Pfad erreichbar ist (a also links oberhalb von b liegt)Der resultierende Graph G ist ein gerichteter azyklischer Graph (DAG). Nun suchst Du einen längsten Pfad in diesem Graphen; hierfür gibt es fertige Algorithmen.
-
Jester schrieb:
Nun suchst Du einen längsten Pfad in diesem Graphen; hierfür gibt es fertige Algorithmen.
Die Suche nach dem laengsten Pfad ist normalerweise nicht so gut, oder? Wegen der Komplexitaet. Ich weiss allerdings nicht, ob hier vielleicht ein Spezialfall vorliegt.
Ich wuerde das eher als ein Kuerzester Pfad Problem formulieren. Alle Felder, in denen Marken sind, kriegen Kosten <1, die leeren Felder hingegen Kosten >=1. Wenn man das dann mittels Dynamic Programming loest, ist man wieder bei SeppJs Loesung.
-
Gregor schrieb:
Jester schrieb:
Nun suchst Du einen längsten Pfad in diesem Graphen; hierfür gibt es fertige Algorithmen.
Die Suche nach dem laengsten Pfad ist normalerweise nicht so gut, oder? Wegen der Komplexitaet. Ich weiss allerdings nicht, ob hier vielleicht ein Spezialfall vorliegt.
Wie ich sagte ist das ein DAG, da kann man auch längste Wege berechnen, sogar kürzeste Wege wenn die Gewichte beliebig (auch negativ) sind.
Deine Umschreibung als Kürzeste-Wege-Problem funktioniert nur wenn alle Wege von der Quelle zum Ziel dieselbe Hop-Länge (Anzahl der Knoten/Kanten auf dem Weg) haben. Das ist hier der Fall. Gilt es nicht, kann man die Pfadlänge und die aufgesammelten Knoten gegeneinander ausspielen und optimiert dann eher sowas wie Anzahl der aufgesammelten Marken pro besuchten Knoten -- das ist meist nicht das was man will.
-
Brute Force, (+Wegeschablonen). Machen Staubsauger glaube ich auch so
.
Wo kommt die Übersicht her? Gibt es einen "Vorhersage-Cache" für x Felder/x Vektoren?(Die Problematik erinnert an "Vier gewinnt")
-
wirrinirr schrieb:
Brute Force, (+Wegeschablonen).
Wo bekommst du die Schablonen her? Wozu braucht man überhaupt Schablonen, wenn man sowieso alle Pfade abdecken möchte? Wann ist Brute Force jemals die beste Antwort auf irgendwas?
Machen Staubsauger glaube ich auch so
.Staubsauger machen einen Random-Walk, das ist ganz was anderes. Und sie haben eine ganz andere Aufgabe, nämlich möglichst das ganze Feld abzudecken, nicht auf einer Fahrt möglichst viel einzusaugen.
(Die Problematik erinnert an "Vier gewinnt")
Soll dieser Beitrag eine Parodie auf Furble Wurble sein?
-
[quote="SeppJ"]Staubsauger machen einen Random-Walk, das ist ganz was anderes. Und sie haben eine ganz andere Aufgabe, nämlich möglichst das ganze Feld abzudecken, nicht auf einer Fahrt möglichst viel einzusaugen.
[quote]Naja, also genau genommen würde es mir ja reichen wenn er die Stellen abfährt wo Dreck ist -- die allerdings alle und nicht nur möglichst viele während er von der Ecke des Raums wo ich ihn abgesetzt hab zur Ladestation fährt.
-
Wenn der Staubsauger die Möglichkeit hätte, den Raum gezielt nach Dreck abzuscannen, dann wäre das sicher eine gute Idee, da es sehr viel Energie und Zeit spart. Aber ich glaube, die Robotik ist da noch nicht ganz so weit
Und der Staubsauger müsste dann für den optimalen Pfad das Traveling Salesman Problem lösen, was viel interessanter ist!
-
SeppJ schrieb:
Und der Staubsauger müsste dann für den optimalen Pfad das Traveling Salesman Problem lösen, was viel interessanter ist!
Das ist ein euklidisches Traveling Salesman Problem. Das kann man zumindest effizient approximativ mit einer Garantie bezueglich der maximalen Abweichung vom Optimum loesen.
