Monoton steigende Pfadkosten?

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

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.

https://www.google.com/search?q=monoton+steigend&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:de:official&client=firefox-a

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.

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.

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:

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

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