TSP для неориентированного графа сетки с наименьшим количеством поворотов
Мне нужно найти маршрут через график сетки, который посещает каждую вершину хотя бы один раз, начиная и заканчивая в одной и той же фиксированной точке. Маршрут должен иметь наименьшее количество поворотов.
Я пытался решить эту проблему с помощью генетического алгоритма (GA), но мне сказали, что это немного излишне на графике сетки.
Поэтому мой вопрос: есть ли другие алгоритмы, которые могут более эффективно решить эту проблему на сеточном графе? Я не ищу точное решение, так как знаю, что проблема NP-трудная. Приближение будет делать.