은 .. 나는이 문제에 작업을 시도하고

Question

이 ... 아래에 언급 한 algorithm..i 알아 낸 것입니다

입력 선형 시간에 나무에 대한 최적의 정점 커버를 발견하는 효율적인 욕심이 알고리즘을 지정 그래프 은 다른 모든 노드와 일치하는 정도가 가장 높은 정점을 선택합니다. 이 노드에서 발생하는 가장자리를 제거하십시오. 선택한 꼭지점과 그 가장자리를 집합 X에 추가합니다. Return X

여기서 X는 꼭지점 덮개에 필요한 최소 꼭지점 집합을 반환합니다.이 방법은 올바른 것입니까? 감사합니다.

Answer 1

가장 높은 등급의 정점을 선택하는 것이 최선의 해결책을 보장 할 수는 없습니다.

는

1 2 // (1,2) is connected. 
1 3 
1 4 
2 5 
3 6 
4 7 

최소 정점 커버가 {2,3,4}입니다, 그러나 욕심 접근 방식을 기반으로, 당신은 {선택합니다 : 당신이 7 개 정점과 나무가 예를 들어, 다음과 같이, 가장자리가 나열되어 있습니다 1}을 먼저 선택하면 왼쪽 3 가장자리를 덮기 위해 적어도 3 개의 정점을 선택하게됩니다.

참으로, 트리의 정점 커버 문제를 해결하기위한 탐욕적인 알고리즘이 있습니다. 즉, 각 단계마다 리프가 있음을 알 수 있습니다 (입력이 나무이기 때문에 왼쪽 가장자리가 없으면 항상 그런 리프를 찾을 수 있습니다).) 다음, 버텍스 커버 세트 X에 대한 리프의 이웃을 선택하십시오. 그래프가 비어있을 때 X를 최소 버텍스 커버로 반환하십시오. 복잡성은 E = V-1 일 때 O (E)이므로 선형 솔루션이라고 말할 수 있습니다.