Olá meus amigos nerds, mesmo estando com um pouco de calos nos olhos devido ao jogo de ontem da seleção, estou aqui hoje para resolver um probleminha com vocês.
Hoje vamos falar do problema 2616. Caixeiro-Viajante B que nos pede para traçar a rota de um caixeiro viajante de modo que ele gaste o mínimo possível com passagens de trem para visitar todos os seus clientes. Mais especificamente, o problema só nos pede o valor mínimo gasto com as passagens.
Solução
O primeiro ponto a destacar, é que esse não é o clássico problema do caixeiro viajante, tão estudado quando se fala em problemas NP. Ainda bem, já que isso facilita bastante as coisas.
Como em outros problemas que já resolvemos aqui, vamos pensar em uma modelagem usando grafos. Nesse problema isso é bem simples, as cidades seriam os vértices e as ferrovias as arestas.
O problema nos afirma que há apenas um caminho ligando cada par de cidades, então nosso grafo é, na realidade, uma árvore. Cada cidade em que há um cliente do caixeiro precisa ser visitada, isso significa que cada ferrovia que o caixeiro passar será usada 2 vezes (ida e volta).
A forma de minimizar o gasto com passagens é não percorrer uma ferrovia mais do que uma duas vez (ida e volta), já que há apenas 1 caminho entre qualquer par de cidades. Isso significa que, cada vez que o caixeiro chegar a uma "encruzilhada" que tem caminhos para mais do que uma cidade ele deve visitar a primeira delas, voltar até a encruzilhada e partir dali direto para a próxima cidade. Observe que o que acabei de descrever é simplesmente percorrer o grafo em uma busca em profundidade.
Problema resolvido? Não! Pode haver cidades que não possuem clientes do caixeiro e que não estão no caminho de outras cidades, ou seja, que não precisam ser visitadas, mas que provavelmente seriam contadas caso você fizesse uma busca em profundidade simples. Mas isso é simples de resolver. Para contornar esse pequeno detalhe basta fazer a busca em profundidade primeiro (enraizando a árvore pelo nó que representa a cidade inicial do caixeiro) e ir percorrendo os caminhos das cidades de destino para a raiz (ou seja, fazendo o caminho oposto), marcando as arestas para que elas não sejam contadas novamente.
Nenhum comentário:
Postar um comentário