Que abordagem produz a turnê mais curta no problema TSP: vizinho mais próximo ou algoritmos genéticos?

Question

Nos últimos dias tenho notado algumas web locais que solução TS demonstrada utilizando algoritmos genéticos.

Qual é a abordagem produz a turnê mais curta no problema TSP:? Vizinho mais próximo ou algoritmos genéticos

Answer 1

Uma vez que nem técnica garante uma solução ótima, sua milhagem pode variar. Com um pouco de sorte, tanto técnica pode realizar-se a outra. Ambas as técnicas têm prós e contras.

vizinho mais próximo: + rápido, + simples, -normalmente não ideal

algoritmo genético: -slower, -mais complexos, + soluções tendência ideal ao longo do tempo

A grande diferença é que os algoritmos randomizados, como simulado de recozimento e algoritmos genéticos podem continuar a melhorar ao longo do tempo - quanto mais tempo você deixá-los correr, mais chances você tem para uma solução ótima (embora não há garantias).

Desde NN é rápido, não há nada que impeça você de combinando as técnicas. Run NN para encontrar uma solução de partida, possivelmente,-better-than-aleatória. Em seguida, alimentar essa solução em seu algoritmo genético e deixá-lo correr, desde que você achar mais adequado.

Se você estiver interessado em soluções óptimas, consulte a Lin-Kernighan heurística e Programação Linear . Ambos foram utilizados para encontrar soluções óptimas para grandes passeios, incluindo esta solução para um 85.900 city tour e uma 24978 cidade Suécia turnê .

O é um grande recurso.