Алгоритм: прохождение всех элементов массива с ограниченным ограничением перемещения

Question

Привет.

У меня есть двумерный массив размером [N] [N], который будет представлять прямоугольную область / карту с N строками и N столбцами.

Допустим, я выбираю середину в качестве отправной точки (или в любом другом месте), я хочу пройтись по всем элементам с ограничением перемещения только X раз, прежде чем придется возвращаться к начальной точке. Затем я смогу пройти по пути, по которому пошел, но это потратит впустую ход.

Мне просто интересно, есть ли конкретный алгоритм для этой проблемы, чтобы я мог сравнить с моим текущим способом выполнения, который просто хранит ходы, которые я уже сделал. (довольно грязно)

Заранее спасибо.

Answer 1

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

Я пытался сделать свой ответ более четким, для каждого хода делайте следующее.

1. Определите ценность целей
   • Определите количество шагов, необходимых для достижения цели, используя алгоритм поиска пути .
   • Рассчитать необходимое количество ходов (Math.Ceil(steps / stepsPerTurn))
   • Определить объект с наибольшим значением за наименьшее количество витков.
   • Отправляйся к этой цели.

Answer 2

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

Начните с текущей точки и идите прямо до стены. Спустись, иди налево. Продолжайте зигзагообразно взад и вперед. Если вы дойдете до дна, начните все сначала и зигзагообразно закройте верхнюю половину аналогичным образом.

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

Этот алгоритм не оптимален, но, скорее всего, это 10 строк кода и 2 переменные.