Минимальная структура данных для предотвращения повторения 2D-сетки путешественника

Question

Извините, если это дубликат какого-либо потока, но я действительно не знаю, как описать вопрос.

Мне интересно, какова минимальная структура данных , чтобы предотвратить2D-сетка путешественника от повторения (то есть до того момента, когда она уже путешествовала) .Путешественник может двигаться только горизонтально или вертикально на 1 шаг каждый раз.Для моего особого случая (ниже) 2D-сетка на самом деле представляет собой нижний левый треугольник , где одна координата никогда не превышает другую.

Например, в случае 1D это можно сделать простозаписав направление последнего путешествия.Если направление изменяется, оно повторяется.

Для 2D-случая это становится сложным. Самым тривиальным способом было бы создание списка, записывающего пройденные ранее точки, но мне интересно, есть ли более эффективные способы сделать это?

Я реализую более или менееменьше алгоритма «4 пальца» для 4-суммы , где 2 пальца в середине движутся в двух направлениях (а именно i, j, k и l):

  i=>    <=j=>     <=k=>       <=l
1 2 3 ... 71 72 ... 123 124 ... 201 202 203

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

РЕДАКТИРОВАТЬ

За эти дни я нашел 2 решения.Ни один из них не является идеальным решением этой проблемы, но они, по крайней мере, несколько пригодны для использования:

• Как упомянуто ниже @Sorin, одним из решений было бы сохранение массива битов, представляющего состояние всех ячеек.,Для примера с треугольной сеткой мы можем даже сжать массив, чтобы сократить стоимость памяти вдвое (хотя для вычисления позиции бита требуется k^2 время, где k - степень свободы, то есть 2 здесь. Стандартный массив будет использоватьтолько линейное время).

• Другим решением было бы прямое избегание путешествия назад.Настройте алгоритм так, чтобы j и k двигались только в одном направлении (это, вероятно, жадно).

Но все же, поскольку путешественник по 2D-сетке обладает хорошим свойством, чтоон перемещается вдоль оси 1 шаг каждый раз, мне интересно, есть ли более "специализированное" представление для этого вида движения.

Спасибо за вашу помощь!

Answer 1

Если вы ищете оптимальную сложность поиска, тогда лучше всего использовать хэш-сет.Вам нужна O (N) память, но все поиски и вставки будут O (1).

Если вы часто посещаете большинство ячеек, вы можете даже пропустить часть хеша и сохранить битовый массив.Это означает, что для каждой ячейки хранится один бит, и просто проверьте, равен ли соответствующий бит 0 или 1. Это намного более компактно в памяти (по крайней мере, 32x, один бит против одного целого, но, вероятно, больше, поскольку вы также пропускаете хранение некоторых внутренних указателей.до структуры данных, 64 бита).

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

Другие структуры, такие как BSP или Kd-деревья, также могут работать.Как только вы достигнете точки, где все будет свободным или занятым (игнорируя неиспользуемые ячейки в верхнем треугольнике), вы можете хранить всю эту информацию в одном узле.Это трудно рекомендовать из-за его сложности и того, что он, вероятно, также будет использовать O (N) память во многих случаях, но с большей константой.Также все проверки будут O (logN).