difask's blog

Can't solve problem :(
By difask, 10 years ago, In English

You are given N points (N <= 20). Distance between 2 points is abs(x1-x2)+abs(y1-y2). You should find the shortest way which will visit all points. You can start from any point.

  • Vote: I like it
  • -20
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can you give me link?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

It's like the Traveling Salesman problem, but since N ≤ 20, you can do DP with bitmask with complexity O(2N * N).

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Seems like actually it will be N*(2^N). =)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, you're correct. I forgot to consider that.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know bitmasks. Where can I read about it? And also if it isn't hard can some of you write code or pseudocode for it?

        → Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Well if O(2^N * N^2) is fast enough, then you can just create a full graph with the distances and solve the Travelling Salesman problem similarly to Hamiltonian Path problem, using bitmasks in states.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Why O(2N * N2) ???

    There are 2N states, and you perform N checks in each one of them (which point to go next), so total complexity would be O(2N * N).

    EDIT: Actually, you're right. There are 2N * N states, so complexity is O(2N * N2).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Enchom is right.
      There're actually N * (2^N) states.
      DP is f[mask][lastVertex].
      So it's really N^2 * (2^N). :)

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, that was pretty stupid of me... sorry.

        → Reply