Modelagem via grafos:
Noções sobre algoritmos de solução
Noções de Algoritmos de Solução
Problema do Caixeiro Viajante (PCV):
Determinar se existe um ciclo Hamiltoniano
de custo mínimo
Problema de Coloração:
Determinar se um grafo G possui número
cromático, χ(G) = k, para k ≥ 3.
Noções de Algoritmos de Solução
• Não existe um algoritmo eficiente para
resolver estes problemas (NP-difícil)
• Pelo algoritmo de força bruta seria
necessário gerar todas as possibilidades
possíveis e verificar cada uma delas
• É impraticável para problemas grandes!!
Algoritmo de força bruta
• Problema do caixeiro viajante: (n-1)!
Soluções possíveis sendo n o número de
vértices (cidades)
• Problema de coloração (χ(G) = k): para cada
vértice existe k possibilidade de cor.
• É impraticável para problemas grandes!!
Noções de Algoritmos de Solução
• Heurística: é uma técnica para resolver um
problema mais rapidamente quando os métodos
clássicos são muito lentos ou para encontrar uma
solução aproximada quando os métodos clássicos
não conseguem encontrar uma solução exata
Algoritmo guloso: é aquele que sempre realiza a
escolha que parece ser a melhor no momento, fazendo
uma escolha ótima local, na esperança de que esta
escolha leve até a solução ótima global.
Heurística - PCV
Algoritmo do vizinho mais próximo (Nearest neighbor):
1. Inicie a rota com um vértice escolhido aleatoriamente.
2. Escolher dentre os vértices que ainda não estão na rota, o vértice
adjacente mais próximo do último vértice inserido na rota.
3. Adicionar o vértice escolhido na posição final da rota
4. Pare se todos os vértices foram adicionados a rota, senão voltar
ao passo 2.
Noções de Algoritmos de Solução
Algoritmo do vizinho mais próximo:
Comprimento Total = 20
Ref: [Link]
Comparação de Heurística - PCV
Comparações de heurísticas em um bechmark com
problemas variando de 105 a 2392 cidades. Distância
média da solução ótima
• Nearest neighbor: 24% (Vizinho mais próximo)
• Closest insertion: 20%;
• Farthest insertion: 10%;
• Cheapest insertion: 17%;
• Random Insertion: 11%
Heurística – Coloração em Grafos
Algoritmo Guloso:
Vértices de listados em ordem v1, v2, . . . , vn.
Conjunto de cores C = {1, 2, . . . , n}.
1. Escolha uma cor para o vértice inicial
2. Para cada vértice não colorido, escolha uma cor que ainda
não foi atribuída a nenhum de seus vizinhos já coloridos.
3. Se todos os vértices foram coloridos parar, senão voltar ao
passo 2.
Heurística – Coloração em Grafos
2 5
Foram necessárias 5 cores!!! Esse é um grafo bipartido e o seu numéro cromático é 2
Grafos - Representação Computacional
Matriz de Adjacência:
Desvantagem: requer maior espaço para armazenamento
Vantagem: Indica rapidamente se existe uma aresta conectando dois
vértices
Melhor escolha para representar grafos densos (|E| ≈|V|2)
Grafos - Representação Computacional
Lista Encadeada:
Desvantagem: para determinar se uma aresta está na lista e necessário
percorrer todas as adjacências
Vantagem: requer menor espaço para armazenamento
Melhor escolha para representar grafos esparsos (|E|<<|V|2)
Nesta aula:
1. Estudamos algoritmos simples para resolver
problemas em grafos
2. Discutimos heurísticas gulosas para o PCV e
para o problema de coloração em grafos
3. Analisamos formas de representar grafos
usando no computador
Exercícios
1. Represente os grafos a seguir usando lista encadeada e matriz de adjacência
G1
G2
Exercícios
2. Aplique o algoritmo do vizinho mais próximo para resolver o problema do
caixeiro viajante no grafo a seguir.
Qual a distância percorrida obtida usando essa heurística? Compare com o
valor obtido usando um algoritmo de força bruta.
Em que circunstâncias devemos escolher uma heurística para resolver o
problema?
Próxima Aula
Materiais indicados para estudo para fixar o
conhecimento