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

Can't solve problem :(
Автор difask, 10 лет назад, перевод, По-русски

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.

  • Проголосовать: нравится
  • -20
  • Проголосовать: не нравится

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

Can you give me link?

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

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

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

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.

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

    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).

    → Ответить