탐욕 알고리즘에서는 풀이를 한 조각씩 덧붙여 만들어가는 반면, 반복 향상(iterative improvement) 알고리즘에서는 쉽게 구할 수 있는 근사적인 해에서 시작해 몇 가지 단순한 단계를 반복적으로 적용함으로써 풀이를 개선한다. 이런 알고리즘이 유효한지 확인하기 위해서는 그 알고리즘은 유한한 단계 안에 종료되는지, 최종적으로 구한 근사적인 풀이가 문제의 진짜 풀이인지 분명히 알 수 있어야 한다. 다음 문제는 Martin Gardner의 aha!Insight[Gar78, pp.131-132]에 실려 있던 문제를 현시대에 맞게 바꾼 버전이다.

레모네이드 가판대 배치 방법 다섯 친구 - 알렉스, 브렌다, 케이시, 댄, 얼 - 가 레모네이드 가판대를 설치하려고 한다. 이 다섯 친구는 그림 1-10 (a)에 있는 지도에 각각 A, B, C, D, E로 표시된 지점에서 살고 있다. 각 집에서의 거리를 최소화하고 싶다면 어느 위치에 레모네이드 가판대를 설치해야 할까? 가판대까지의 거리는 집으로부터 총 블록 수 - 가로세로 모두 더함 - 로 따진다.

처음에는 맨 왼쪽에 있는 A와 맨 오른쪽에 있는 B를 기준으로 수평 방향으로 중간 지점이면서 맨 위에 있는 A와 맨 아래에 있는 E를 기준으로 수직 방향으로 중간 지점인 1번 사거리(그림 1-10 (b))에 가판대를 설치하기로 했다. 그런데 누군가 따져보니 그곳은 가장 좋은 자리가 아니었다. 그래서 다음과 같이 반복 향상 알고리즘을 따르기로 했다. 원래 후보 지점에서 시작해 한 블록 떨어진 지점을 (위(북), 오른쪽(동), 아래쪽(남), 왼쪽(서) 같은 식으로) 정해진 순서대로 따져본다. 모든 친구의 집까지의 거리가 새 위치에서 더 가까우면 기존 위치를 새 후보 지점으로 바꾼 후 똑같은 확인 절차를 반복한다. 한 칸 떨어진 네 지점 중에서 더 가까운 곳이 없다면 현재 위치를 최적으로 간주하고 알고리즘을 중단시킨다. 이 알고리즘이 돌아가는 과정은 그림 1-10 (b), 계산한 거리는 그림 1-10 (c)에 정리했다.