これを 2 次元で解決しようとしており、説明されているもの以外の問題については、より一般的な解決策を検討してみましょう。有向グラフの最短経路問題を解こうとしています。
グラフの現在の表現は のようなものa -> [a]で、関数は入力から到達可能な頂点を返します。どの実装でも、2 つの頂点が同じかどうかを比較して確認できるようにする必要があるため、 が必要になりますEq a。
次のグラフは問題があり、一般的に問題を解決する際のほとんどすべての困難を紹介しています。
problematic 1 = [2]
problematic 2 = [3]
problematic 3 = [2]
problematic 4 = []
1 から 4 に到達しようとすると、1 から 4 へのパスがないと判断するために検出する必要がある 2 と 3 を含むサイクルがあります。
幅優先探索
ウィルが提示するアルゴリズムは、有限グラフの一般的な問題に適用された場合、時間と空間の両方で無制限の最悪の場合のパフォーマンスを示します。サイクル検出を追加することにより、有限パスと有限サイクルのみを含むグラフの一般的な問題を攻撃するように彼のソリューションを変更できます。彼の元の解決策とこの変更は、無限グラフでも有限パスを見つけますが、無限グラフの 2 つの頂点間にパスがないと確実に判断することはできません。
acyclicPaths :: (Eq a) => (a->[a]) -> a -> a -> [[a]]
acyclicPaths steps i j = map (tail . reverse) . filter ((== j).head) $ queue
where
queue = [[i]] ++ gen 1 queue
gen d _ | d <= 0 = []
gen d (visited:t) = let r = filter ((flip notElem) visited) . steps . head $ visited
in map (:visited) r ++ gen (d+length r-1) t
shortestPath :: (Eq a) => (a->[a]) -> a -> a -> Maybe [a]
shortestPath succs i j = listToMaybe (acyclicPaths succs i j)
ウィルの回答の関数を問題例の定義として再利用するstepと、11 階建ての建物の 4 階から 5 階までの最短経路の長さを で取得できますfmap length $ shortestPath (step 11) 4 5。これは を返しますJust 3。
v 個の頂点と e 個の辺を持つ有限グラフを考えてみましょう。v 個の頂点と e 個の辺を持つグラフは、サイズ n ~ O(v+e) の入力によって記述できます。このアルゴリズムの最悪の場合のグラフは、到達不能な頂点 が 1 つjあり、残りの頂点と辺が から始まる最大数の非巡回パスの作成に費やされることiです。iこれはおそらく、またはではないすべての頂点を含むクリークのようなものであり、 からではない他のすべての頂点へのjエッジがあります。e 個のエッジを持つクリークの頂点の数は O(e^(1/2)) なので、このグラフは e ~ O(n), v ~ O(n^(1/2)) になります。このグラフには、O((n^(1/2))!) 個のパスがあり、到達不能であると判断する前に探索する必要があります。ijj
この場合、この関数が必要とするメモリは O((n^(1/2))!) です。これは、パスごとにキューを一定に増やすだけでよいためです。
この場合、この関数に必要な時間は O((n^(1/2))! * n^(1/2)) です。パスを展開するたびに、新しいノードがまだパスにないことを確認する必要があり、これには O(v) ~ O(n^(1/2)) の時間がかかります。訪問した頂点を保存するためにまたは同様の構造をOrd a使用した場合、これは O(log (n^(1/2))) に改善される可能性があります。Set a
非有限グラフの場合、この関数は、 からiへの有限パスが存在しないが、 からへjの非有限パスが存在する場合にのみ終了に失敗する必要があります。ij
動的計画法
動的計画法のソリューションは、同じ方法で一般化することはできません。その理由を探ってみましょう。
まず、chaosmasttter のソリューションを適応させて、幅優先探索ソリューションと同じインターフェイスを持たせます。
instance Show Natural where
show = show . toNum
infinity = Next infinity
shortestPath' :: (Eq a) => (a->[a]) -> a -> a -> Natural
shortestPath' steps i j = go i
where
go i | i == j = Zero
| otherwise = Next . foldr minimal infinity . map go . steps $ i
これは、エレベータの問題でうまく機能しshortestPath' (step 11) 4 5ます3。残念ながら、問題のある問題でshortestPath' problematic 1 4は、スタックがオーバーフローします。Natural数値のコードをもう少し追加すると、次のようになります。
fromInt :: Int -> Natural
fromInt x = (iterate Next Zero) !! x
instance Eq Natural where
Zero == Zero = True
(Next a) == (Next b) = a == b
_ == _ = False
instance Ord Natural where
compare Zero Zero = EQ
compare Zero _ = LT
compare _ Zero = GT
compare (Next a) (Next b) = compare a b
最短経路が上限よりも短いかどうかを尋ねることができます。私の意見では、これは遅延評価で何が起こっているかを実際に示しています。problematic 1 4 < fromInt 100です。False_ problematic 1 4 > fromInt 100_True
次に、動的計画法を調べるために、動的計画法を導入する必要があります。すべての下位問題に対する解の表を作成するため、頂点が取り得る可能な値を知る必要があります。これにより、わずかに異なるインターフェースが得られます。
shortestPath'' :: (Ix a) => (a->[a]) -> (a, a) -> a -> a -> Natural
shortestPath'' steps bounds i j = go i
where
go i = lookupTable ! i
lookupTable = buildTable bounds go2
go2 i | i == j = Zero
| otherwise = Next . foldr minimal infinity . map go . steps $ i
-- A utility function that makes memoizing things easier
buildTable :: (Ix i) => (i, i) -> (i -> e) -> Array i e
buildTable bounds f = array bounds . map (\x -> (x, f x)) $ range bounds
shortestPath'' (step 11) (1,11) 4 5これはまたはのように使用できますshortestPath'' problematic (1,4) 1 4 < fromInt 100。これはまだサイクルを検出できません...
動的計画法とサイクル検出
サブ問題は、異なるパスからアプローチされた場合に同じではないため、動的計画法ではサイクル検出が問題になります。problematic私たちの問題の変形を考えてみましょう。
problematic' 1 = [2, 3]
problematic' 2 = [3]
problematic' 3 = [2]
problematic' 4 = []
1からに移動しようとしている場合4、次の 2 つのオプションがあります。
- に行き、からへ
2の最短経路を取る24
- に行き、からへ
3の最短経路を取る34
探索することを選択した場合2、次のオプションに直面します。
3からへの最短経路の 2 つの探索を4テーブルの同じエントリに結合したいと考えています。サイクルを回避したい場合、これは実際にはもう少し微妙なことです。私たちが実際に直面した問題は次のとおりです。
- に行ってから、訪問しない
2最短経路を2たどる41
- に行ってから、訪問しない
3最短経路を3たどる41
選択後2
2 つのわずかに異なる答え3を得る方法についてのこれらの 2 つの質問。4これらは、テーブルの同じ場所に収まらない 2 つの異なるサブ問題です。4最初の質問に答えるには、最終的にfromに到達できないと判断する必要があります2。2 番目の質問への回答は簡単です。
以前に訪れた頂点の可能なセットごとに一連のテーブルを作成することもできますが、それはあまり効率的ではないようです。遅延のみを使用した動的プログラミングの問題として到達可能性を実行することはできないと、私はほとんど確信しています。
幅優先探索還元
到達可能性またはサイクル検出を使用した動的計画法ソリューションに取り組んでいるときに、オプションでノードを確認すると、そのノードをたどるかどうかに関係なく、そのノードにアクセスするパスが最適になることはないことに気付きました。再考するとproblematic'：
1からに移動しようとしている場合4、次の 2 つのオプションがあります。
- に行き、 、、またはを訪問せずにからへ
2の最短経路を取る24123
- に行き、 、、またはを訪問せずにからへ
3の最短経路を取る34123
これにより、最短経路の長さを非常に簡単に見つけるアルゴリズムが得られます。
-- Vertices first reachable in each generation
generations :: (Ord a) => (a->[a]) -> a -> [Set.Set a]
generations steps i = takeWhile (not . Set.null) $ Set.singleton i: go (Set.singleton i) (Set.singleton i)
where go seen previouslyNovel = let reachable = Set.fromList (Set.toList previouslyNovel >>= steps)
novel = reachable `Set.difference` seen
nowSeen = reachable `Set.union` seen
in novel:go nowSeen novel
lengthShortestPath :: (Ord a) => (a->[a]) -> a -> a -> Maybe Int
lengthShortestPath steps i j = findIndex (Set.member j) $ generations steps i
さすが、lengthShortestPath (step 11) 4 5です。_Just 3lengthShortestPath problematic 1 4Nothing
最悪の場合、generationsO(v*log v) のスペースと O(v*e*log v) の時間が必要になります。
