Supponiamo di avere un grafico G pesato e abbiamo trovato il percorso più breve tra i vertici uev in G usando A * search o qualsiasi altro algoritmo di percorso più breve. Supponiamo ora di raddoppiare tutti i pesi dei bordi in G. Il percorso più breve cambia?Percorso più breve dopo il raddoppio dei pesi dei contorni
Il mio argomento è il seguente: il percorso più breve non cambia. Chiamare il percorso P originale e supponiamo che esiste un secondo, differente percorso P 'da u a v tale che dopo aver raddoppiato i pesi dei bordi, P' è più breve di P. Quindi,
weight(P') < weight(P)
dopo il raddoppio . Tuttavia, dividendo entrambi i lati per 2 vediamo che P 'deve essere stato anche più corto prima del raddoppio, quindi P non era la via più breve per iniziare e abbiamo una contraddizione. Pertanto, P rimane il percorso più breve dopo aver raddoppiato i pesi dei bordi.
Qualcuno potrebbe criticare questa soluzione? È corretto?
Penso che potrebbe essere leggermente sopravvalutato ... Moltiplicare ogni peso del bordo con un fattore costante positivo non cambierà il percorso più breve, cioè corretto (perché la moltiplicazione viene distribuita oltre l'addizione). Tuttavia, l'aggiunta di 1 ad ogni bordo del percorso, che è anche una "trasformazione lineare", penalizzerà quei percorsi con più segmenti in misura maggiore rispetto a quelli con meno segmenti, il che spesso significa che c'è un diverso percorso più breve ... – twalberg
@ twalberg L'aggiunta di 1 a ciascun peso è più propriamente descritta come "affine", ma concordo sul fatto che la formulazione qui lascia qualcosa a desiderare. –
@DavidEisenstat Hmmm ... Sì, credo che tu abbia ragione ... sono passati alcuni .... anni ... da quando ero l'ultimo esperto di concetti di algebra lineare, quindi il vocabolario è scivolato un po '. Ma se la distinzione è tra polinomi lineari vs ordine superiore, esponenziali, trascendentali e simili, considerare le trasformazioni affini sotto l'ombrello di "lineare" non è troppo lontano ... – twalberg