Для класса у нас есть сетка и куча квадратов на сетке, которые мы должны обнаружить и перейти к ней.Мы начинаем с (0,0).Мы сканируем крошечные области сетки за раз (по причинам, связанным с нашей структурой данных, это обязательно), и когда мы обнаруживаем квадраты, которые нам нужно пройти, а затем мы путешествуем.В сетке 32 локации, но нам нужно проехать только 16 из них, и как можно быстрее (мы подбегаем к ним кого-то другого).
Алгоритм Дейкстры найдет кратчайший путь из нашего текущегоместо для нашего следующего местоположения.Однако это не оптимально, потому что наше следующее местоположение может быть очень далеко от этого места.Было бы более полезно, если бы мы могли каким-то образом вычислить плотность местоположений при сканировании, а затем решили перейти в очень плотное место и перемещаться по всем местоположениям в этой области.
Существует ли алгоритм, который лучше всего подходитдля такой ситуации?Я знаю, что жадная эвристика не оптимальна.A * и Dijkstra - это те, о которых мы думали поначалу, но мы надеемся, что есть совершенно другое решение.
PS К сожалению, это делается в сборке.