2次元配列で最長ルートを見つける

Question

私はこのような割り当てを得ました。私はいくつかの細胞が訪問することが禁じられている2D配列を得ました。次に、禁止された細胞に入ることなく最長の経路を選択して配列全体を横断する必要があります。私はまた "戻る"と別のターンを取ることはできません、トラバーサルは常に "前方に"行く必要があります。出力は、訪問されたセルの数と正しい順序でなければなりません。アルゴリズムは、少なくとも100x100セルの配列の場合にはスケーラブルでなければなりません。以下はその仕事を示す写真です。上の写真のように

、ちょうど2つのソリューションを実際にそこにある：ちょうど例のように、再び、エッジに沿って続く、その後、一つのセルを下に移動して、どちらかが。それとも、それは完全なエッジに沿って続くことができます。訪問した細胞の数は依然として同じでなければなりません。 12.

これで多くのバリエーションが見つかりました。私は、おそらくDjikstras、Bellman-Ford、A *アルゴリズム、または何らかの種類のDepth/Breadth-first traversalを使用できるはずです。しかし、私は完全に立ち往生して、ここからどこに行くべきか分からない。

Answer 1

A. Itai, C. Papadimitriou, J. Szwarcfiter, Hamiltonian paths in grid graphsに示すように、この問題はNPハードです。したがって、正確な多項式時間アルゴリズムは存在しない。

実際には、あなたのサイズの問題は近代的なConstraint Solversで解くべきです。最も長い経路探索のためにConstraint Problemを作る方法の見直しは、Q. Pham, Y. Deville, Solving the Longest Simple Path Problem with Constraint-Based Techniquesで見つけることができる。