0

したがって、基本的に、float値のn x m配列があり、値の1行目とm行目の値の間の最短パスを見つけようとしています。(i, j)グラフのノードに{(i, j+1), (i-1, j+1), i+1, j+1)}は、端(0 < i < n-1)になく、一番下の行にないノードの子があり(j < m-1)ます。この特定の問題を適切なタイミングで解決するアルゴリズムを探しています。私の現在の考えは A* 検索を中心に展開していますが、あなたの考えを教えてください。

4

1 に答える 1

1
  • リスト項目

動的解は O(NM) または O(M^2) です。そして、それを下に置くことはできません-これは、より良い解決策の反例です。最初の行の左端の要素と最後の行の左端の要素の間のパスを見つけたいとしましょう。この形式の行列を見てみましょう。

10000000000000
11000000000000
11100000000000
11110000000000
11111000000000
11111100000000
11111110000000
11111111000000
11111110000000
11111100000000
11111000000000
11110000000000
11100000000000
11000000000000
10000000000000

「1」は、ソース要素から宛先要素へのパスで通過する可能性のある要素です。「0」は通過できない要素です。

「1」の数は NM/4 オーダーなので、O(NM) (実際には、Min(NM, M^2)、以下を参照)。したがって、この行列の各 1 を読み取るアルゴリズムは、>=O(NM) の複雑さになります。

一方、すべての「1」を読み取らないアルゴリズムは正しくありません。

証明: 行列の数を重みとします。アルゴリズムが読み取らない「1」を選択します。その 1 を 0.5 に変更します。最適なパスが決して読み取らない要素を通過するため、アルゴリズムはこの入力に対して失敗します (最初に読み取った要素はどれも変更されていないため、今回も同じ要素を読み取ります。それが機能するかどうかはランダムな可能性であり、これも不正確になります)。

ただし、優れた O(NM) ソリューションは、1000x1000 行列 (1 秒未満) に対しては問題なく機能するはずです。ヒットする必要がある要素のみをヒットする場合は、Min(M^2, MN) に最適化できます (たとえば、私の例のマトリックスでは、幅が 10000000 に増加した場合、追加された要素を読み取る必要はありません)。 ）。同様に、高さが 10000000 に増加した場合、行列の境界を超えないため、M^2 オーダーの読み取りはありません。ただし、両方の次元が非常に大きいと言うように、これはほとんど役に立たないと思います。

于 2012-05-14T11:20:39.220 に答える