Solução Maior Menor Caminho

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

 

A solução por força bruta seria simplesmente testar todos os vértices como possíveis A, B, C e D. Entretanto, note que para dados B e C fixos, não faz sentido escolher A_1 mais próximo de B que A_2 se A_2 não aparecer como nenhum dos outros vértices escolhidos. Deste modo, temos apenas 3 possibilidades para A: os 3 vértices mais distantes de B (partindo deles), visto que não faz sentido escolher um outro pois dentre eles sempre há pelo menos um que não é C ou D. De modo semelhante, há apenas três possibilidades para D.

Seja \alpha(v) = {u_1, u_2, u_3} de modo que a distância de u_i para v não é inferior à de nenhum vértice não contido em \alpha(v) (\alpha(v)={u_1,u_2,u_3}, \forall 1\leq i \leq 3, j, d(u_i,v)\geq d(j,v)), ou seja \alpha(v) são três vértices u_i cujos valores d(u_i,v) são máximos. De maneira semelhante, Seja \beta(v) = {u_1, u_2, u_3} de modo que a distância de v para u_i não é inferior à de nenhum vértice não contido em \beta(v)

Como vimos, basta agora testarmos todos os valores possíveis para A, B, C e D da seguinte maneira: vamos testar, por força bruta, todos os possíveis valores de B e C, então testaremos os três valores possíveis de A (\alpha(B)) e os tr~\e possíveis valores de D (\beta(D)). A complexidade é O(n^2).

Segue o código para melhor entendimento:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: