cela pourrait être une question un peu stupide, mais quelle est la différence exacte dans la résolution de TSP et ATSP. J'ai toujours pensé que dans ATSP, il fallait calculer le retour (puisque la matrice d'entrée est asymétrique). Par conséquent, le chemin d'accès à ATSP est deux fois plus long que le protocole TSP. Ai-je raison? Je comprends que c'est une question très simple, mais le doute est entré dans mon esprit. Merci.Différence entre ATSP et TSP
Un ATSP est un TSP avec asymétrique distances. Étant donné un TSP avec des emplacements A, B, C, D, E pour lesquels la distance de A à B est égale à 100, la distance de B à A sera également de 100. Pour un ATSP, cela n'est pas vrai: la distance de B à A pourrait être de 120 à la place.
Un vrai FST wold en utilisant une voiture ou un camion est toujours un ATSP parce que conduire du mauvais côté de la route est illégale. Traiter un ATSP comme un TSP et résoudre ce TSP de manière optimale, will not result in the optimal solution for that ATSP.
Merci pour votre réponse, pourriez-vous s'il vous plaît conseiller sur ce qui est la diffrence dans l'œuvre d'un algorithme glouton simple? Par exemple. Disons que nous avons une matrice comme X 2 3 5 X 6 2 1 X. Et une matrice symétrique du coin supérieur. quelle serait la différence? – Greenmachine
La plupart des algorithmes gloutons ne reposent pas sur la symétrie du TSP, donc pas de différence, tant que votre code sépare nettement 'a.getDistanceTo (b)' de 'a.getDistanceFrom (b)'. –
Merci Geoffrey. D'une certaine façon, cela n'était pas clair pour moi. – Greenmachine