T11 Ajuste potencial
Recordemos algumas definições. Seja \((D,c)\) um grafo dirigido com custos reais definidos nos arcos. Isto é, suponha que $D$ seja um grafo dirigido e $c$ seja uma função real $c\colon E(D)\to{\mathbb R}$. Para quaisquer vértices $s$ e $t$ de $D$, definimos a distância $d_{D,c}(s,t)$ de $s$ a $t$ em $(D,c)$ como sendo o mínimo dos custos $c(P)$ onde $P$ varia sobre todos os caminhos dirigidos $P$ de $s$ a $t$ em $D$, e $c(P)=\sum\{c(e)\colon e\in E(P)\}$. Caso $t$ não seja acessível a partir de $s$, temos que $d_{D,c}(s,t)=\infty$.
Suponha agora que fixamos uma função $h\colon V(D)\to{\mathbb R}$, que chamamos de função potencial ou função heurística. Definimos $c'\colon E(D)\to{\mathbb R}$ pondo
\( c'(v,w) = c(v,w) - h(v) + h(w) \)
para todo arco $(v,w)$ de $D$. Considere agora o par $(D,c')$, isto é, o mesmo grafo dirigido $D$ munido da função custo $c'$. Naturalmente, para quaisquer vértices $s$ e $t$ em $D$, podemos considerar a distância $d_{D,c'}(s,t)$ de $s$ a $t$ em $(D,c')$.
(a) Sejam $s$ e $t$ vértices de $D$ e seja $P$ um caminho dirigido de $s$ a $t$ em $D$. Prove que $c'(P)=c(P)-h(s)+h(t)$. Deduza que $d_{D,c'}(s,t)=d_{D,c}(s,t) - h(s) + h(t)$.
(b) Sejam $s$, $t$ e $P$ como em (a). Prove que $P$ é um caminho de custo mínimo em $(D,c)$ se e só $P$ é um caminho de custo mínimo em $(D,c')$.
(c) Suponha que a função potencial $h$ seja tal que
\( c'(v,w) = c(v,w) - h(v) + h(w) \geq 0 \)
para todo arco $(v,w)$ de $D$. Fixe $s$ e $t$ em $V(D)$. Diga como podemos encontrar um caminho de custo mínimo de $s$ para $t$ em $(D,c)$ eficientemente, usando $(D,c')$. (Basta dizer qual algoritmo devemos executar e com qual entrada, observando que tal entrada é válida.)
(d) Suponha que $(D,c)$ não contenha circuitos dirigidos negativos, de forma que $d_{D,c}(u,w)\leq d_{D,c}(u,v) + d_{D,c}(v,w)$ para quaisquer vértices $u$, $v$ e $w$ de $D$. Fixe dois vértices $s$ e $t$ de $D$. Suponha que tomamos $h(v)=d_{D,c}(v,t)$. Prove que
\( c'(v,w) = c(v,w) - h(v) + h(w) \geq 0 \)
para todo arco $(v,w)$ de $D$.
(e) Adicionalmente às hipóteses em (d), suponha que $(D,c)$ não contenha circuitos dirigidos de custo zero (isto é, todos os circuitos dirigidos em $(D,c)$ são estritamente positivos). Então $d_{D,c}(u,w)\leq d_{D,c}(u,v) + d_{D,c}(v,w)$ para quaisquer vértices $u$, $v$ e $w$ de $D$, com igualdade se e só se $v$ pertence a um caminho de custo mínimo de $u$ para $w$ em $(D,c)$. Prove que $d_{D,c'}(s,v)=0$ se e só se $v$ pertence a um caminho de custo de mínimo de $s$ a $t$ em $(D,c)$, onde $c'$ é como definido em (d).
Observação. Note que (e) implica que, ao executarmos o algoritmo de Dijkstra sobre $(D,c')$ para determinar $d_{D,c'}(s,t)$, o algoritmo inclui na árvore de caminhos mínimos, inicialmente, exatamente os vértices $v$ que pertencem a caminhos mínimos de $s$ a $t$ em $(D,c)$. Assim, o algoritmos não explora "vértices não-relevantes" (aqueles que não pertecem a caminhos mínimos) antes de incluir $t$ na árvore de caminhos mínimos. Este fato explica, pelo menos intuitivamente, por que funções potenciais $h(v)$ que aproximam $d_{D,c}(v,t)$ "orientam" a busca de um caminho mínimo de $s$ a $t$ na "direção de $s$ para $t$" quando a busca é executada em $(D,c')$.
Material relacionado. Você pode achar interessante assistir ao vídeo em https://youtu.be/A60q6dcoCjw?si=S2Q6TlOmOAwAYcTr