다음과 같은 경우 greedy 알고리즘이 실패한 이유

Question

동적 프로그래밍만을 사용하여 해결할 수있는 문제를 해결하려고했습니다. 다음은 문제입니다. 남자는 총 에너지가 H이고 거리 D를 커버 할 필요가 있습니다. 그는 최소 시간 동안 최대 에너지를 사용하여이 거리를 커버하려고합니다. 그는 5 가지 모드로 실행할 수 있습니다. 총 거리는 5 가지 모드 중 하나에 따라 각 km를 달리게하여 보상됩니다. '500 만 10 초', 6 '분 11 초」, 「7m 7 초', 8 '분 11 초」, 「9m의 11 초'

- : 이들 5 가지 모드가

시간 정렬 된 두 개의 배열을 사용하여 설명한다 필요한

에너지 : -11,9,8,7,6

그래서 내 욕심 솔루션 전략은 가장 낮은 소요 H/D

실행 다음 km 사용 모드의

1. 계산 X = 바닥이다 시간과 에너지가 필요합니다 < 모드

   집합 D = 필요한 = X

   & 세트 H = H 에너지 D-1

2. 오도 남은 거리까지 단계 1 0

3. 답변 모두의 일부가 될 것이다진다 각 km 당 시간.

이 솔루션은 효과가 있지만 실제로는 실패합니다. DP를 사용하여 문제를 해결하는 방법을 알고 있지만 실패한 부분을 알고 싶습니다. 나는 많은 예를 시도했지만 그 느낌을 얻지 못했습니다. 나는 두 개의 배열 요소를 정확하게 상상할 수는 없지만 반드시 정렬 된 순서로 존재한다.

Answer 1

이유는 간단합니다. 알고리즘을 입증하지 않았기 때문에 올바른 알고리즘이라고 주장 할 수 없습니다. 그처럼 간단합니다. 당신은 연구 문헌에서 얼마나 많은 휴리스틱 알고리즘이 "룩"한지 알 수 있지만 정확성에 대한 증명이 없습니다. 그렇다면 왜 그들은 경험적 방법 일 뿐이 냐고.

당신의 솔루션은 경험적입니다. 예를 들면. H=100, D=3을 가져 가십시오. 또한 시간이 [1,2,3,4,5]이고 해당 에너지가 [35,34,32,32,32] 인 모드를 선택하십시오.

귀하의 초기 x은 floor(100/3)=33입니다. 에너지가 <=33 인 가장 낮은 시간은 3입니다. 그것을 선택하십시오. H=67, D=2과 같이 H와 D를 업데이트하십시오. 우리는 floor(67/2)=33 있습니다. 다시 3 시간을 선택하십시오. H=34, D=1과 같이 H와 D를 업데이트하십시오. 마지막으로 x=floor(34/1)=34 시간을 선택하십시오 2. 따라서 거리를 표시하는 시간 목록은입니다. 총 에너지는 32+32+34=98이고 총 시간은 8입니다.

그러나 나는 탐욕스러운 해결책보다 나은 해결책을 찾을 수 있습니다. 즉, 시간이 8 인 [1,3,4] 시간이지만 총 에너지는 35+32+32=99입니다. 당신의 탐욕스러운 해결책을이기십시오.

이야기의 도덕? 귀하의 알고리즘을 증명할 수 없다면, 잘못 추측하거나 단순히 경험적으로 추측 해보십시오.