O Travelling Salesman

Lista 6

Thomaz Hugo Suzuki

EXER 1

Provar que a escolha gulosa funciona.

S = {a1, a2, . . . , an}

Inicio s(i); Fim f(i)

Algoritmo 🡪 escolher a ultima atividade à começar, sem sobreposições.

Lema: Seja A uma solução ótima para S e  a atividade que começa por ultimo, sem sobreposição.  é o ultimo a começar em A.[pic 1][pic 2]

1.  então funciona [pic 3]
2. [pic 4]

Provar que é ótima.

Lema: Seja A computada pelo algoritmo descrito acima para S, seja  a escolha gulosa. Se |A¨| é a solução ótima para , então A é ótimo para S.[pic 5][pic 6]

Considerando:

        |A| = |A¨| + 1, |A¨| = |A| - 1

Hipótese: Suponha A* tal que |A*| > |A|

        |A*| = |A*¨| + 1

        |A*¨| = |A*| - 1

        --------------------

                >|A|-1

                =|A¨|, contradição.

EXER 2

Max = d. por dia

p1, p2, p3, ..., pn.

Escolha gulosa: escolher sempre a parada mais distante do ponto atual.

Prova:

Escolhendo o ponto de parada mais distante do ponto atual garante que todos os dias sejam percorridos a maior distância e decorrente desse subproblema otimizado, garantimos também que chegaremos a cidade em menor tempo.

EXER 3

G=(V,E)     u,v  V [pic 7]

Faz v.d =  para todo v  V[pic 8][pic 9]

s.d = 0

v.c = 1

c = {s}

enquanto cv[pic 10]

        dentre todas arestas (u,v),

        se v.d > u.d + [pic 11]

        v.d = u.d + [pic 12]

        update (G, v)

                se v.d == u.d + [pic 13]

                v.c = v.c+1

                fim

        fim

fim

EXER 4

G=(V,E)    

G’=(V,E’)    

No grafo G’ o algoritmo de busca em largura perde muito de sua eficácia devido ao grande número de vértices e poucas arestas. Nesses casos a busca em profundidade é mais aconselhável.

EXER 5

A	B	C	D	E	F	G
0	[pic 14]	[pic 15]	[pic 16]	[pic 17]	[pic 18]	[pic 19]
0	2	4	7	[pic 20]	[pic 21]	[pic 22]
0	2	4	7	5	[pic 23]	10
0	2	4	7	5	5	10
0	2	4	7	5	5	10
0	2	4	6	5	5	10
0	2	4	6	5	5	10
0	2	4	6	5	5	10

Arvore de distancia

  D         G

  1            8

  F 5 A 2 B 3 E

        4

        C

EXER 6

Um caminho mínimo não pode ter ciclos, pois o caminho mínimo de um vértice até ele mesmo é 0, portanto se existir um ciclo, ele será maior que 0, não sendo mais o caminho mínimo.

EXER 7

Utilizarei do algoritmo de busca em largura.

BFS (G, S)

Marca S

Insere S em F

Enquanto F não está vazia faça

        Seja v o primeiro vértice de F

        Para cada w  ListaAdjacencias de v faça[pic 24]

                Se w não marcado então

                        Visite aresta em v e w

                        Marca w

                        Insere w em F

                Senão se w F então[pic 25]

                        Visita aresta em v e w

                Fim

                Fim

        Retira v de f

Fim

Meu algoritmo não funciona se o grafo possuir arestas negativas, pois após ele passar pela aresta, ele já conta como o caminho menor e marca aquela aresta como visitada, portanto se no decorrer do algoritmo ele achar um aresta negativa que diminua o caminha até um vértice que ele já passou, ele não atualizará o valor do vértice, pois o vértice já estará marcado (fechado).

...