問題の定式化をより正確にするために、「都市」ゲームとして再定式化させてください。2 人でプレイします。プレーヤー 1 は都市名を言いMoscowます。プレーヤー 2 は、以前に呼び出された都市の最後の文字から始まる都市名を言わなければなりません。この文字はWですので、2 番目のプレーヤーは のように言いますWashington。N次に、プレイヤー 1 はasで始まる都市を呼び出しNorilsk、プレイヤー 2 は都市名を言う必要がありますK。都市の名前を言えない人はゲームに負けます。
a..zここで、文字をグラフの頂点として、都市名のリスト (たとえば 10000) をエッジとして持っているとします。すべてのエッジは 2 つの頂点を接続し ( と をmoscow接続するようmにw)、向きを合わせm -> wます。
これでマルチグラフの方向性が決まりました。
タスクは、リストで指定された都市の可能な限り長いシーケンスを見つけることです。すべての都市が順番に出現するのは 1 回だけです。したがって、タスクはオイラー パスに非常に近いですが、与えられたグラフには多くのオイラー サブグラフが存在する可能性があります。
私の質問は、妥当な時間内に最大パスを見つける方法ですか?
私は、最大オイラーサブグラフ問題が NP 困難であることを知っています。しかし、私の問題では、グラフは非常に強く接続されており、少数の固定数の頂点があります (上記の「都市」ゲームのように)。それを使用して、優れたヒューリスティックを構築することは可能でしょうか?
また、stackoverflowでいくつかの単語シーケンスの質問を見つけましたが、合理的な答えはありません。単語がエッジの場合、文字グラフのオイラー部分グラフよりも、単語グラフのハミルトニアン部分グラフを見つけるのがはるかに難しいことは明らかであり、この質問はすべてハミルトニアンに関するものです。オイラーサブグラフではありません。
プログラミング言語または疑似コードでの有用なリンク、アイデア、アルゴリズムの説明、およびアプローチを高く評価します。
敬具、コンスタンチン