問題タブ [longest-path]

グリッド上の 2 点間の最長パスを見つけるアルゴリズムを探していますが、グリッド上のセルを再訪できないという制限が追加されています。(また、上下左右にしか移動できません)。

これらの制限を考えると、最長の道を歩くことは、できるだけ多くのスペースを埋めようとすることと同じだと思います. ただし、これを行う方法を理解するのは少し難しいです。

グリッド G を指定します。各セルには、[0 - 9] の数字または大文字のアルファベット (Z など) を含めることができます。左上隅から始めることができます。次に、現在のセル番号が a の場合、セルを正確に上下左右に移動できます。アルファベット文字に到達するまで停止します。これらのルールを考慮して、最初からグリッドから出るまでの最大パスを見つけたいと考えています。パスが無限の場合は、「-1」を出力します。

私はゲーム ソルバーの作成に約 1 か月間取り組んでおり、さまざまな戦略を試していますが、そのほとんどはブルート フォースに重点を置いています。これは、ゲームの単純なケースでは機能しますが、より複雑なケース (ゲーム ツリーの深さが高い) では失敗します。以下は、ゲームの抽象的な定式化です。

1) 実行可能な一連のアクションがあります。A.

2) 状態にアクションを適用すると、可能な状態の確率分布が生成されます。apply(A, s) = [[s1, p1], [s2, p2], [s3, p3]]

3) ゴール状態に到達するとゲームは終了します。

4) 各状態には、それに関連付けられたスコアがあります。

3) 目標状態には、状態のスコアが前の状態のスコアである「成功」状態と、スコアが 0 である「失敗」状態の 2 種類があります。

5) 目標は、ゲーム終了時の平均スコアを最大化する戦略を作成することです。

6) サイクルはありません。すべてのパスには有限の長さがあります。

私はこのゲームを可能な限り抽象的な意味で定式化しました。私の現在の戦略は、作業の重複を防ぐために一意の状態をキャッシュする単純な深さ優先検索です。これは、メモリが不足する約 2 億の一意の状態まで機能します。最適化を見つけるために下位レベルの詳細を分解する前に、ゲームの一般的なケースに適した巧妙なアルゴリズムがあるかどうかを知りたい. 状態遷移がどのように生成されるかの詳細に興味がある場合は、提供できます。問題を既知の問題に減らすいくつかの方法を次に示します。

1) 状態報酬関数が非ゴール状態の場合は 0 であり、それ以外の場合はゴール状態のスコアである確率的マルコフ決定プロセス。MDP の一般的なアルゴリズムがあまり効率的でないことはわかっていますが、MDP の特定のクラスには効率的なソリューションがあります。この問題は、これらの特定のクラスのいずれかに当てはまりますか?

2) 辺の重みが負の有向非巡回グラフにおける確率的最長経路問題。

最小スパニングツリーで、すべてのノードから最も遠いノードまでの距離を見つける必要があります。これまでにこれを行いましたが、ノードからの最長距離を見つける手がかりがありませんでした。

ノード 1 2 3 4 を持つスパニング ツリーがある場合、スパニング ツリーで 1 2 3 4 からの最長距離を見つける必要があります (最長距離は、1 つだけでなく多くのエッジで構成できます)。

文字列の非常に大きな DAG (~200k) があります。このグラフに存在する最長パスを見つけたいと思います。以下のコードは、(文字列のリストから) グラフを設定した方法ですnew_list。

私は、すべてのノードから他のすべてのノードへのパス距離をチェックする単純なアプローチを試みました...これは明らかに非現実的であり、終了しません。

また、このスレッドのlongest_path()コードを作り直そうとしましたが、役に立ちませんでした。

トポロジカルソートの実行とグラフの順序付けについて理解できることについて多くのことを読みましたが、これを実装するのに問題があります。Networkx は function を提供するtopological_sort(g)ので、作業は私のために行われます。しかし、topo_sorted グラフができたので、ここからどのように進めればよいでしょうか?