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 x1x2.....xnonde custa ceu jdenota o custo de viajar da cidade xeupara xj. O problema do caixeiro viajante consiste em encontrar uma rota começando e terminando em x1que vai abranger todas as cidades com o custo mínimo.
ml em onças
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:
fontes para gimp
custoeu j=
O passeio começa na área H1e então selecione a área de custo mínimo acessível em H1.
Marcar área H6porque é a área de custo mínimo alcançável a partir de H1e, em seguida, selecione a área de custo mínimo acessível em H6.
Marcar área H7porque é a área de custo mínimo alcançável a partir de H6e, em seguida, selecione a área de custo mínimo acessível em H7.
entrada java
Marcar área H8porque é a área de custo mínimo alcançável a partir de H8.
Marcar área H5porque é a área de custo mínimo alcançável a partir de H5.
Marcar área H2porque é a área de custo mínimo alcançável a partir de H2.
Marcar área H3porque é a área de custo mínimo alcançável a partir de H3.
Marcar área H4e então selecione a área de custo mínimo acessível em H4é H1.Então, usando a estratégia gananciosa, obtemos o seguinte.
são exemplos de modelos
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.