Как найти один гамильтонов путь в кубе ((2n) ^ 3)? - PullRequest
Новая
       9

Как найти один гамильтонов путь в кубе ((2n) ^ 3)?

2 голосов
/ 23 ноября 2011

Я решаю проблему acm-icpc, своего рода теорию графов.

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

куб существует в пространстве [0, 2n] x [0, 2n] x [0, 2n], и n может быть 2 <= n <= 50. </p>

мы должны найти один гамильтонов путь, когда я играю на двух позициях, начиная с A до B.

и выведите все пути (1 0 1 -> 1 0 3 -> .... -> 3 1 4).

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

как я могу найти гамильтонов путь в общем случае?;

Ответы [ 2 ]

3 голосов
/ 23 ноября 2011

Похоже, код Грея * проблема 1002 *, в частности n-арный код Грея .

Коды Грея - это гамильтоновы циклы, но вы ищете гамильтонову траекторию с конечными вершинами A и B. Я не уверен, но, возможно, Однотонные коды Грея могут помочь. Если вершины куба можно разбить на V_i, чтобы V_0 = {A}, V_n = {B}, то конструкция в статье может решить проблему.

Редактировать: На странице Википедии есть ссылка на черновик Кнута о поколении n-кортежей из Art Volume 4A.

1 голос
/ 23 ноября 2011

Проблема в том, что NP завершена, и вам нужно перебрать все возможные пути. Смотрите здесь: Алгоритмы для нахождения количества гамильтоновых путей в графе . Однако в вашей задаче есть ярлык, потому что это куб рубика, а обход кода серого куба рубика - это гамильтонов путь. Существует 6 способов обхода серого кода кубического рубика. Например, если у вас есть октри, и вы нашли гамильтонову траекторию, скорее всего, вы нашли кривую заполнения пространства, уменьшающую 3d до 1d сложности. Затем вы можете отсортировать путь сверху вниз или снизу вверх. Если у вас есть 5 других кривых заполнения пространства, у вас могут быть другие списки. Вот ссылка, которая объясняет разницу между эйлеровым путем и гамильтоновым путем: Разница между гамильтоновым путем и эйлеровым путем . Вот пример кривой Гильберта http://www.tiac.net/~sw/2008/10/Hilbert/, в которой используется двоично-отраженный код, а не n-арный код или монотонный серый код.

...