Greedy 알고리즘에 결함이 있습니까?

Question

이 문제를 해결하기 위해 내 욕심쟁이 알고리즘에 결함이나 문제점이 있는지 궁금합니다. 문제는 :

• 그들은 직원의 집합이야
• 각 직원이 한 주 동안의 시간의 단일 간격을 하나 개 작업 교대가있다. 직원의 교대는 중복 될 가능성이 있습니다.
• 직원의 하위 집합이 감독 그룹을 구성합니다.
• 감독 그룹은 모든 직원의 교대 시간마다 감독자가 근무하는 속성이 있습니다.

목표는 가능한 작은 크기의 감독 그룹을 생성하는 것입니다.

이제, 내 욕심쟁이 알고리즘이이를 해결합니다.

While(there are employee's who aren't supervisors and are not removed) 
     Choose first employee working with longest work shift to be supervisor. 
     Remove any employee whos finish time is less than the current supervisor finish time. 

     If(supervisor shift is ending) 
     Turn employee whos shift interests with supervisor shift, 
     with longest work time remaining into a supervisor as well. 
     end if 
    End while 

     return list of supervisors 

이 작품은 윌 : 직원의 목록이있을 것 같은데요? 그리고 이것이 실제로 가능한 가장 작은 그룹의 수퍼바이저를 돌려 줄 것입니까? 이것이 최선의 방법인지 확실하지 않습니다.

덕분에 각 직원 정확히 1 개 교대 작업으로

Answer 1

, 욕심 전략은 최적의 솔루션을 생산하는 것을 증명하기 쉽습니다.

알고리즘이 최적의 솔루션을 생성하지 않는다고 가정 해 봅시다. 즉, 두 개의 연속 된 간격에 대해 감독자가 할당 된 최소 두 명의 직원 E1 및 E2을 대체 할 수있는 직원 E0이 있음을 의미합니다. 이것은 E0의 시프트가 적어도 E1 초에 시작되었고 늦게 또는 늦게 E2으로 끝났음을 의미합니다. 그것이 사실이라면, 당신의 욕심 많은 알고리즘은 E1을 넘는 E0을 감독자로 선정했을 것입니다. 이것은 모순입니다. 이는 알고리즘이 문제에 대한 최적의 솔루션을 찾는다는 의미입니다.