쉽게 배우는 알고리즘 해답, 솔루션, 답안지

목차

1장
2장
3장
4장
5장
6장
7장
8장
9장
10장
11장
12장

본문내용

7. 잃는 점: 최적해를 보장할 수 없다.
얻는 점: 잔여거리보다 작은 것을 보장하기 위해 추정치와 실제잔여치의 차이가 필요 이상으로 커질 가능성이 많다. 잔여거리보다 작은 것이 보장되지는 않지만 잔여거리를 더 정확히 추정할 수 있는 수단이 있으면 최적해는 보장하지 못하지만 탐색은 더 빠르고 효율성은 높아질 것이다.
실제 잔여거리보다 작은 추정값을 구할 수 없을 때, 잔여거리보다 작은 것이 보장되지 않는 추정값이라도 쓰면 근사해를 구할 수 있다. (잔여거리의 추정치를 무조건 0으로 놓으면 실제 잔여거리보다 작은 추정값으로 삼을 수는 있으나 아무 의미없는 추정치라 탐색의 품질에 도움을 주지 못한다. 이럴 때 잔여거리보다 작은 것이 보장되지는 않지만 잔여거리를 추정할 수 있는 수단이 있으면 그것을 사용하는 것이 더 나을 수 있다. 물론 추정의 합리성에 따라 품질은 영향을 받겠지만...)

참고 자료

없음