algorithm - グリッド セルを再訪することなく、グリッド上の最長パス

Question

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

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

Answer 1

最長パスの問題は、一般的なグリッドグラフ (あなたが説明している種類) では依然として NP 困難です。

これは、ハミルトニアン パスが一般的なグリッド グラフで NP 完全であるためです。削減は同じです。高速な最長パス ソルバーは、ノードのすべてのペア間の最長パスの長さを と比較するだけで、すぐに高速なハミルトニアン パス ソルバーを提供しますn-1。