뒤로 추적. 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

당신의 솔루션이 이상합니다. 역 추적은 대개 예/아니요 문제가 아닌 최적화에 사용됩니다. 작성한 알고리즘은 u을 어떻게 선택 하느냐에 달려 있습니다. 그리고 당신은 결코 뒤로 물러 설 수 없기 때문에 그것은 확실히 되돌아 오지 않습니다.

이러한 문제는 이중 그래프 (최대 도당 문제)의 문제를 해결

철저한 검색,

예컨대 :

• 유전자 프로그래밍, 다수의 방식으로 해결 될 수있다.