The Gas Station Problem

상위 문서: Dynamic Programming

개요

Gas Station Problem은 아래와 같은 문제 정의를 가진다:

가정 1: 뉴욕에서 플로리다까지 가는 길에 주유소 $g_1,g_2,\cdots ,g_n$이 있다.
가정 2: 각 주요소는 mile marker $m_i$에 위치해 있으며, 자동차는 한 번 주유로 R마일을 달릴 수 있다.
목표: 목적지까지 가기 위해 최소 몇 번 주유해야 하는가?

이때 위 문제를 해결하기 위해서 $G[i]$를 주유소 $g_i$에 도달하기 위해 필요한 최소 주유 횟수라고 하면 점화식은 아래와 같이 정의된다:

$G[1]=0$
$G[i]=\underset{j<i,(m_i-m_j<R)}{\min }(G[i]+1)$

이는 이전 주유소 중에서 i까지 한 번에 갈 수 있는 모든 j에 대해, 가장 적은 주유 횟수의 경우를 선택하고 한 번 추가한다는 것을 의미한다.

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

Minimum Average Station Price

이번에는 문제를 변형하여, 각 주요소마다 단가 $p(s)$가 다르다고 가정하여 “평균 가격이 최소가 되도록 어느 주유소들에서 멈춰야 하는가?”를 구해야 한다고 가정하자. 이때에는 얼마나 자주 넣는가를 고려하지 않고 방문하는 주유소들의 주유비 평균만 최소화하면 된다고 하자. 이를 해결하기 위해 $G[i,k]$를 주유소 $g_i$에 정확히 k번 주유한 뒤 도달할 때의 총 단가 합계라고 하면, 아래와 같이 점화식이 정의된다:

$G[1,0]=0$
$G[i,k]=\underset{j<i,(m_i-m_j<R)}{\min }(G[j,k-1]+p(j))$

즉, 해당 점화식은 이전 주유소 j에서 k-1번째 주유까지의 최소 단가합과 이번에 방문하는 주유소의 단가의 합을 의미한다. 최종적으로는 아래와 같은 식을 통해 평균 주유비가 최소가 되는 k를 찾는다:

$\underset{k}{\min }\frac{G[n,k]}{k}$

하지만 이 방식은 “싼 곳에서 많이 넣고 비싼 곳에서 덜 넣는” 실제 전략을 반영하지는 못한다.

Cheapest Filling Schedule

해당 문단에서는 위 문제를 더욱 현실적으로 변형하여, 한 번에 “정수 갤런” 단위로만 주유가 가능하며, 각 주유소마다 가격이 다를 때, “최소 총비용으로 목적지까지 가는 주유 스케줄은 무엇인가?”를 구해야 한다고 가정하자. 이를 해결하기 위해 $G[i,k]$를 주유소 $g_i$에 도착했을 때 k갤런의 기름이 남은 상태로의 최소 비용을 의미한다고 가정하자. 이를 이용하면 점화식은 아래와 같이 구해진다:

$G[1,0]=0$ 
$G[i,k]=\underset{c}{\min }\underset{j<i,(m_i-m_j<R_c)}{\min }\{G[j,c]+p(j)\cdot (k-c^{\prime })\}$

위에서 $c^{\prime }$은 출발 시 남은 기름량이며, $p(j)$는 j번째 주유소의 단가를 의미한다. 또한 $(m_i-m_j<R_c)$은 주유 후 남은 연료로 i까지 도달 가능한 경우만 고려한다는 것을 의미한다.