Clever Geek Handbook

How to check for existence of a Hamiltonian walk in O (2 ^ n) memory and O (2 ^ n * n) time

We can simply modify the traveling salesman problem to get whether the Hamilton motion exists or not in O (2 ^ N * N ^ 2). Complexity of time.

But I read it on codeforces that this problem can be solved in O (2 ^ N * N) time.

While I can't understand the state they are looking at, they kind of compress the original state of the seller issue.

Can someone give me a detailed explanation, I am new to bitmasking + DP (Infact I started today: D)

If you want, you can check point 4 on Codeforces

+3


source to share


2 answers


Terminology:

  • binary (x)

    means x

    based on 2

    .
  • Nodes numbered starting with 0

  • mask

    always represent set

    nodes. A node i

    is in mask

    means 2^i AND mask != 0

    . Likewise, set mask-i

    (here -

    means deletion i

    from the set) can be represented as mask XOR 2^i

    in a bit mask.

Let be the mask

bitmask of the node set. We define dp[mask]

as a bitmask of another set of nodes that contains a node i

if and only if:

  • i

    in mask

  • there is a hamilton walk for a set of nodes mask

    that ends with nodei

For example, dp[binary(1011)] = binary(1010)

means that for binary(1011)

there is a Hamiltonian walk that ends at node 1

, and for binary(1011)

there is another Hamiltonian walk that ends at node3

So, for knots N

for all of them, there is a Hamiltonian projection ifdp[2^N - 1] != 0

Then, as described in the Codeforces link you provided, we can compute dp[]

:



When mask

contains only one nodei

dp[2^i] = 2^i

(which means for one node, a always exists and it ends by itself.

Otherwise

Given mask

, by definition dp[mask]

, for each node i

in mask

, we want to know if there is a prog for mask

and ends with i

. to calculate this, we first check if there is any walk for the set of nodes mask-i

, then check among those walks mask-i

if there is a walk ends on the node j

that is connected to i

. Because combining them gives us a walk mask

that ends with i

.

To make this step faster, we preprocess M[i]

all notes associated with a bitmask as a bit mask i

. So, i

in dp[mask]

if dp[mask XOR 2^i] AND M[i] != 0

.

To explain a little more about this step dp[mask XOR 2^i]

is a set of nodes that can walk from mask-i

, and M[i]

is a set of nodes that are directly related to i

. So one of them AND

means that there is any move mask

that ends with i

.

dp[]

is O(2^N)

in space. The calculation dp[]

looks like

for mask = range(0, 2^N):
  for i in range(0,N):
    if 2^i AND mask != 0: # Node i in mask
      if (mask only has one node) || (dp[mask XOR 2^i] AND M[i] != 0):
        dp[mask] = dp[mask] OR 2^i # adding node i to dp[mask]

What is O (2 ^ N * N)

+3


source


[EDIT: After seeing the other answer, I realize I answered the wrong question. Maybe this information is still useful? If not, I will delete it. Let me know in the comments.]

They give a clear idea of ​​what each record in the DP table will store. This is a solution to a specific subproblem, consisting only of a certain subset of vertices, with an additional restriction that the path must end at a certain vertex:

Let dp [mask] [i] be the length of the shortest Hamiltonian walk in the subgraph generated by the vertices in the mask that ends with vertex i.

Each path ends at some vertex, so the solution to the original problem (or at least its length) can be found by looking for the minimum dp[(1 << n) - 1][i]

over all 0 <= i <n ( (1 << n) - 1

- just a nice trick to create a bitset with the lowest bit n

set in 1).

The basic update rule (which I've paraphrased a bit below due to formatting limitations) might get more explanation:



dp [mask] [i] = min (dp [mask XOR (1 <i)] [j] + d (j, i)) all over j, so bit (j, mask) = 1 and (j, i ) is an edge

So, to fill dp[mask][i]

, we want to solve a subproblem for a set of vertices in mask

, assuming that the last vertex is in the path i

. First, note that any path P

that goes through all vertices in mask

and ends with i

must have a finite edge (assuming mask

there are at least 2 vertices in). This edge will be from some vertex i

j

in mask

to i

. For convenience, let k

be the number of vertices in mask

which have an output k i

. Let be Q

the same path as P

, but with its final edge (j, i)

discarded: then the length P

is equal length(Q) + d(j, i)

. Since any path can be decomposed in this way, we could split the set of all paths through frommask

up i

to the groups k

according to their final edge, find the best path in each group and then choose the best of these minimums k

, and this ensures that we don't miss any opportunities.

More formally, to find the shortest path P

, it would be enough to consider all k

possible final edges (j, i)

, for each such choice, find a path Q

through the remaining vertices in mask

(i.e., all vertices except for itself i

), which ends with j

and minimizes length(Q) + d(j, i)

, and then chooses the minimum these minima.

End-edge grouping doesn't seem to help much at first. But note that for a particular choice, j

any path Q

that ends with j

and minimizes length(Q) + d(j, i)

also minimizes length(Q)

and vice versa, since it d(j, i)

is only a fixed additional cost when j

(and of course i

) fixed. And it just so happens that we already know such a path (or at least its length, which is all we really need): this dp[mask XOR (1 << i)][j]

! (1 << i)

means "binary integer 1 shifted left i

times" - this creates a bitset consisting of one vertex, namely i

; XOR

has the effect of removing that vertex from mask

(since we already know that the corresponding bit should be 1 in mask

). Generally,mask XOR (1 << i)

means mask \ {i}

in more mathematical notation.

We still don't know which j

is the best penultimate vertex , so we have to try all k

of them and pick the best as before, but finding the best path Q

for each choice is j

now a simple O (1) array search instead of an exponential search :)

+2


source






More articles:


All Articles