Finden minimalen Pfades in einem Baum mit mehrwertigem Knoten

Question

Meine Mathe Klassen sind weit hinter sich, und ich bin zu kämpfen zur Zeit eine anständige Lösung für ein Problem zu finden, ich habe: Ich habe einen Baum haben, in denen Knoten Aktionen sind, und sind „gewichtet“ nach mehreren Kriterien: die Kosten der Aktion, wird die Zeit nehmen, sie die erforderlichen Mittel aufzunehmen, die Störung, etc ...

Und ich mag den Pfad in diesem Baum zu finden, die sowohl die Kosten und die Zeit, beispielsweise minimiert oder die Störung und die Kosten und die Zeit, usw. Mein Problem ist, dass ich keine Ahnung habe, wie man es tun, außer indem sie mit einer globalen Kostenfunktion F (Kosten, Zeit, Ressourcen, ...) kommen, und wenden Sie einen regelmäßigen Baumdurchlauf-Algorithmus das Ergebnis von F (...) als mein einziges Gewicht. Aber dann, wie kann ich mit F kommen? So etwas wie "F (Kosten, Zeit, Ressourcen) = a * Kosten + b * time + c * Ressourcen" fühlt sich sehr "unprofessionell" ...

Edit:

ich das Wort „Summieren“ vermeiden wollte, da ich nicht sicher war, es war wirklich der Weg zu gehen, aber im Grunde ist das, was ich tue: Gesamtkosten für jeden „Pfad“ oder „Zweig“ Rechen das geht von diesem obersten Knoten zu einem der Blätter, und die Wahl der „Pfad“ oder „Zweig“, die die Kosten minimiert. Das Problem ist, dass jeder Knoten ein Gewicht auf der Basis der Zeit, die notwendig, über die finanzielle Kosten, auf die Ressourcennutzung, etc.

So scheint es unvermeidlich, mit einer Formel zu haben, zu kommen, wie Stephan sagt, dass all diese Parameter zu einem global Kosten reduzieren, pro Knoten, die ich kann dann über den Knoten zusammenfassen, wie ich den Baum fahre nach unten, und wählen Sie der Weg, die Gesamtkosten.

minimiert

Also ich meine Frage erraten wirklich ist, es gibt eine Methode, um diese Funktion zu wählen?

Vielen Dank für Ihre Antworten und Kommentare, es fängt jetzt ein bisschen mehr klar im Kopf zu sein.

Answer 1

Lassen Sie uns sagen, dass wir vier Paare haben (x, y) wie (1, 4), (1, 5), (2, 3), (3, 3). Jetzt wollen Sie minimieren „x und y“. Was meinst du? Wenn Sie erste x minimieren und dann y Sie am Ende mit (1, 4). Wenn Sie zuerst y minimieren und dann x Sie finden (2, 3).

Wenn Sie eine globale Kostenfunktion F (x, y) wählen, wie in Ihrer Beobachtung, ich sehe keine Bedeutung von „both“. (Wie auch immer, sobald F gewählt wird, kann es noch mehrere Minima sein.) Übrigens, meiner Meinung nach einer linearen Kombination (die positiven Multiplikatoren a, b, c als „Gewichte“ zu verstehen ist) nicht „unprofessionell“ überhaupt wenn Sie zumindest haben keine Vorstellung davon, was eine geeignetere Kostenfunktion sein könnte.

Edit:

  

So scheint es unvermeidlich, mit einer Formel zu haben, zu kommen, wie Stephan sagt, dass all diese Parameter zu einem global Kosten reduzieren, pro Knoten, die ich kann dann über den Knoten zusammenfassen, wie ich den Baum fahre nach unten, und wählen Sie der Weg, die Gesamtkosten.

minimiert

Vorsicht. Tatsächlich macht diese Strategie nur Sinn, wenn F linear ist. Sicherlich Kosten, Zeit, Ressourcen usw. sind additiv Funktionen, im Sinne, dass die Zeit (node1 -> Knoten2 -> node3) = Zeit (node1) + Zeit (Knoten2) + Zeit (node3), aber im Allgemeinen ist dies nicht der Fall, für F, es sei denn, es ist linear. (Das heißt F (Kosten (node1 -.> Knoten2)) = F (Kosten (node1) + Kosten (Knoten2)) = F (Kosten (node1)) + F (Kosten (Knoten2)))

Wenn Sie eine nicht-lineare globale Kostenfunktion wählen, die richtige Strategie für jeden Knoten zu berechnen, die Gesamtkosten, Gesamtzeit, Gesamtressourcen von der Wurzel zu diesem Knoten, und berechnet (dann minimieren) F nur für das Endgerät Knoten.

Answer 2

mit F Coming up ist das Wichtigste. Wenn ich Ihnen 6 Kosten und 5 Mal oder 5 Mal und 6 Kosten geben kann, was bevorzugen Sie? Ihre Kostenfunktion muss, dass berücksichtigen. Es gibt keinen Algorithmus, der dieses Problem für Sie zu lösen, geht leider. Ich bestreiten, dass für eine Woche, bevor ich setzte mich hin und schrieb F für eine Optimierungsanwendung ich arbeite. Im schlimmsten Fall, lassen Sie Parameter für den Benutzer zu basteln.

Answer 3

Warum sollte nicht ein normaler Graph Suchalgorithmus wie A * Arbeit?

Für die Pfadkostenfunktion, können Sie die laufende Summe der relevanten Kriterien verwenden. Die Entfernung zum Ziel ist es schwieriger ...

Es könnte der Abstand zum nächsten Blatt, im Voraus berechneten für alle oder einzelne Knoten, aber das ist furchtbar teuer klingt. Je nach Struktur des Baumes, könnten Sie mit einer billigeren Unterschätzung kommen -. Wenn es perfekt ausbalanciert ist, zum Beispiel, ist es trivial