Algoritmos viáveis e sua aceitabilidade (8)


Continuemos agora com o exemplo das cinco cidades:

Aceitamos que muitos algoritmos matemáticos dão respostas aproximadas em ve z de respostas exactas. Para o PCV procuramos repostas tão boas quanto possível (ou tão boas quanto queiramos), ou melhor procuramos uma resposta que é a melhor possível para os nossos interesses práticos. Tentemos abordagens de bom senso ou de senso comum.

Consideremos a cidade A como ponto de partida e de chegada. Podemos construir exemplos de algoritmos passo por passo:

Primeiro.
Escolhemos a cidade mais próxima de A (i.e, tomemos a aresta de peso mínimo entre as arestas AB, AC, AD e AE: mín{418, 592, 302, 607} = 302 correspondente a AD) que é D. Vamos para D. De D partamos para a cidade mais próxima (que não seja A) que é B (427). Pelo mesmo processo, partamos de B para a mais próxima (excepto A e D) que é C (415), depois para E (583) e retornemos finalmente a A (607). Por este processo algorítmico, encontramos o circuito ADBCEA, com o peso total de 302+427+415+583+627=2334. Não sabemos se é o melhor a não ser que calculemos os 12 circuitos possíveis (o que é possível para 12 circuitos, mas não seria praticável noutros casos com mais cidades). O processo pode ser descrito simplesmente, dizendo que se vai de cidade em cidade, de cada vez indo para a cidade mais próxima ainda não visitada.
 
Segundo.
Ordenemos o conjunto dos pesos das arestas {418, 592, 302, 607, 415, 427, 613, 581, 583}. Obtemos a seguinte sequência ordenada: 302, 415, 418,427, 581, 592, 607, 613, a que corresponde a sequência de arestas AD, BC, AB, BE, CE, AC, AD e BD. Partindo de A, escolhemos D. Para continuar o circuito, temos em seguida de ir para B, depois para E, para C e finalmente para A, obtendo o circuito ADBECA, com o peso total de 302+613+427+581+592 =2515. Seguimos a sequência ordenada dos pesos,
A este processo, podemos chamar algoritmo por ordenação de arestas.
 

Tarefas 2232
a) Partindo de cidades diferentes, a aplicação destes algoritmos pode dar resultados diferentes. Por isso, a cidade sede pode ser escolhida tendo em atenção esses resultados. Aplique aqueles algoritmos a diversas cidades de partida e indique qual a cidade que escolheria para sediar o seu gestor de vendas responsável por aquelas cinco cidades.
b) Se puder, invente um algoritmo diferente destes - processo de decisão única passo por passo que conduza a um resultado único.
c) Calcule a solução óptima para este caso. Qual é o grau de aceitabilidade dos resultados obtidos anteriormente?
 
Tarefa obrigatória:
De um mapa de estradas (ou um roteiro, ou um mapa de companhia aérea) escolha 7 cidades da Europa ligadas que gostaria de visitar numas férias, indicando as distâncias indicada no mapa (ou roteiro). Desenhe um grafo representativo da situação, com as cidades, as arestas e respectivos pesos. Escolha um algoritmo e decida o seu plano de férias de visita a essas cidades.


voltar ao sumário