Problema do vendedor viajante
Os problemas do caixeiro viajante residem em um caixeiro e em um conjunto de cidades. O vendedor deve visitar cada uma das cidades a partir de uma determinada (por exemplo, a cidade natal) e retornar à mesma cidade. O desafio do problema é que o caixeiro viajante precisa minimizar a duração total da viagem.
Suponha que as cidades sejam x 1 x 2 .....x n onde custa c eu j denota o custo de viajar da cidade x eu para x j . O problema do caixeiro viajante consiste em encontrar uma rota começando e terminando em x 1 que vai abranger todas as cidades com o custo mínimo.
Exemplo: Um jornalista entrega diariamente o jornal na área designada de forma que tenha que cobrir todas as casas da respectiva área com custo mínimo de viagem. Calcule o custo mínimo de viagem.
A área atribuída ao agente onde deverá deixar o jornal é mostrada na fig:
Solução: A matriz de adjacência de custos do grafo G é a seguinte:
custo eu j =
O passeio começa na área H 1 e então selecione a área de custo mínimo acessível em H 1 .
Marcar área H 6 porque é a área de custo mínimo alcançável a partir de H 1 e, em seguida, selecione a área de custo mínimo acessível em H 6 .
Marcar área H 7 porque é a área de custo mínimo alcançável a partir de H 6 e, em seguida, selecione a área de custo mínimo acessível em H 7 .
Marcar área H 8 porque é a área de custo mínimo alcançável a partir de H 8 .
Marcar área H 5 porque é a área de custo mínimo alcançável a partir de H 5 .
Marcar área H 2 porque é a área de custo mínimo alcançável a partir de H 2 .
Marcar área H 3 porque é a área de custo mínimo alcançável a partir de H 3 .
Marcar área H 4 e então selecione a área de custo mínimo acessível em H 4 é H 1 .Então, usando a estratégia gananciosa, obtemos o seguinte.
4 3 2 4 3 2 1 6 H<sub>1</sub> → H<sub>6</sub> → H<sub>7</sub> → H<sub>8</sub> → H<sub>5</sub> → H<sub>2</sub> → H<sub>3</sub> → H<sub>4</sub> → <sub>H<sub>1</sub></sub>.
Assim, o custo mínimo de viagem = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matróides:
Uma matróide é um par ordenado M(S, I) que satisfaz as seguintes condições:
- S é um conjunto finito.
- I é uma família não vazia de subconjuntos de S, chamados de subconjuntos independentes de S, tais que se B ∈ I e A ∈ I. Dizemos que I é hereditário se satisfaz esta propriedade. Observe que o conjunto vazio ∅ é necessariamente um membro de I.
- Se A ∈ I, B ∈ I e |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>
Dizemos que uma matróide M (S, I) é ponderada se houver uma função de peso associada w que atribui um peso estritamente positivo w (x) a cada elemento x ∈ S. A função de peso w se estende a um subconjunto de S por soma :
w (A) = ∑<sub>x∈A</sub> w(x)
para qualquer A ∈ S.
