Hi Leute, Was genau sind monoton steigende Pfadkosten im Zusammenhang mit Graphenalgorithmen, insbesondere Tiefensuche und Breitensuche? Wäre super, wenn es mir jemand in einfachen Worten erklären könnte. Danke Hello World
hello_world schrieb: > Hi Leute, > Was genau sind monoton steigende Pfadkosten im Zusammenhang mit > Graphenalgorithmen, insbesondere Tiefensuche und Breitensuche? > Wäre super, wenn es mir jemand in einfachen Worten erklären könnte. > Danke ich habe überhaupt keine Ahnung, aber falls die Worte in der Informatik das bedeuten, was sie ansonsten bedeuten, dann gibt es Pfade, offensichtlich der Weg von einem Startpunkt zu einem Ziel, das gesucht ist. offensichtlich führt ein Pfad über mehrere Stationen und hat somit eine Länge offensichtlich sind mit der Länge eines Pfades Kosten verbunden (Rechenzeit?) Monoton steigend sind die Pfadkosten, wenn jeder Pfad wenn er länger wird auch teurer (oder bestenfalls gleichteuer) wird Monoton steigende Pfadkosten scheinen insbesondere den theoretisch denkbaren Fall auszuschließen, dass ein längerer Pfad billiger ist. Vermutlich kann man sagen, dass die Tiefensuche möglicherweise unnötig lange Pfade findet wenn gleichzeitig jeder längere Pfad auch teurer ist, würde das bedeuten, dass ein solcher unnötig langer Pfad nicht optimal wäre. Aber bestimmt erklärt gleich noch einer mit Ahnung, was wirklich gemeint ist ... vlg Timm
Sowas habe ich mir auch gedacht, danke. Folglich müsste Breitensuche doch nicht mehr schneller als Tiefensuche sein. Ich glaube auch, dass sie dann nicht mehr optimal wäre, oder?
wer sagt, dass Breitensuche optimal wäre? Der Aufwand von Breiten und Tiefensuche ist doch identisch. monoton steigende Pfadkosten könnte auch bedeuten, dass Pfadkosten durch hinzunehmen von Kanten immer ansteigen müssen, eine Kante also keine negativen Kosten haben darf.
Udo Schmitt schrieb: > https://www.google.com/search?q=monoton+steigend&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:de:official&client=firefox-a was willst du damit sagen? ich glaub wir wissen alle, was monoton steigend bedeutet.
Vlad Tepesch schrieb: > was willst du damit sagen? > ich glaub wir wissen alle, was monoton steigend bedeutet. Ihr ja, der TO wohl noch nicht. Er fragt nach monoton steigenden Pfadkosten. Monoton steigend bezeichnet eine Funktion, die bei steigendem Argument auch steigended Funktionswerte hat. Pfadkosten ist also eine Funktion, aber was das Funktionsargument ist, das weiss derzeit nur der TO. Vermuten kann man daß eine mehrdimensionale oder mehrere eindimensionale Funktionen gemeint sind mit den Argumenten Tiefe und Breite. Der Link sollte eigentlich ein Augenöffner sein, wie sich der TO bei so einem unbekannten Begriff das selbst erschliessen kann.
:
Bearbeitet durch User
Udo Schmitt schrieb: > Pfadkosten ist also eine Funktion, aber was das Funktionsargument ist, > das weiss derzeit nur der TO. > Vermuten kann man daß eine mehrdimensionale oder mehrere eindimensionale > Funktionen gemeint sind mit den Argumenten Tiefe und Breite. Das braucht man nicht vermuten. Er hat eindeutig von Graphentheorie gesprochen. Also ein Netzwerk aus Knoten und Verbindungen dieser Knoten, wobei jede Verbindung in diesem Netz über eine Attributierung 'Pfadkosten' verfügt. Gesucht ist meist ein Weg von einem Knoten zu einem anderen Knoten, bei dem die Summe der Pfadkosten auf diesem Weg minimal ist. Siehe zb Djikstra Algorithmus http://de.wikipedia.org/wiki/Dijkstra-Algorithmus Die im Wiki Artikel angegebene FOrderung, dass die Kantengewichtungen nicht negativ sein dürfen ist identisch zur Aussage, dass die Pfadkosten monoton steigend sind. Wird ein Pfad um eine Kante verlängert, dann werden die Kosten des neuen Pfades größer. Sie können auch gleichbleiben aber werden sicher nicht kleiner.
:
Bearbeitet durch User
> ich glaub wir wissen alle, was monoton steigend bedeutet. Udo Schmitt schrieb: > Ihr ja, der TO wohl noch nicht. Du auch nicht ... > Monoton steigend bezeichnet eine Funktion, die bei steigendem Argument > auch steigended Funktionswerte hat. Nein, das wäre "streng monoton wachsend/steigend". Karl Heinz schrieb: "Sie können auch gleichbleiben aber werden sicher nicht kleiner." Eben.
Klassisch auch SPP genannt (shortest path problem): Hilft beim googlen. Gruß Jonas
Labskaus schrieb: > Du auch nicht ... > >> Monoton steigend bezeichnet eine Funktion, die bei steigendem Argument >> auch steigended Funktionswerte hat. > > Nein, das wäre "streng monoton wachsend/steigend". Klasse Erbsenzähler, jetzt hast du mich erwischt :-) Wenn ich jetzt auch mal den Erbsenzählermodus anmache. In der Theorie können die Kosten gleichbleiben, in der Praxsis wird der Aufwand immer streng monoton steigend sein, weil das Programm irgendwas tun musst um von einem Knoten über die Kante zum nächsten Knoten zu kommen, und wenn es nur eine Zeigerzuweisung ist.
Udo Schmitt schrieb: > Klasse Erbsenzähler, jetzt hast du mich erwischt :-) Reine Menschenfreundlichkeit und Nächstenliebe. Ein psychisch labiler Mitmensch könnte den Thread lesen, sich deine Aussage merken, deswegen durch die nächste Matheprüfung fallen und sich rächen wollen. Du schuldest mir was.
Udo Schmitt schrieb: > Wenn ich jetzt auch mal den Erbsenzählermodus anmache. In der Theorie > können die Kosten gleichbleiben, in der Praxsis wird der Aufwand immer > streng monoton steigend sein, weil das Programm irgendwas tun musst um > von einem Knoten über die Kante zum nächsten Knoten zu kommen, und wenn > es nur eine Zeigerzuweisung ist. Du redest jetzt aber von anderne 'Kosten'. Es geht um die Fragestellung: Gegeben ein Haufen Städte. Von jeder Stadt zu jeder anderen Stadt entstehen 'Kosten' wenn ich diesen Weg nehme. Die Kosten setzen sich zusammen aus Sprit, Reifenverschleiss, Maut, etc. Die Frage lautet: Wie fahre ich von München nach Verona, so dass ich die geringsten Kosten habe. Was das in Rechenzeit bedeutet, interessiert hier nicht (ausser dass es erlebbar sein muss). Für eine Spedition ist interessant, was sie dem Kunden an Frachtkosten verrechnen soll, so dass noch ein Reibach übrig bleibt. Und dazu brauchen sie die kostengünstigste Route.
Karl Heinz schrieb: > Du redest jetzt aber von anderne 'Kosten'. Du hast recht Kosten können in dem Fall beliebige Attribute sein, ich habe Rechenzeit als "Kostenfaktor" impliziert wegen den Worten "Tiefensuche" Für eine "Suche" sind die Kosten normalerweise die Zeit. Mein Fehler. Aber dafür hinkt dein Beispiel : Im Straßenverkehr/Routenfindung sind die Kosten wie du richtig sagst Sprit+Zeit+Veraschleiss. Die Kanten sind die Straßen, die Knoten die Kreuzungen/Einmündungen. In dem Beispiel gibt es aber keine Kanten mit Kosten 0 da du immer eine Länge hast und dadurch immer Kosten entstehen. Ausser du lässt Kanten mit der Länge 0 zu um eine Kreuzung durch mehrere Knoten abzubilden. Labskaus schrieb: > Du schuldest mir was. Würde ich wenn du mich freundlich verbessert hättest. Deine Aussage: Labskaus schrieb: > Du auch nicht ... hat jegliche Schuld getilgt. :-p
Udo Schmitt schrieb: > Aber dafür hinkt dein Beispiel : Ja natürlich hinkt das. > In dem Beispiel gibt es aber keine Kanten mit Kosten 0 da du immer eine > Länge hast und dadurch immer Kosten entstehen. Motor aus und über den Brenner runterrollen lassen. :-) Ok, ist nicht ganz 0. Aber die Spritkosten sind 0. Ja, ich weiß, nicht alles was hinkt ist ein Vergleich. Worum es aber in der Ausgangssaussage geht: du kannst vielleicht die Kosten an einer Kante auf 0 bringen, aber wie sehr du dich auch bemühst, du kriegst auf dieser Strecke kein Geld zurück. Der Sprit im Tank wird nun mal nicht vermehrt, selbst wenn ich den Brenner runterrolle. In diesem Sinne: die Pfadkosten sind monoton steigend. Ist mir danach auch gekommen, dass die Sache mit Städten und Strassen nicht so gut geeignet ist. Ich hatte zunächst nur die Spritkosten im Auge, musste dann aber den Verschleiss und sonstiges auch noch mit dazunehmen, was die Kernaussage "die kannst vielleicht mit 0 Kosten eine Teilstrecke abfahren aber du kriegst auf keinen Fall Geld zurück - die Pfadkosten sind immer positiv" etwas verwässert hat. Und auf die Schnelle ist mir nichts anderes eingefallen :-)
:
Bearbeitet durch User
Karl Heinz schrieb: > Kosten an einer Kante auf 0 bringen, aber wie sehr du dich auch bemühst, > du kriegst auf dieser Strecke kein Geld zurück. Der Sprit im Tank wird > nun mal nicht vermehrt, selbst wenn ich den Brenner runterrolle. > In diesem Sinne: die Pfadkosten sind monoton steigend. und wenn bei E-Autos der Gegenwert des durch Recuperation gewonnenen Stroms den Wertverlusst durch Verschleiß übersteigt?
Karl Heinz schrieb: > Und auf die > Schnelle ist mir nichts anderes eingefallen :-) Das Beispiel ist schon ok, wenn du z.B. nur Zusatzkosten wie Maut ermitteln willst.
Vlad Tepesch schrieb: > Karl Heinz schrieb: >> Kosten an einer Kante auf 0 bringen, aber wie sehr du dich auch bemühst, >> du kriegst auf dieser Strecke kein Geld zurück. Der Sprit im Tank wird >> nun mal nicht vermehrt, selbst wenn ich den Brenner runterrolle. >> In diesem Sinne: die Pfadkosten sind monoton steigend. > > und wenn bei E-Autos der Gegenwert des durch Recuperation gewonnenen > Stroms den Wertverlusst durch Verschleiß übersteigt? Hmm. Gute Frage. Rückenwind? Ich habs: Dann kannst du den Dijkstra nicht nehmen :-)
Ok. Danke. Sorry fuer die ungenauen Angaben, sodass ihr selbst raten müsst. Es geht darum, in einem Spiel ohne Gegner den optimalen Weg zum Sieg zu finden. Fuer ein gegebenes Spielfeld muss die optimale Loesung gefunden werden, jedoch ist zu Beginn des Spieles nicht klar, wie die Loesung am Ende aussehen muss(Anders als z.B. bei Sudoku). Bisher dachte ich, dass diejenige Loesung die bessere ist, bei der weniger Zuege gemacht werden, als die, bei denen mehr Zuege gemacht werden. Das ist jedoch in seltenen Faellen nicht so. Die Frage war nun, ob man bei dem, was ich zuvor gennant habe monoton steigende Pfadkosten hat. Zudem ist es doch so, dass, wenn die Loesung mit den wenigsten Zuegen nicht die beste ist, Breitensuche keinen direkten Vorteil gegenueber Tiefensuche hat, oder? Danke schoneinmal im Vorraus
Rein theoretisch hat Breitensuche den Vorteil, dass sie immer zum Ergebnis führt, Tiefensuche dagegen unendlichlange laufen könnte ;)
du kannst iterativ vertiefende Tefensuche benutzen. Das spart arbeitsspeicher und ist nicht unendlich lange
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.