Блог пользователя Ripatti

Автор Ripatti, 15 лет назад, По-русски
Введение
После окончания Codeforces Beta Round #11 несколько участников захотели почитать что нибудь о задачах, похожих на задачу D этого раунда. Автор статьи, в целях помочь этим участникам, попытался найти подобную информацию, однако был удивлен, что ничего путного в интернете нет. Неизвестно, то ли автор плохо искал, то ли это действительно так, однако (на всякий случай), он решил написать собственную статью на эту тему.

В некотором смысле эту статью можно рассматривать как разбор задачи D 11го бета раунда.



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

Динамика по подмножествам
Рассмотрим множество элементов, занумерованных от 0 до N - 1. Каждое подмножество этого множества можно закодировать последовательностью битов длины N (эту последовательность будем называть маской). Если i-й бит маски равен 1, то i-й элемент входит в подмножество, иначе - нет. Например, маска 00010011 означает, что в подмножестве находятся элементы 0, 1 и 4 из множества [0... 7]. Всего получается 2N масок, задающих 2N подмножеств. Каждая маска по сути является целым числом, записанном в двоичной системе счисления.

Метод состоит в том, чтобы каждой маске (а значит и каждому подмножеству) сопоставлять какое либо значение и, на основе уже просчитанных значений для некоторых масок, получать значения для других масок. Как правило, в процессе просчета из текущего подмножества A извлекается один элемент всеми допустимыми способами и из полученных подмножеств A1', A2', ... , Ak' получается значение для A. Однако для этого все значения для Ai' уже должны быть вычислены. Поэтому требуется установить порядок, в котором будут просматриваться маски. Несложно понять, что перебор масок в порядке возрастания чисел, которыми и являются эти маски, нам подойдет.

Для дальнейшего повествования примем следующие обозначения:
bit(i, mask) - i-й бит маски mask
count(mask) - количество битов 1 в маске mask
first(mask) - наименьший номер бита 1 в маске mask
(a?b: c) - возвратить b если выполняется a, или возвратить c в противном случае.
Элементами множества будут являться вершины графа. Для простоты мы будем считать, что граф является неориентированным. Модификация нижеприведенных алгоритмов для случая ориентированного графа предоставляется читателю.

1. Нахождение кратчайшего гамильтонова пути
Пусть в графе G = (V, E) n вершин и каждое ребро имеет некоторый вес d(i, j). Необходимо найти гамильтонов путь, сумма весов по ребрам которого минимальна.

Пусть dp[mask][i] обозначает длину кратчайшего гамильтонова пути подмножества вершин mask, заканчивающегося в вершине i.

Динамика считается по следующим соотношениям:
dp[mask][i] = 0, если count(mask) = 1 и bit(i, mask) = 1;
, если count(mask) > 1 и bit(i, mask) = 1;
dp[mask][i] = ∞ во всех остальных случаях.

Теперь искомая минимальная длина пути . Если pmin = ∞, то гамильтонова пути в графе, увы, нет. Восстановить сам путь несложно. Пусть минимальный путь заканчивается в вершине i. Тогда j ≠ i, для которого , является предыдущей вершиной пути. Теперь удалим i из множества и только что описанным способом найдем вершину предыдущую к j. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.

Данное решение требует O(2nn) памяти и O(2nn2) времени.

2. Нахождение количества гамильтоновых путей
Пусть теперь у нас есть невзвешенный граф G = (V, E). Модифицируем предыдущий алгоритм. Пусть dp[mask][i] теперь означает количество гамильтоновых путей подмножества mask, заканчивающихся в вершине i. Динамика перепишется следующим образом:
dp[mask][i] = 1, если count(mask) = 1 и bit(i, mask) = 1;
, если count(mask) > 1 и bit(i, mask) = 1;
dp[mask][i] = 0 во всех остальных случаях.

Ответом будет число .

Решение требует O(2nn) памяти и O(2nn2) времени.

3. Нахождение количества простых цепей
Посчитаем динамику, указанную в предыдущем пункте. Ответом будет являться число . Коэффициент 1 / 2 необходим, поскольку каждую цепь мы учитываем 2 раза - в одном и обратном направлении. Так же следует отметить, что тут учтены только пути длины хотя бы 1. При желании можно к ответу добавить n путей длины 0.

Данное решение требует O(2nn) памяти и O(2nn2) времени.

4. Проверка существования гамильтонова пути

Тут можно обойтись решением 2, заменив сумму на побитовое ИЛИ. Тогда dp[mask][i] будет содержать булево значение - существует ли в подмножестве mask гамильтонов путь, заканчивающийся в вершине i. Сама динамика будет такая:
dp[mask][i] = 1, если count(mask) = 1 и bit(i, mask) = 1;
, если count(mask) > 1 и bit(i, mask) = 1;
dp[mask][i] = 0 во всех остальных случаях.

Это решение, как и решение 2, требует O(2nn) памяти и O(2nn2) времени. Эту оценку можно улучшить, если изменить динамику следующим образом.

Пусть dp'[mask] хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве mask, заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: dp'[mask] будет равно . Для графа G выпишем n масок Mi, для каждой вершины задающие множество вершин, которые связаны ребром в данной вершиной. То есть .

Тогда динамика перепишется следующим образом:
dp'[mask] = 2i, если count(mask) = 1 и bit(i, mask) = 1;
, если count(mask) > 1;
dp'[mask] = 0 во всех остальных случаях.

Особое внимание следует уделить выражению . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве mask без вершины i, а вторая - подмножество вершин, связанных с i ребром. Если эти множества пересекаются хотя бы по одной вершине (их and не равен 0), то, как нетрудно понять, в mask существует гамильтонов путь, заканчивающийся в вершине i.

Окончательная проверка состоит в сравнении dp[2n - 1] c 0.

Это решение использует O(2n) памяти и имеет асимптотику O(2nn).

5. Нахождение кратчайшего гамильтонова цикла
Поскольку нам безразлично с какой вершины начинаться цикл, пусть он начинается с вершины 0. Далее, воспользуемся решением 1 для подмножества вершин, видоизменив соотношения следующим образом:
dp[1][0] = 0;
, если i > 0, bit(0, mask) = 1 и bit(i, mask) = 1;
dp[mask][i] = ∞ во всех остальных случаях.

Таким образом, dp[mask][i] будет содержать длину кратчайшего гамильтонова пути от вершины 0 до вершины i.

Искомый минимум нужно будет выбирать по формуле . Если полученный минимум равен , то искомого цикла не существует. Искомый цикл восстанавливается аналогично решению 1.

6. Нахождение количества гамильтоновых циклов
Используя идеи решений 5 и 2, можно получить динамику, считающую количество гамильтоновых циклов за время O(2nn2), использующее O(2nn) памяти.

7. Нахождение количества простых циклов
Пусть dp[mask][i] означает количество гамильтоновых путей в подмножестве вершин mask, начинающихся в вершине first(mask) и заканчивающихся в вершине i. Переход динамики выглядит так:
dp[mask][i] = 1, если count(mask) = 1 и bit(i, mask) = 1;
, если count(mask) > 1, bit(i, mask) = 1 и i ≠ first(mask);
dp[mask][i] = 0 иначе.

Ответом будет являться сумма .

Это решение за время O(2nn2) и память O(2nn).

8. Проверка существования гамильтонова цикла
Модифицируем решение 5 и, воспользовавшись приемом, описанном в решении 4, получим решение для этой задачи за время O(2nn) и память O(2n).

Упражнения
CFBR11D
CCTOOLS

P.S. Эта статья в будущем, возможно, будет дополняться и исправляться. Автор будет благодарен за пополнение раздела упражнений ссылками на задачи из архивов, а так же на найденные ошибки и неточности.
  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

15 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
http://www.spoj.pl/problems/ASSIGN/

For example
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    спасибо, задача очень понравилась)) действительно, дп по подмножествам, только вот без графов и маршрутов в них. поэтому пока не знаю, стоит добавлять ее в статью или нет.

    пусть пока повисит тут. потом, возможно, добавлю. возможно в новый раздел:)
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо, очень содержательно!

Боюсь наврать, но кажется. что у задачи подсчёта количества гамильтоновых путей есть решение за O (2n/2 poly (n) ).
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    м... интересно было бы посмотреть на это решение)) я лично не знаю такого

    только, боюсь, оно большое, страшное и представляет из себя чисто теоретический интерес:) то есть для олимпиад совершенно непригодное
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Шутка, вру. Я имел в виду подсчёт количества клик.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Nice tutorial. You could also add an explanation on how to count hamiltonian circuits on a grid of size n x m with (n <= 7 and m <= 10^9) for example which is also fairly classical.
  • 15 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Counting hamiltonian circuits on a grid is quite different from problems which was viewed there. In article I view foremost masks over subsets and paths in graphs. But in your problem motzkin words and matrix multiplication are used:)

    Maybe I will view your problem in fiture article:)
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    CouDo you have a reference to such a problem?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    If the size of grid is 12*12 . Can we use DP over Subsets
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Огромное спасибо за прекрасную статью!
У меня только одна мелкая корректировка, в п.5 вместо этого:

по-моему, правильнее будет вот это (особенно, если граф ориентированный):
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    дельное замечание)) поправил
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ещё раз боюсь показаться мелочным :), но вместо ребра все-таки должно быть (раз мы начали в 0, то и закончить цикл должны в 0, а не в i); также первую d надо заменить на dp.
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        ну, вообще говоря, (i,0) или (0,i) - без разницы... граф не ориентированный. а вот d на dp надо поправить
        • 15 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я забыл, что вы для простоты рассматриваете неориентированный граф. Но если есть благоприятная возможность обобщить алгоритм на ориентированный граф путем перестановкой всего двух символов, то почему бы ею не воспользоваться?
        • 15 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Вот ещё по пятому пункту. Второе условие в определении dp "если i > 1, count(mask) > 1, bit(0, mask) = 1 и bit(i, mask) = 1" нужно заменить на "если i > 0, count(mask) > 1, bit(0, mask) = 1 и bit(i, mask) = 1", а ещё лучше упростить до "если i > 0, bit(0, mask) = 1 и bit(i, mask) = 1".
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вы говорите, что в интернете нигде про это не нашли. А сами про это откуда узнали, со сборов?? 
Может кинете какую-нить ссылку на статьи в стиле "how to count hamiltonian circuits on a grid of size n x m"? Просто я о таких вещах слышу в первый раз, и интересно может есть ещё что-нибудь полезное, чтобы знать а не выводить самому при необходимости.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    узнал я этот прием на разборе городской школьной олимпиады по информатике классе в 9 или 10)) дело в том, что задачи составлял товарищ, который на данный момент имеет бронзу с финала ACM ICPC, и он немножко переборщил со сложностью задач:D в итоге первое место имело ну очень мало баллов от максимума (подробностей уже не помню). Ну, потом еще кое где еще встречал задачи на ту же идею (сборы и, вроде бы, открытый кубок).

    про циклы на сетке где-то выше уже была ссылка:
    http://www.cs.ust.hk/mjg_lib/Library/Kwong_Ham_94.pdf
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ну я это видел.. вы меня не так поняли) .. я хотел спросить может есть какой-нить архив полезных статей? как например эта. Для этой я ссылку видел
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        в плане именно таких даже и не припомню)) идея довольно редкая, думаю, вряд ли можно найти про это больше статей. весь стандарт (в том числе довольно крутой) можно почерпнуть из Кормена, e-maxx и лекций MIT. все остальное имхо можно почерпнуть разве что через опыт решения задач, лазаньем по тематическим форумам или от тех людей, которые это знают)) то есть не через статьи.

        конечно, если вдруг и существует подобный архив, мне самому было бы интересно на него взглянуть:)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Привет всем.
Находил в Интернете  по теме "дп по профилю":
1. статью "Василевский Б. - Динамическое программирование по профилю"
2. книгу "Д. Павлова - Лекции по информатике"

статья (1.) отличная, но мне что-то показалось что там мало написано про "ДП по изломанному профилю", может ли кто нибудь дать ссылку (хотя бы на английском,я не знаю как это на английском будет )? (именно про ДП по изломанному профилю).

и еще можно ли за полином памяти или времени решать подобные задачи?

спасибо.


  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    да, когда я тогда сканировал инет, только статью Василевского и нашел)) где-то в обсуждении 11го раунда я же на эту статью и приводил ссылку))

    про дп по ломаному профилю я бы тоже хотел почитать если кто поделится ссылкой:)

    по поводу можно ли решать за полином по времени - это вопрос задачи P vs NP. поэтому еще никто этого не знает. вот недавно появилась попытка доказать что таки P!=NP)) сами же задачи, которые я рассмотрел, относятся к классу NP в общем случае.

    если нужен полином по памяти - backtracking вам в руки:) правда время выполнения тут несколько увеличивается и остается экспоненциальным.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Глупый вопрос - а это очевидно, что все эти задачи NP?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Совсем не глупый вопрос :)
        Многие задачи принадлежат классу #P что конечно не тоже самое что NP.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Это да, но я имел в виду даже не задачи подсчёта, а, например, поиск кратчайшего гамильтонова пути.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Поиск кратчайшего гамильтонова пути это NP.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          упс... беру свои слова обратно:D я не очень хорошо разбираюсь в классах сложности задач. всю жизнь делил все задачи только на классы P и NP.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
http://www.codechef.com/problems/TOOLS
is an example problem for part 5.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как найти гамильтонов цикл в графе Дирака??? В графе 1000 вершин.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    сначала расположим все точки по кругу первым попавшимся образом. a->b будет обозначать, что b следующая по обходу по часовой стрелке после a.

    будем итеративно выполнять следующий процесс:
    для пары соседних точек A->B, не соединенных ребром найдем такую пару C->D, что имеются ребра AC и BD. такая пара всегда найдется из-за того, что граф Дирака (ну, там по принципу Дирихле можно доказать). теперь все точки от B до D перезаписываем в обратном порядке (дугу как бы переворачиваем).

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

    итого - алгоритм за O(n*n), для 1000 вершин все замечательно:)
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

      в предыдущий комментарий, вероятно, закралась опечатка.

      правильно "теперь все точки от B до C перезаписываем в обратном порядке (дугу как бы переворачиваем)."

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could you please further explain the recurrence in the first example (finding a shortest Hamiltonian walk)?

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

The following paper is potentially useful as reference:

"A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp, 1962. [citation, download]

It contains lots of preliminary analysis and at least the DP approaches described in 1. and 5. of your post. I believe the algorithm is actually called "Held–Karp algorithm" in academic literature, but it was described independently by Bellman et al. in another paper.

A list of optimal algorithms for TSP with better runtime complexity can be found here.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In 4th section's second dp formulation second part, the condition stated is count(mask)>1 only. Isn't bit(mask, i) == 1 condition should also be included?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anybody give me link to its implemented code for any of the above part. Rest I got stuck at bit masking in implementation. Thanks in advance whoever will give link.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    My solution for task D of CF beta round 11.

    Btw,am i the only one who can't see the solution of others in this contest?i can't even open my solution.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      me too, something is wrong today, I can't open submission code, including myself, now I can only open my "official" submissions.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes also just encountered this problem. Why I try to open my own solution I get "You are not allowed to view the requested page" error.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I actually have theory now for why this is. I think problem D might have been used in the VK Cup Finals — Trial Contest, and so they blocked solutions so we could not see submission from people in that contest.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

In first Section, consider a graph with only two vertices and one edge of weight say w then the answer computed by the process, comes to be w but expected asnwer is 2*w as for a hamiltonian walk the starting and ending vertices must be same.

»
8 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

In the 7th section, how are those paths included in the answer where we use vertices v < first(mask). This means, if our bit representation of mask is 1101000, and we want to count no. of paths starting at first(mask)=3(3rd bit, 0-based indexing from right to left) and ending at vertex v=5(0-based indexing from right to left), how will paths like the one starting from vertex 3 to vertex 5 with vertex 0 on the way(and similar) be counted if we use the dp meaning given in section 7?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In a hamiltonian walk the vertices might repeat. On the other hand, in a simple path repetition of vertices is not allowed. How is it that using the same dp for ques 3 which was used for ques 2 works? Any insights would be highly appreciated.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Isn't checking for hamiltonian path obvious when atleast 2 nodes are attached to each other?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great Post. Cleared all the doubts regarding "Hamiltonian". Thanks a lot.

»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

in problem 2, is the graph complete?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think in the first two problem author is talking about Hamiltonian path, not about Hamiltonian walk. Please correct me if I am wrong. Thanks!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как в сэмпле задачи 11D - Простая задача получилось 7 простых циклов?

1-2-3

1-2-4

1-3-4

2-3-4

1-2-3-4

где ещё два цикла?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Link to HackerEarth practice problems.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I noticed a minor issue(maybe typo) in the transition of the DP state in P4 : Checking the existence of the Hamiltonian walk in $$$O(2^{n} \cdot n)$$$, since I'm writing a comment anyway let me explain with a little more detail which smol idea help us optimize it from $$$O(2^{n} \cdot n^2)$$$ to $$$O(2^{n} \cdot n)$$$ .

Idea — Since we only need a binary (yes/no) answer for each vertex $$$j$$$ in $$$mask$$$ to see whether it can reach $$$i$$$, we can use mask $$$X$$$ to store all that information instead of using $$$j$$$ (which is iterating over all $$$n$$$), this saves us extra $$$O(n)$$$.

Def. — $$$dp'[mask]~=~X$$$, $$$X$$$ is a subset of the $$$mask$$$, where the set-bits in $$$X$$$ indicate the vertices that allow for a successful Hamiltonian Walk across $$$mask$$$ which ends at the set-bit vertex.

Transition — For $$$i$$$-th bit that is set in $$$mask$$$ , we need to know whether $$$dp'[mask \oplus 2^{i}]$$$'s successful Walks can reach $$$i$$$-th vertex, for that we need to precalculate $$$M_{i}$$$, $$$M_{i} = $$$ mask made of vertices that are incident to $$$i$$$. If $$$M_{i}$$$ and $$$dp[mask \oplus i]$$$ share vertices we can extend our successful Walk towards $$$i$$$ and set $$$dp'[mask]$$$'s $$$i$$$-th bit as $$$1$$$.

$$$ dp'[mask] = \displaystyle \sum_{i=0}^{n-1} 2^{i} ~ \cdot ~ (( ~ dp'[mask \oplus 2^{i}] \& M_{i} ~) ~~ \& \& ~~ (mask \& 2^{i}) ~ ? ~ 1 : 0)$$$

Base — $$$dp'[2^{i}] = 2^{i}$$$ for every $$$i \le n$$$.

  • »
    »
    12 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I'm not really sure but shouldn't the part were you wrote " Mi= mask made of vertices that are incident to i . If Mi and dp[mask⊕i] share vertices " shouldn't it be mask xor pow(2,i) ?