Какова вычислительная сложность поиска табу?

Question

Мне было интересно, какова вычислительная сложность метаэвристики, подобной табу. Почему в исходной статье отсутствует раздел, в котором обсуждается временная и пространственная сложность алгоритма и даже об улучшении алгоритма, например, итеративный поиск табу и реактивный поиск табу?

Я хочу проанализировать алгоритм с другими по проблеме коммивояжера.

begin
 T:= [ ];
 s:=initial solution;
 s*:=s
 repeat
 find the best admissible s’ є N(s);
 if f(s’) > f(s*) then s*:=s’
 s:=s’;
 update tabu list T;
 until stopping criterion:
end;

Answer 1

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