Алгоритм поиска кратчайшего расстояния, охватывающего наименьшее количество ячеек

Question

Я разрабатываю систему для поиска кратчайшего маршрута, охватывающего наименьшее количество ячеек. Предположим, что плоскость разделена на прямоугольные ячейки. Какой будет наиболее подходящий алгоритм для этого. Я просто ищу начальный старт, а не правильный код или реализацию.

Answer 1

Вы имеете дело с shortest path problem, в невзвешенном графике (вершины ячейки в сетке, а ребра возможные ходы от одной клетки к другой)

• Самый простой подход является простым BFS - что находит самый короткий путь от источника ко всем целям (в невзвешенных графах).
  Этот алгоритм довольно прост и итеративно «обнаруживает» ближайшие узлы, все узлы расстояния 1, затем расстояния 2, ...
• Оптимизация использует bi-directional search. Здесь вы можете использовать единый источник и единую цель, выполняя BFS с обеих сторон, эффективно уменьшая количество узлов, которые вам нужно разрабатывать.
• Еще одна оптимизация может заключаться в использовании A* Search Algorithm с допустимой эвристической функцией manhattan distances.
  В A * Search вы можете воспользоваться тем, что график не является произвольным графом, а сеткой, и вы можете оценить расстояние от одного узла до другого, основываясь на своих местоположениях в сетке. Алгоритм будет использовать эти оценки, чтобы быстрее найти оптимальный путь.

Примечание. Все алгоритмы, которые я предложил найти, кратчайший путь, разница в том времени, когда потребуется их найти.