Posted on: July 13, 2022 10:27 AM
Posted by: Renato
Categories: PHP algoritimo developer webdev
Views: 1446
Algoritmos Caixeiro Viajante
## Objetivos ##
* Desenvolvimento de um sistema, implementando o Problema do Caixeiro Viajante.
* [Problema do Caixeiro Viajante](https://pt.wikipedia.org/wiki/Problema_do_caixeiro-viajante)
> O Problema do Caixeiro Viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem. Ele é um problema de otimização NP-difícil inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível.
> Nos anos de 1800, problemas relacionados com o PCV começaram a ser desenvolvidos por dois matemáticos: o escocês William Rowan Hamilton e o britânico Thomas Penyngton Kerkman. A forma geral do PCV parece ter sido, pela primeira vez, estudada por matemáticos nos anos de 1930 em Harvard e Viena. O problema foi posteriormente estudado por Hassler Whitney e Merril Flood em Princeton. Exceptuando pequenas variações ortográficas, como traveling vs travelling ou salesman vs salesman's, o nome do problema ficou globalmente conhecido por volta do ano 1950.
> O problema do caixeiro-viajante consiste na procura de um circuito que possua a menor distância, começando numa cidade qualquer, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial (Nilsson, 1982).
> O "problema do caixeiro-viajante" é um problema de otimização combinatorial, em que um vendedor deve começar em uma cidade e retornar a essa cidade depois de viajar para todas as diferentes cidades em uma lista. A questão é saber qual é o caminho mais eficiente entre todos os pontos - o problema se torna exponencialmente mais difícil conforme cada cidade é adicionada à lista.
> É claro que a agenda de um vendedor ou entregador é apenas um exemplo do problema, e, além das questões de logística, há uma infinidade de situações correlatas que os computadores precisam resolver o tempo todo.
- https://gitlab.com/cpdrenato/php-algoritmo-caixeiro-viajante
* Renato Lucena - 2022
Donate to Site
Renato
Developer