Блог

Должна ли матрица смежности задачи коммивояжера быть симметричной? Каковы проблемы, если он асимметричен?

Это зависит от контекста вашей проблемы (например, если у вас улицы с односторонним движением, тогда ориентированный асимметричный граф имеет больше смысла). Интересно, что асимметричный случай фактически эквивалентен симметричному случаю за счет удвоения количества узлов (источник: https://optimization.mccormick.northwestern.edu/index.php/Traveling_salesman_problems#Classifications_of_the_TSP).