Мне нужна хорошая эвристическая функция для звезды для перьевого плоттера / TSP, где каждое состояние моей системы имеет:
- Путь, пройденный
- Точкагде ручка находится в данный момент
- Перо вверх / вниз
«Перо вверх / вниз» относится к состоянию, в котором вы нарисовали линию только тогда, или вы двигаетесь кточка, чтобы начать новую строку.
Учитывая, что мне нужно пройти через каждую точку на каком-то этапе, конечной целью может быть любая точка, делающая невозможной использование любой эвристики, которую я обнаружил в Интернете.должным образом.Я пробовал следующее, но не смог получить хорошую эвристику из него:
(г (х), деленное на сумму общего пройденного расстояния) * количество оставшихся состояний (при условии, что вы чередуетесьмежду рисованием линии или перемещением в новую точку, чтобы нарисовать линию)
Я также пытался
евклидово расстояние между текущим состоянием и состоянием цели (найти ближайшее возможное состояние цели).
Это не работает, поскольку дает эвристику 0, поскольку любое состояние / точка может быть состоянием цели