Final Fantasy XII サブイベント「キャビンチーフ七姉妹」を効率的に攻略する

突然のゲーム攻略エントリ

だいぶ前にFinal Fantasy XII The Zodiac AgeのNintendo Switch版を購入し、先日ラスボスを撃破し、現在2周目をやっている。 FF12のサブイベントに「キャビンチーフ七姉妹」というものがあり、飛空艇定期便の「ゆったり飛空艇」の全航路にいるキャビンチーフのに話しかけるというイベントである。 全7航路あり、効率的にめぐる方法がないだろうか。 これは、グラフ理論の問題に落とし込めば解決できる。

オイラーグラフと準オイラーグラフ

あるグラフGがオイラーグラフであるとはGがオイラー閉路を持つことである。 オイラー閉路とはすべての辺を1回だけ通る閉路である。 また、あるグラフGが準オイラーグラフであるとは、Gがオイラー路を持つがオイラー閉路を持たないことをいう。 オイラーグラフは準オイラーグラフであるが逆は当然成立しない。

NetworkXで解く

御託はここまで、実際に都市を頂点、航路を辺とするグラフがオイラーグラフまたは準オイラーグラフであることをNetworkXで調べてみよう。

nodes = (
    "王都ラバナスタ",
    "ナルビナ城塞",
    "帝都アルケイディス",
    "港町バーフォンハイム",
    "空中都市ビュエルバ",
)
edges = (
    ("王都ラバナスタ", "ナルビナ城塞",),
    ("王都ラバナスタ", "帝都アルケイディス",),
    ("王都ラバナスタ", "空中都市ビュエルバ",),
    ("ナルビナ城塞", "帝都アルケイディス",),
    ("ナルビナ城塞", "港町バーフォンハイム",),
    ("帝都アルケイディス", "港町バーフォンハイム",),
    ("港町バーフォンハイム", "空中都市ビュエルバ",),
)

G = nx.Graph()
G.add_nodes_from(nodes)
G.add_edges_from(edges)

print(nx.is_eulerian(G))
print(nx.is_semieulerian(G))

結果は、

False
False

となる。 これは、空中都市ビュエルバ以外の頂点の次数がすべて奇数であり、オイラーグラフと準オイラーグラフの性質を満たさないから当然である。

俺達にはシュトラールがある

ところで、全航路たどれるタイミングではシュトラールが利用可能になっている。 つまり、辺を追加することで準オイラーグラフにすることができる。 ここで、王都ラバナスタと港町バーフォンハイムをシュトラールで移動することにする。

G.add_edge(*("王都ラバナスタ", "港町バーフォンハイム"))  # シュトラールで移動
print(nx.is_eulerian(G))
print(nx.is_semieulerian(G))

結果は

False
True

となり、準オイラーグラフとなった。

後は、オイラー路を求めれば所望の結果を得る。

for e in nx.eulerian_path(G):
    print(e)

結果は以下の通りである。

('帝都アルケイディス', '港町バーフォンハイム')
('港町バーフォンハイム', '空中都市ビュエルバ')
('空中都市ビュエルバ', '王都ラバナスタ')
('王都ラバナスタ', '港町バーフォンハイム')
('港町バーフォンハイム', 'ナルビナ城塞')
('ナルビナ城塞', '帝都アルケイディス')
('帝都アルケイディス', '王都ラバナスタ')
('王都ラバナスタ', 'ナルビナ城塞')

任意の都市間をシュトラールで移動できるからハミルトン閉路ではダメなのか？という疑問は、あくまでもすべての航路でキャビンチーフに話しかける必要があるのでハミルトン閉路ではなくオイラー閉路である必要があった。