オイラー閉路

本稿では NetworkX の提供する、グラフのオイラー閉路を求める機能を応用する例を示す。

ドラクエ 7 最適基本職習得キャリアパスを計算する

前置きが長くなるが、オリジナル版のドラクエ 7 の転職システムの一部である「職歴技」についておおまかに説明する。以下の説明は厳密に言えばゲームのルールと異なるが、あくまでこれからモデル化するグラフの説明のための表現なのでどうか勘弁して欲しい。

ゲーム中のある時点で、主人公とその仲間たちは「せんし」や「まほうつかい」といった基本職に任意に就職することができる。さらに、ある職業と別の職業にそれぞれ一定期間連続して就職すると、特別な呪文・特技（以下、これらをスキルとまとめて呼ぶ）を修得するという仕様があった。この一定期間がかなり時間的に長いことと、特別スキルのない職業同士の順序で就職すると時間の無駄になるため、ゲームプレイヤーとしては可能な限り効率的に基本職のマスター順序を計画しておきたい。

そこで本稿では、各基本職と意味のある転職をそれぞれノード、エッジに見立てた無向グラフを考える。仮にこのグラフが（準）オイラーグラフであれば、そのノード順に就職していくのが最適解であると結論できる。

関数 nx.is_eulerian

まずはグラフを生成し、ダメ元で関数 nx.is_eulerian を適用してみよう。

#!/usr/bin/env python
"""eulerian.py: demonstrate NetworkX is_eulerian and eulerian_circuit.

Compute the most efficient career path in DRAGON QUEST 7 (2000).
"""
import networkx as nx

def main():
    """The main function.

    Returns:
      None
    """

    G = nx.Graph()
    G.add_edges_from((
        ('せんし', 'とうぞく', dict(skill='ぬすっと斬り')),
        ('せんし', 'おどりこ', dict(skill='つるぎのまい')),
        ('せんし', 'ぎんゆうしじん', dict(skill='たたかいの歌')),
        ('せんし', 'ふなのり', dict(skill='かもめ返し')),
        ('せんし', 'ひつじかい', dict(skill='みねうち')),
        ('せんし', 'わらわせし', dict(skill='へんてこ斬り')),
        ('ぶとうか', 'まほうつかい', dict(skill='火の息')),
        ('ぶとうか', 'とうぞく', dict(skill='きゅうしょ突き')),
        ('ぶとうか', 'おどりこ', dict(skill='マッスルダンス')),
        ('ぶとうか', 'ぎんゆうしじん', dict(skill='おたけび')),
        ('ぶとうか', 'ふなのり', dict(skill='すいめんげり')),
        ('ぶとうか', 'ひつじかい', dict(skill='マトンアタック')),
        ('ぶとうか', 'わらわせし', dict(skill='しっぺ返し')),
        ('まほうつかい', 'ぶとうか', dict(skill='火の息')),
        ('まほうつかい', 'とうぞく', dict(skill='マホトラ')),
        ('まほうつかい', 'おどりこ', dict(skill='マホキテ')),
        ('まほうつかい', 'ぎんゆうしじん', dict(skill='のろいの歌')),
        ('まほうつかい', 'ふなのり', dict(skill='いなずま')),
        ('まほうつかい', 'ひつじかい', dict(skill='ラリホーマ')),
        ('まほうつかい', 'わらわせし', dict(skill='メダパニ')),
        ('そうりょ', 'おどりこ', dict(skill='死のおどり')),
        ('そうりょ', 'ぎんゆうしじん', dict(skill='やすらぎの歌')),
        ('そうりょ', 'ふなのり', dict(skill='ノアのはこぶね')),
        ('そうりょ', 'ひつじかい', dict(skill='スクルト')),
        ('とうぞく', 'せんし', dict(skill='ぬすっと斬り')),
        ('とうぞく', 'ぶとうか', dict(skill='きゅうしょ突き')),
        ('とうぞく', 'まほうつかい', dict(skill='マホトラ')),
        ('とうぞく', 'おどりこ', dict(skill='マホトラおどり')),
        ('とうぞく', 'わらわせし', dict(skill='しのび笑い')),
        ('おどりこ', 'せんし', dict(skill='つるぎのまい')),
        ('おどりこ', 'ぶとうか', dict(skill='マッスルダンス')),
        ('おどりこ', 'まほうつかい', dict(skill='マホキテ')),
        ('おどりこ', 'そうりょ', dict(skill='死のおどり')),
        ('おどりこ', 'とうぞく', dict(skill='マホトラおどり')),
        ('おどりこ', 'ふなのり', dict(skill='船上ダンス')),
        ('おどりこ', 'ひつじかい', dict(skill='ひつじのダンス')),
        ('おどりこ', 'わらわせし', dict(skill='ステテコダンス')),
        ('ぎんゆうしじん', 'せんし', dict(skill='たたかいの歌')),
        ('ぎんゆうしじん', 'ぶとうか', dict(skill='おたけび')),
        ('ぎんゆうしじん', 'まほうつかい', dict(skill='のろいの歌')),
        ('ぎんゆうしじん', 'そうりょ', dict(skill='やすらぎの歌')),
        ('ぎんゆうしじん', 'ふなのり', dict(skill='さざなみの歌')),
        ('ぎんゆうしじん', 'ひつじかい', dict(skill='ひつじかぞえ歌')),
        ('ぎんゆうしじん', 'わらわせし', dict(skill='コミックソング')),
        ('ふなのり', 'せんし', dict(skill='かもめ返し')),
        ('ふなのり', 'ぶとうか', dict(skill='すいめんげり')),
        ('ふなのり', 'まほうつかい', dict(skill='いなずま')),
        ('ふなのり', 'そうりょ', dict(skill='ノアのはこぶね')),
        ('ふなのり', 'おどりこ', dict(skill='船上ダンス')),
        ('ふなのり', 'ぎんゆうしじん', dict(skill='さざなみの歌')),
        ('ひつじかい', 'せんし', dict(skill='みねうち')),
        ('ひつじかい', 'ぶとうか', dict(skill='マトンアタック')),
        ('ひつじかい', 'まほうつかい', dict(skill='ラリホーマ')),
        ('ひつじかい', 'そうりょ', dict(skill='スクルト')),
        ('ひつじかい', 'おどりこ', dict(skill='ひつじのダンス')),
        ('ひつじかい', 'ぎんゆうしじん', dict(skill='ひつじかぞえ歌')),
        ('わらわせし', 'せんし', dict(skill='へんてこ斬り')),
        ('わらわせし', 'ぶとうか', dict(skill='しっぺ返し')),
        ('わらわせし', 'まほうつかい', dict(skill='メダパニ')),
        ('わらわせし', 'とうぞく', dict(skill='しのび笑い')),
        ('わらわせし', 'おどりこ', dict(skill='ステテコダンス')),
        ('わらわせし', 'ぎんゆうしじん', dict(skill='コミックソング')),
        #('けんじゃ', 'スーパースター', dict(skill='メガザルダンス')),
        ))

    if nx.is_eulerian(G):
        print_cycle(G)

def print_cycle(G, source=None):
    """Print an Eulerian cycle in G.

    Args:
      G: A Graph.
      source: Starting node for circuit.

    Returns:
      None
    """

    skills = nx.get_edge_attributes(G, 'skill')
    try:
        for i in nx.eulerian_circuit(G, source):
            if i in skills:
                skill = skills[i]
            else:
                skill = skills[(i[1], i[0])]
            print(f'{i} {skill}')
    except nx.NetworkXError as ex:
        print(ex)

if __name__ == '__main__':
    main()

これをこのまま実行すると、オイラー閉路を標準出力に書き出さずに終了してしまう。これでグラフがオイラーグラフではないことがわかった。しかし希望はある。元々グラフに期待しているのは（準）オイラーグラフであることなので、オイラー閉路でないのは仕方がないのだ。そこで、このグラフを少々加工してオイラーグラフ化することを考える。ゲーム的に言えば、無駄な職歴を少しは重ねることを認める。

具体的には、元のグラフの奇点を列挙して、それらの間に上手にエッジを追加または削除をして（準）オイラーグラフ化する。まず、各ノードの位数を G.degree() で確かめる。次の出力は pprint.pprint(G.degree()) の結果である。

{'おどりこ': 8,
 'ぎんゆうしじん': 7,
 'せんし': 6,
 'そうりょ': 4,
 'とうぞく': 5,
 'ひつじかい': 6,
 'ふなのり': 6,
 'ぶとうか': 7,
 'まほうつかい': 7,
 'わらわせし': 6}

「ぎんゆうしじん」、「とうぞく」、「ぶとうか」、「まほうつかい」の四職業が奇点だ。先程のコードを見ると、上手い具合に「ぎんゆうしじん」「ぶとうか」の間および「とうぞく」「まほうつかい」の間にエッジがある。前者のエッジのスキルは「おたけび」であるが、これは職歴技としては価値ゼロであり（なぜなら「ぶとうか」単体でカバーできるから）、後者のエッジのスキル「マホトラ」は習得呪文としてはレアなので、早いうちにマスターしたい。

関数 nx.eulerian_circuit

というわけで、先のコードの print_cycle 呼び出し以降に次の処理を入れることで、オイラー閉路が得られる。 「マホトラ」エッジの端点である「まほうつかい」をオイラー閉路の始終点に指定しよう。

    G.remove_edge('ぎんゆうしじん', 'ぶとうか')
    G.remove_edge('まほうつかい', 'とうぞく')

出力例を示す。なお、関数 nx.eulerian_circuit の結果は実行するごとにランダムに変わるようなので、再度実行してもこれと同じ結果が得られない場合がある。

('まほうつかい', 'わらわせし') メダパニ
('わらわせし', 'ぶとうか') しっぺ返し
('ぶとうか', 'ひつじかい') マトンアタック
('ひつじかい', 'ぎんゆうしじん') ひつじかぞえ歌
('ぎんゆうしじん', 'ふなのり') さざなみの歌
('ふなのり', 'そうりょ') ノアのはこぶね
('そうりょ', 'ひつじかい') スクルト
('ひつじかい', 'せんし') みねうち
('せんし', 'わらわせし') へんてこ斬り
('わらわせし', 'ぎんゆうしじん') コミックソング
('ぎんゆうしじん', 'そうりょ') やすらぎの歌
('そうりょ', 'おどりこ') 死のおどり
('おどりこ', 'わらわせし') ステテコダンス
('わらわせし', 'とうぞく') しのび笑い
('とうぞく', 'せんし') ぬすっと斬り
('せんし', 'ふなのり') かもめ返し
('ふなのり', 'ぶとうか') すいめんげり
('ぶとうか', 'とうぞく') きゅうしょ突き
('とうぞく', 'おどりこ') マホトラおどり
('おどりこ', 'ふなのり') 船上ダンス
('ふなのり', 'まほうつかい') いなずま
('まほうつかい', 'ぶとうか') 火の息
('ぶとうか', 'おどりこ') マッスルダンス
('おどりこ', 'ひつじかい') ひつじのダンス
('ひつじかい', 'まほうつかい') ラリホーマ
('まほうつかい', 'ぎんゆうしじん') のろいの歌
('ぎんゆうしじん', 'せんし') たたかいの歌
('せんし', 'おどりこ') つるぎのまい
('おどりこ', 'まほうつかい') マホキテ

このオイラー閉路職歴の最初または最後に「とうぞく」を追加したものが、本問題における最適キャリアの条件を満たす（実際にはモンスター職コンプリートや基本職固有の戦闘回数ノルマの大小も加味してパスを調整したい）。もっとも、2014 年現在では、PS 版オリジナルよりは職歴技システムが完全に廃止されている 3DS 版のリメイクを遊ぶほうがよさそうだが。