Back Tracking Vs. Greedy Algorithm Максимальный независимый набор

Question

Я реализовал алгоритм обратной трассировки, используя как алгоритм жадного алгоритма, так и алгоритм обратного слежения. алгоритм отслеживания обратно следующим образом:

MIS(G= (V,E): a graph): largest set of independent vertices 
1:if|V|= 0 
then return . 
3:end if 
if | V|= 1 
then return V 
end if 
pick u ∈ V 
Gout←G−{u}{remove u from V and E } 
Gn ← G−{ u}−N(u){N(u) are the neighbors of u} 
Sout ←MIS(Gout) 
Sin←MIS(Gin)∪{u} 
return maxsize(Sout,Sin){return Sin if there’s a tie — there’s a reason for this. 
} 

Жадный алгоритм итеративно выбрать узел с наименьшей степени, поместить его в MIS, а затем удалить его и его соседей из G.

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

Answer 1

Ваше решение является странным. Backtracking обычно используется для да/нет проблем, а не для оптимизации. Алгоритм, который вы написали, сильно зависит от того, как вы выбираете u. И это определенно не отступает, потому что вы никогда не возвращаетесь назад.

Такая проблема может быть решена в ряде способов, например .:

• генетическое программирование,
• исчерпывающий поиск,
• решения задачи о двойном графике (максимальная проблема кликой).