Angenommen, wir haben einen gewichteten gerichteten Graphen G und wir haben den kürzesten Weg zwischen den Ecken u und v in G gefunden, indem wir A * suchen oder einen anderen Algorithmus für den kürzesten Weg verwenden. Angenommen, wir verdoppeln alle Kantengewichte in G. Ändert sich der kürzeste Pfad?Kürzester Pfad nach Verdoppelung der Kantengewichte
Mein Argument ist wie folgt: der kürzeste Pfad nicht ändern. Rufen Sie den ursprünglichen Pfad P und nehmen wir an, dass es einen zweiten, anderen Pfad P existiert ‚von u zu v, so dass nach der Gewichte der Kanten zu verdoppeln, P‘ als P. kürzer wird dann,
weight(P') < weight(P)
nach der Verdoppelung . Wenn wir jedoch beide Seiten durch 2 teilen, sehen wir, dass P 'vor der Verdoppelung auch kürzer gewesen sein muss, also war P nicht der kürzeste Weg, um damit zu beginnen, und wir haben einen Widerspruch. Somit bleibt P der kürzeste Pfad nach Verdopplung der Kantengewichte.
Kann jemand diese Lösung kritisieren? Ist es richtig?
Ich denke, das könnte etwas übertrieben sein ... Multiplizieren jedes Kantengewicht mit einem positiven konstanten Faktor ändert nicht den kürzesten Weg - das ist richtig (weil Multiplikation über Addition verteilt). Das Hinzufügen von 1 zu jeder Pfadkante, die auch eine "lineare Transformation" ist, wird jedoch jene Pfade mit mehr Segmenten stärker bestrafen als die mit weniger Segmenten, was oft bedeutet, dass es einen anderen kürzesten Pfad gibt ... – twalberg
@ twalberg Das Hinzufügen von 1 zu jedem Gewicht wird korrekter als "affine" beschrieben, aber ich stimme zu, dass der Wortlaut hier etwas zu wünschen übrig lässt. –
@DavidEisenstat Hmmm ... Ja, ich glaube, du hast Recht ... es sind ein paar ... Jahre ... seit ich das letzte Mal mit den Konzepten der Linearen Algebra vertraut war, ist das Vokabular ein wenig gerutscht. Wenn man jedoch zwischen Polynomen höherer Ordnung, Polynomen höherer Ordnung, Exponentialen, Transzendenten usw. unterscheidet, ist es nicht allzu weit entfernt, affine Transformationen unter dem Begriff "linear" zu betrachten ... – twalberg