The Gas Station Problem 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[Dynamic Programming]] 

==개요==
Gas Station Problem은 아래와 같은 문제 정의를 가진다:
 가정 1: 뉴욕에서 플로리다까지 가는 길에 주유소 <math>g_1, g_2, \cdots, g_n</math>이 있다.
 가정 2: 각 주유소는 mile marker <math>m_i</math>에 위치해 있으며, 자동차는 한 번 주유로 R마일을 달릴 수 있다.
 목표: 목적지까지 가기 위해 최소 몇 번 주유해야 하는가?
이때 위 문제를 해결하기 위해서 <math>G[i]</math>를 주유소 <math>g_i</math>에 도달하기 위해 필요한 최소 주유 횟수라고 하면 점화식은 아래와 같이 정의된다: 
 <math>G[1]=0</math><ref>첫 번째 주유소는 출발점이므로 주유 횟수가 0이다.</ref>
 <math>G[i]=\min_{j<i,(m_i-m_j<R)}(G[i]+1)</math>
이는 이전 주유소 중에서 i까지 한 번에 갈 수 있는 모든 j에 대해, 가장 적은 주유 횟수의 경우를 선택하고 한 번 추가한다는 것을 의미한다. 

이에 대한 시간복잡도를 계산하면 <math>O(n^2)</math>이다. 이때 모든 i에 대해 가능한 j를 확인하므로 이 문제는 [[BFS]]로도 해결할 수 있다. 각 주유소를 정점, 도달 가능한 관계를 간선으로 보면 unweighted shortest path 문제이기 때문이다. 사실 많은 DP 문제는 실제로 DAG(Directed Acyclic Graph)에서 최단 경로를 찾는 문제의 변형이다.

==Minimum Average Station Price==
이번에는 문제를 변형하여, 각 주요소마다 단가 <math>p(s)</math>가 다르다고 가정하여 “평균 가격이 최소가 되도록 어느 주유소들에서 멈춰야 하는가?”를 구해야 한다고 가정하자. 이때에는 얼마나 자주 넣는가를 고려하지 않고 방문하는 주유소들의 주유비 평균만 최소화하면 된다고 하자. 이를 해결하기 위해 <math>G[i,k]</math>를 주유소 <math>g_i</math>에 정확히 k번 주유한 뒤 도달할 때의 총 단가 합계라고 하면, 아래와 같이 점화식이 정의된다:
 <math>G[1,0]=0</math>
 <math>G[i,k]=\min_{j<i,(m_i-m_j<R)}(G[j,k-1]+p(j))</math>
즉, 해당 점화식은 이전 주유소 j에서 k-1번째 주유까지의 최소 단가합과 이번에 방문하는 주유소의 단가의 합을 의미한다. 최종적으로는 아래와 같은 식을 통해 평균 주유비가 최소가 되는 k를 찾는다:
 <math>\min_{k}\frac{G[n,k]}{k}</math>
하지만 이 방식은 “싼 곳에서 많이 넣고 비싼 곳에서 덜 넣는” 실제 전략을 반영하지는 못한다.

==Cheapest Filling Schedule==
해당 문단에서는 위 문제를 더욱 현실적으로 변형하여, 한 번에 “정수 갤런” 단위로만 주유가 가능하며, 각 주유소마다 가격이 다를 때, “최소 총비용으로 목적지까지 가는 주유 스케줄은 무엇인가?”를 구해야 한다고 가정하자. 이를 해결하기 위해 <math>G[i,k]</math>를 주유소 <math>g_i</math>에 도착했을 때 k갤런의 기름이 남은 상태로의 최소 비용을 의미한다고 가정하자. 이를 이용하면 점화식은 아래와 같이 구해진다:
 <math>G[1,0]=0</math> 
 <math>G[i,k]=\min_c \min_{j<i,(m_i-m_j<R_c)}\{G[j,c]+p(j)\cdot (k-c')\}</math>
위에서 <math>c'</math>은 출발 시 남은 기름량이며, <math>p(j)</math>는 j번째 주유소의 단가를 의미한다. 또한 <math>(m_i-m_j<R_c)</math>은 주유 후 남은 연료로 i까지 도달 가능한 경우만 고려한다는 것을 의미한다.

==각주==