C++で解くガソリンスタンド巡回問題 ― トラックが一周できる最初の出発地点を見つけるアルゴリズム

問題の概要

円周上に n 個のガソリンスタンドがあるとします。各スタンドについては、次の2種類のデータが与えられます。

• 各ガソリンスタンドが保有している燃料の量
• あるガソリンスタンドから次のガソリンスタンドまでの距離

このとき、トラックが円を一周しきれる出発地点のうち、最初の地点を求めるのが本問題の目的です。ただし、1リットルの燃料で1単位の距離を走行できるものと仮定します。

具体例

たとえば、4つのガソリンスタンドがあり、それぞれの「燃料量」と「次のスタンドまでの距離」が以下のように与えられているとします。

[(4, 6), (6, 5), (7, 3), (4, 5)]

この場合、トラックが一周できる最初の出発地点は2番目のガソリンスタンドです。したがって、出力は start = 1（2番目のスタンドのインデックス）となります。

キューを使った効率的な解法

この問題は、キュー（queue）を用いることで効率的に解くことができます。基本的な考え方は次のとおりです。

• キューには、現在検討中の巡回経路を格納します。
• まず最初のガソリンスタンドをキューに追加し、その後も巡回が完了するか、現在の燃料残量が負になるまで順にスタンドを追加していきます。
• 燃料残量が負になった場合は、再び正になるまでキューの先頭からスタンドを取り除いていきます。

この方法では、各ガソリンスタンドは最大でも1回の追加と1回の削除しか行われないため、全体の計算量は O(n) となり、全出発点を毎回試す素朴な O(n²) のアプローチよりも大幅に高速です。

C++での実装例

#include <iostream>
using namespace std;
class pump {
    public:
    int petrol;
    int distance;
};
int findStartIndex(pump pumpQueue[], int n) {
    int start_point = 0;
    int end_point = 1;
    int curr_petrol = pumpQueue[start_point].petrol - pumpQueue[start_point].distance;
    while (end_point != start_point || curr_petrol < 0) {
        while (curr_petrol < 0 && start_point != end_point) {
            curr_petrol -= pumpQueue[start_point].petrol - pumpQueue[start_point].distance;
            start_point = (start_point + 1) % n;
            if (start_point == 0)
                return -1;
        }
        curr_petrol += pumpQueue[end_point].petrol - pumpQueue[end_point].distance;
        end_point = (end_point + 1) % n;
    }
    return start_point;
}
int main() {
    pump PumpArray[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
    int n = sizeof(PumpArray)/sizeof(PumpArray[0]);
    int start = findStartIndex(PumpArray, n);
    if(start == -1)
        cout<<"No solution";
    else
        cout<<"Index of first petrol pump : "<<start;
}

実行結果

Index of first petrol pump : 1

処理の流れのポイント

• curr_petrol: 現在の経路で保持している燃料の純増減（燃料量 − 移動距離の累積）を表します。
• start_point: 巡回の候補となる出発地点です。燃料が不足した場合はここを進めます。
• end_point: 次に追加を試みるガソリンスタンドの位置です。剰余演算（% n）により円環状に巡回します。
• start_point が一周して 0 に戻った場合は、どの出発点でも一周できないことを意味するため、-1 を返します。

このように、キューによる両端の管理を活用することで、一周可能な出発地点を線形時間で見つけられるのがこのアルゴリズムの大きな特徴です。