Блог

Главная - Вопросы по программированию - Временная сложность Tsp с использованием DP

Временная сложность Tsp с использованием DP

#algorithm #time-complexity #traveling-salesman

#алгоритм #временная сложность #коммивояжер

Вопрос:

это формула рекурсии для задачи :

C(i,S) = min { d(i,j) C(j,S-{j}) }

На самом деле, когда я попытался реализовать это в виде кода, мне на ум пришел следующий код:

 int TSP(i, S){
    if(S.size == 0)
    return dist(start_vertex,i)
min = inf
cost = inf
  for(int j=0;j<S.size;j  )
     {
      cost = dist(i,S[j]) TSP(j,S-{j});
      if(cost < min)
       min = cost;
      }
global_cost =min;
return min;
}

Поскольку это for сравнивает n раз, чтобы найти минимум, это означает его рекурсию как:

 T(n) = nT(n-1) n ==> T(n) = O(n!)

Поскольку каждый шаг, который мы сравниваем, чтобы найти минимальный размер size S, конечно, код является факториальным. Итак, какое это имеет отношение к подмножеству и
Итак, почему сложность времени в форме (n^2*2^n) ? И каково доказательство его временной сложности?

Комментарии:

1. размер таблицы dp равен n * 2 ^ n, и при каждом вызове ftion мы тратим n времени в цикле for, следовательно, время завершения равно n * n * 2 ^ n

2. @Photon Как получается 2 ^ n? что такое таблица dp?

3. просто погуглите несколько статей о подходе TSP dp, ваш псевдокод — это не dp, а просто рекурсия, для dp вам нужно использовать таблицу для сохранения результатов предыдущих вычислений, чтобы они не пересчитывались каждый раз

4. @Photon этот код пересчитывается каждый раз? То есть он пересчитывает режим дублирования, который он уже рассчитал? Можете ли вы привести пример?

5. ваш код вообще не dp, он просто выбирает первый узел, затем повторяется для набора оставшихся узлов, поэтому сложность ofc будет факторной, динамическое программирование использует другой подход, в Интернете есть много хороших объяснений, которые вы можете посмотреть для лучшего понимания (т. Е. youtube.com/watch?v=-JjA4BLQyqE )