チェスボードパズルでナイトの最短経路にOCaml再帰的ソリューションのスタックオーバーフロー

Question

質問はここに記載されています：Knight's Shortest Path Chess Question。

let is_in_list x s = List.exists (fun y -> if y = x then true else false) s;; (* find out if an element belongs to a list *) 

let next_step n = [n+10;n-6;n+6;n-10;n+17;n-17;n+15;n-15];; 

let rec legal_next_step = function 
    |[]->[] 
    |x::s-> 
    if x<0 or x>63 then legal_next_step s 
    else x::legal_next_step s;; 

let find_next_step n = legal_next_step (next_step n);; (* here is to find all the valid next moves and put them into a list*) 

let rec min s = 
    let rec loop result = function 
    |[]->result; 
    |x::s-> 
     if x < result then loop x s 
     else loop result s in 
    loop (List.hd s) s;; 

let rec find_shortest_path n m = 
    if is_in_list m (next_step n) then 1 
    else 
    1 + min (List.map (fun x -> find_shortest_path x m) (find_next_step n)) ;; 

これは、「スタックオーバーフロー」の問題を引き起こします。これは、次のような直感的な再帰的な方法を使用して解決しようとしました。何故ですか？私のプログラムはスタック内で再帰呼び出しのレイヤーを非常に多く作成していますか？または、私のコードで何かがひどく間違っています。そして、これらすべての結果の最小値を計算する -

Answer 1

はあなたが

List.map (fun x -> find_shortest_path x m) (find_next_step n)) 

を書くときあなたは、文字通りすべての可能な隣人から「ここから最短経路」すべてを計算することを理解する必要があります。

だからあなたのコード内の無限ループがあります：あなたが位置Aから開始し、その隣人Bの1からの最短経路を計算しようとした場合、その後、Bから呼び出さfind_shortest_pathは必然的に、パスは次のようになり時間の長さを表示しようとします彼の最初の動きがAに戻っていたならば。したがって、試行される可能性がある他のすべての移動の中で、ループA-B-A-B-A-B...の「長さ」、つまり無限ループを計算します。

その問題を回避するには、いくつかの方法があります（それ自体はそれはOCamlのプログラミングに関連していないが、それはどの言語でもマニフェストになり、プログラムのロジックのエラーです）：

• 代わりbreadth-first searchを使用奥行きの最初の検索を行うことができます。これにより、指定された長さのすべてのパスを段階的に探索し、見つかった最小の勝利パスで停止します。もしあなたが望むならば、これはすべてのパスを並行して探索することに相当するので、無限のパス全体を探索しようとする前に停止する限り（無限のパスを持つことができます）。 「戻る」しないように、あなたは深さ優先使用する場合は、すでに

  • （これはあなたの目的地に到達するための最短の道になることはありません）、訪問した場所は、これらのマークがなければならないので、これは繊細で検索します（単にブール値の行列を変更することはできません）。たとえば、int listパラメータをfind_shortest_path関数に追加できます。これは、現在探索されているパスの一部である場所のリストになります。可能なネイバーから最短パスを計算しようとする前に、それがこのリストにないことを確認してください。より効率的なものを得るには、セット（module IntSet = Set.Make(struct type t = int let compare = Pervasives.compare)）（リニアの代わりに、メンバーシップ・テストの対数）を使用するか、異なるパスを選択したときに状態の変化を慎重に注意しながら、可変ブール・マトリックスを使用します。

  • 幅優先検索を使用する場合は、指定した長さまですべてのパスを同時に探索するため、「あなたが既に訪れた場所」のグローバルブール値行列を使用できます。すでに訪れているとマークされている場所に出くわした場合は、別のパスが以前に訪れたことを知っているので、すでにあなたより先行しており、そこから最短パスを取得しようとすることはありません。

だから、短い答えは：あなたは、幅優先探索について学ぶ必要があります。

Answer 2

まあ、次の合法的計算は私には間違っています。私が右下にいる（正方形7、言う）場合、私は正方形1に移動することはできません。これはループを引き起こすべきではありませんが、それはちょうど間違った答えを取得する必要があります。

私が推測しているのは、非常に長く失敗したパスをたどっているということです。私はあなたが最初に深みではなく幅優先探索をする必要があると思います。本質的には、到達可能な四角形のセットを保持し、それぞれの到達可能なスポットをで1つ進め、それぞれのステップでを移動します。あなたのコードは、常に新しい場所から目的地に到達しようとします。したがって、（おそらく）多くの長い道をたどります。