Проблема: Учитывая сетку (NxN), начальный узел и набор целевых узлов, найдите кратчайший путь, который проходит через все узлы в данном наборе. Вы можете проходить через один и тот же узел более одного раза, если он дает кратчайший путь.
Я должен использовать алгоритм A * с минимальным остовным деревом в качестве эвристики, но я не уверен, как.
IЯ изучал подобные проблемы, и часто люди обсуждают проблему TSP, однако я не думаю, что это то же самое.
Я думал о том, чтобы найти кратчайший путь от каждого из узлов (начало и цель) друг к другу. и затем запускаю некоторый алгоритм MST, чтобы найти путь, однако я не думаю, что это очень эффективно, и он не использует A *, как я упоминал.