最近、技術面接でこの質問をされました。これが私の解決策です。http://pastebin.com/JMVHcfRq間違えましたか、それとももっと良い解決策がありますか?
選択した言語の数字の長方形グリッドで、隣接する非反復セル (対角線を含む) を通る最長の非減少シーケンスの長さを見つけます。ソリューションは、任意の幅と高さのグリッドを処理する必要があります。
たとえば、次のグリッドでは、トレースできる有効なパス (最長ではありませんが) は 0->3->7->9 であり、その長さは 4 です。
8 2 4
0 7 1
3 7 9
パス隣接する場所のみを接続できます (8 -> 9 を接続することはできません)。この例で可能な最長のシーケンスは、パス 0->2->4->7->7->9 または 1->2->4->7->7->8 をトレースすることにより、長さ 6 になります。
選択した言語で、数値の長方形グリッドを入力として取り、そのような最長のシーケンスの長さを出力として返すメソッドを作成します。
有向グラフを使用して問題をモデル化できます。
各セルはグラフの頂点であり、2 つのセル C i,j、C k,mが隣接し、C i,j < C k, m の場合、C i,j →C k,mのエッジがあります。
問題はこのグラフで最長パスを見つけることですが、このグラフは有向非巡回グラフです。問題が言うように、マトリックスには繰り返し数がなく、「<」関係も反対称であるためです。したがって、問題は有向非巡回グラフで最長パスを見つけるようになりました。これは、最初にトポロジカルソートを実行してから最長パスを見つけることで簡単です。たとえば、これを参照してください。
更新: 一見したところ、等しい隣人を持つことは不可能だと思っていましたが、今では可能であることがわかりました。上記のグラフの構築では、< を <= に置き換える必要があります。グラフは非循環的ではありませんが、それでも問題はこれで最長パスを見つけることです。グラフ。
P.S1: この最長パスの問題に対する多項式の答えがあれば、ここに持ってきますが、この問題の分類により、その周りを検索しやすくなる可能性があります。
P.S2: mbeckishがコメントで述べたように、最長パスの問題は一般的なグラフでは NP-Hard ですが、この特別なケースでは P で解決できると思いますが、現在正確なアルゴリズムはありません。
P.S3: 私はそれについて少し調査を行います。グリッド グラフのハミルトニアン パスは NP-Completeであることがわかりました。したがって、あなたの問題も NP-Complete のようです (現在は縮約はありませんが、それぞれに非常に近いです)他の）。
また、n dijkstra 呼び出しを使用して (最大パスを見つけるためにそれを逆にします)、O(n^3) で解決できます。最大ヒープを使用すると、それを 0(n^2 log n) に下げることができます。グラフを作成するときは、現在の頂点に対して >= である近傍へのエッジのみを作成します。
トポロジカル ソートを試みましたが、グラフにサイクルが見つかりました。私のコードを確認する必要があります。