Коммивояжер (нужно посетить только подмножество узлов): прослушивается


Мне нужна помощь с моим кодом проблемы коммивояжера. Его прослушивали... Я знаю, потому что это школьное задание и есть тестовые случаи. Ну вот и все.

Задан связный граф, в котором мне нужно посетить подмножество узлов. Как вычислить кратчайший путь?

Введите описание изображения здесь

В качестве примера обратитесь к приведенному выше изображению. Мне нужно начать с 0 и посетить некоторые / все узлы, а затем вернуться к нулю. В процессе мне нужно вычислить кратчайший путь.

Предположим, мне нужно чтобы посетить все узлы, я буду идти от 0 -> 1 -> 2 -> 3 -> 0 = 20 + 30 + 12 + 35 = 97. Предположим, что теперь мне нужно только посетить узел 2, я пойду от 0 -> 3 -> 2 -> 3 -> 0, поскольку это дает кратчайший путь 94 (я могу посетить узлы, которые мне не нужно посещать, если он может дать кратчайший путь).

В основном, я сделал:

  1. Вычислите кратчайший путь между любыми 2 парами требуемых узлов и источником (0). Это дает мне кратчайший путь 2D-таблицы, как (я использовал dijkstra):
      |  0  1  2  3
    --+--------------
    0 | 
    1 |
    2 | 
    3 |
    
  2. Теперь я модифицирую продавца покупок алгоритм (он же. Флойд Warshall или АПСП), чтобы использовать эту таблицу. Текущий источник Java (TSP и dijkstra) выглядит следующим образом:

    int TSP(int source, int visited) {
       if (visited == (int)(Math.pow(2, K)-1)) { // all required visited
        return sssp.get(source).get(0); // return to source (0)
      } else if (memo.containsKey(source) && memo.get(source).containsKey(visited)) {
        return memo.get(source).get(visited);
      } else {
        int item;
        if (!memo.containsKey(source)) {
          memo.put(source, new HashMap<Integer, Integer>());
        }
        memo.get(source).put(visited, 1000000);
        for (int v = 0; v < K; v++) {
          item = shoppingList[v];
          if (!hasVisited(visited, item)) {
            memo.get(source).put(visited, Math.min(
              memo.get(source).get(visited),
              sssp.get(source).get(item) + TSP(item, visit(visited, v))
            ));
          }
        }
        return memo.get(source).get(visited);
      }
    }
    
    int dijkstra(int src, int dest) {
      PriorityQueue<IntegerPair> PQ = new PriorityQueue<IntegerPair>();
      HashMap<Integer, Integer> dist = new HashMap<Integer, Integer>(); // shortest known dist from {src} to {node}
      // init shortest known distance
      for (int i = 0; i < N+1; i++) {
        if (i != src) {
          dist.put(i, Integer.MAX_VALUE); // dist to any {i} is big(unknown) by default
        } else {
          dist.put(src, 0); // dist to {src} is always 0
        }
      }
      IntegerPair node;
      int nodeDist;
      int nodeIndex;
    
      PQ.offer(new IntegerPair(0, src)); 
      while (PQ.size() > 0) {
        node = PQ.poll();
        nodeDist = node.first();
        nodeIndex = node.second();
    
        if (nodeDist == dist.get(nodeIndex)) {
          // process out going edges
          for (int v = 0; v < N+1; v++) { // since its a complete graph, process all edges
            if (v != nodeIndex) { // except curr node
              if (dist.get(v) > dist.get(nodeIndex) + T[nodeIndex][v]) { // relax if possible
                dist.put(v, dist.get(nodeIndex) + T[nodeIndex][v]);
                PQ.offer(new IntegerPair(dist.get(v), v));
              }
            }
          }
        }
      }
      return dist.get(dest);
    }
    
    1. visited используется в качестве битовой маски для указания, посещен ли узел
    2. sssp - это HashMap<Integer, HashMap<Integer, Integer>>, где ключ 1-й хэшмапы является исходным узлом, а ключ 2-й хэшмапы-конечным. Таким образом, он в основном представляет собой 2D-таблицу, которую вы видите в пункте 1.
    3. memo - это как раз то, что я использовал в динамическом программировании в качестве "кэша" ранее вычисленных кратчайший путь от узла, заданного посещаемым растровым изображением.

Полный источник: http://pastie.org/5171509

Тестовый случай, который проходит:

1

3 3
1 2 3
0 20 51 35
20 0 30 34
51 30 0 12  
35 34 12 0 

Где 1-я строка-количество тестовых случаев. 3-я строка (3 3). 1-й 3 - это число узлов, 2-й 3-это число требуемых узлов. 4-я строка-это список необходимых узлов. Далее следует таблица Весов ребер.

Тестовый случай, который терпит неудачу, является:

9 9
1 2 3 4 5 6 7 8 9
0 42 360 335 188 170 725 479 359 206
42 0 402 377 146 212 767 521 401 248
360 402 0 573 548 190 392 488 490 154
335 377 573 0 293 383 422 717 683 419
188 146 548 293 0 358 715 667 539 394
170 212 190 383 358 0 582 370 300 36
725 767 392 422 715 582 0 880 704 546
479 521 488 717 667 370 880 0 323 334
359 401 490 683 539 300 704 323 0 336
206 248 154 419 394 36 546 334 336 0
Я получил 3995, но ответ-2537... извините, я знаю, что это трудно отладить ... У меня та же проблема, тестовый случай слишком велик ... по крайней мере, для людей ... поэтому я создаю меньший тестовый случай, чтобы проверить ,но они, кажется, проходят...
1 2

1 ответ:

Возможно, не полный ответ, но я думаю, что он, по крайней мере, указывает в правильном направлении: ваш код, кажется, дает результаты следования путям 0->1->2->...->N - > 0. Похоже, никакой реальной оптимизации не происходит.

Я немного переработал ваш код, чтобы получить небольшой неудачный тестовый случай:

int[][]mat=new int[N+1][N+1];
//original
//mat[0]=new int[]{0,20,51,35};
//mat[1]=new int[]{20,0,30,34};
//mat[2]=new int[]{51,30,0,12};
//mat[3]=new int[]{35,34,12,0};
//switched order of nodes, node 2 is now node 1
mat[0]=new int[]{0,51,20,35};
mat[1]=new int[]{51,0,30,12};
mat[2]=new int[]{20,30,0,34};
mat[3]=new int[]{35,12,34,0};

Это производит 146 как лучший путь, показывая, что он следует по пути 0->1->2->3->0 (47+30+34+35, 47 является кратчайшим путем от 0 до 1, используя узел 4) (Все номера узлов с моим переключателем порядка).

Edit: я нашел преступника после еще одного быстрого взгляда. У вас есть строка if (!hasVisited(visited, item)), чтобы проверить, посещали ли вы уже узел item. Однако visited строится по visit(visited, v), в котором v является индексом в shoppinglist. item =shoppinglist[v] но вы должны использовать то же самое, если вы перемещаете посещаемый вектор.

Вы должны использовать if (!hasVisited(visited, v)) вместо if (!hasVisited(visited, item))

На несвязанной ноте, я не уверен, является ли первый шаг поиска кратчайших путей необходимым или может повлиять на ваши результаты. Если прямая связь от A до B длиннее, чем через другие узлы (скажем, C), тогда она заменяется в таблице расстояний. Если бы вы затем использовали эту ссылку в своем окончательном решении, чтобы перейти от А К В, то вы бы на самом деле шли через С, который уже был бы на вашем пути (так как этот путь является полным решением TSP). Если узел можно посетить только один раз, то это может быть проблемой.