ハスケル-騎士の動き

学校の子供時代、娯楽の1つは、馬の動きに合わせて箱の中のノートブックにある種の長方形mx nを塗りつぶすことでした。 通常は10x10の正方形でしたが、今では唇を噛んで（舌を突き出して）、セルに慎重に数字を入力します。 次のステップで、あなたは行き​​止まりにいることを理解し、最初からやり直します。 これはかなり前のことであり、真実ではありませんでしたが、Haskell言語を勉強しているときに、 https：//wiki.haskell.org/99_questions番号91の一般リストでこのタスクに出会いました。



実際に、この問題を解決するにはどうすればよいですか。 「Haskellを善の名で探検してください」という本の著者の戒めを思い出してください。これは「再帰的に考える」ように聞こえます。 つまり、一連のセルからいくつかのセルを取得し、残りを何らかの方法で埋め、元のセルが満たされた「馬の動き」に接続することを確認します。 さて、「どういうわけか残りを埋める」とは、セルのセットを減らして再帰に入ることを意味します。 遅かれ早かれ、セットは単一の要素に縮小され、これが再帰の基礎になります。 リストデザイナを使用したコードでは、たとえば次のように記述できます。

knightComb [x] = [[x]] knightComb xs = [x:ks | x <- xs, ks <- knightComb $ delete x xs, near x $ head ks] where near (x1,y1) (x2,y2) = abs ((x2-x1)*(y2-y1)) == 2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

言語データベースには削除機能はありませんが、Data.Listモジュールからロードできます。



組み合わせ関数の入力では、セルのセットが座標ペア（x、y）のリストの形式で表示され、出力では、このセットをバイパスするすべての可能な方法のリストが表示されます。 すべてのオプションが必要ではなく、任意の1つで十分な場合は、 head関数を使用して最初のオプションを使用できます。その後、Haskellの遅延により、残りは計算されません。 しかし！ 紙の上では滑らかでした。 アルゴリズムは実際に機能し、中央のセルのない3x3の正方形はバタンと塗りつぶされます。 3x4の長方形では、最初の結果は数分後に表示されますが、セルを1つ追加するだけでこの時間は30分に増えます。 大きなスペースについては、どもることもできません。



まあ、原則として、結果は説明可能です。 最初のセルの正しい選択は、再帰のために出た後にチェックされます。最初は、多くのセルがあり、すべてが適合するわけではありません。したがって、怠lazにもかかわらず、検索の複雑さはN！のオーダーです。出力で取得するため、遅延が引き続き機能します。余分な検索を何らかの方法で制限する必要があります。



正確にどのように？ 最初に頭に浮かぶのは、最初に任意のセルではなく、前の動きから取得できるセルを取得することです。 つまり 空きセルのセットに加えて、最後に占有されたセルの座標を再帰入力に転送し、それを使用して可能な移動のリストを作成し、これらのセルが空であることを確認し、セルが終了するまで新しい移動で再び再帰に入ります。

 knightsTo x [] = [[x]] knightsTo x xs = [x:ks | k <- next x, elem k xs, ks <- knightsTo k $ delete k xs] where next (x,y) = [(x+dx,y+dy) | (dx,dy) <- [(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)] ]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そのようなもの。 さて、便宜上、インターフェースを作成します

 knights n = head . knightsTo (1,1) $ tail [(x,y) | x <- [1..n], y <- [1..n]]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、私は言わなければならない、これは顕著な前進です！











そして忍耐があるなら





10x10の正方形では、結果を待ちませんでした。 しかし、それにもかかわらず、再帰の各ステップで、新しい呼び出しの数は現在、フリーセルの数ではなく、可能な移動の数に依存します。 つまり アルゴリズムの複雑さはO（p ^ N）になりました。 多項式でもありませんが、すでに進んでいます。



次の関数は余分な動きを生成する可能性がありますが、それはelemチェックによって切断されますが、リストを8回実行することは非効率的です。 空きセルのリストを一度実行して、適切なセルを除外する方が理にかなっています。

 knightsTo x [] = [[x]] knightsTo x xs = [x:ks | k <- filter (near x) xs, ks <- knightsTo k $ delete k xs] where near (x1,y1) (x2,y2) = abs ((x2-x1)*(y2-y1)) == 2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

しかし、実際には、これはパフォーマンスにまったく影響を与えないことが示されています。ほぼ同時に、まったく同じ答えがあります。 実際、アルゴリズムの複雑さはまったく変化していません。ただし、可能な移動は次の関数で厳密に定義された順序ではなく、空きセルのリストに表示される順序で選択されます。 そして、部分的に順序付けられたセットでは、ソリューションはより高速になります。 順不同のセットでは、それぞれ停止することがよくあります。



他にどのように不必要なバスティングを制限できますか？ たとえば、再帰の各ステップで、孤独なセルがないかどうかの入力リストの追加チェックを編成することができます。 入力セット内の各空のセルには、セット全体が1つのセルで構成されていない限り、少なくとも1つの空きネイバーが必要です。 ただし、このテストの後、カップル、トリプルなどはスローされたままになる可能性があります。 セル。 そして、一般化するには、残りの領域全体の接続性を確認する必要があります。 また、一般的な接続とは、現在の位置から残りのセルへのパスが必要であることを意味します。 このようなチェックは、たとえば、補助関数を作成する「ワイド」バイパスアルゴリズムによって実行できます。

 connected _ [] = True connected [] _ = False connected (x:xs) ws = let ns = filter (near x) ws in connected (xs++ns) (ws\\ns)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

入力関数には2つのリストがあります。チェックされた頂点と未検証の頂点です。2番目の頂点が空になった場合、領域グラフは接続されます。



メイン関数に新しいチェックを追加します

 knightsTo x [] = [[x]] knightsTo x xs = [x:ks | connected [x] xs, k <- filter (near x) xs, ks <- knightsTo k $ delete k xs]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、近傍チェック機能をグローバルに記述します

 near (x1,y1) (x2,y2) = abs ((x2-x1)*(y2-y1)) == 2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それはかなりうまくいきます！ 9x9スクエアのソリューションは、8x8スクエアに以前必要だった時間よりも高速になりました。 これは、追加チェックの複雑さが入力データに二次的に依存するという事実にもかかわらずです。 しかし、アルゴリズムの全体的な複雑さは指数関数的であるため、そのコストであっても不要な分岐を破棄すると、計算が大幅に削減されます。



発行されたソリューションを分析すると、移動選択アルゴリズムがエリアの左側の部分を密に埋めようとしていることがわかります。少なくとも最初はうまく機能します。これは、大きなエリアを小さなコンパクトなスペースに分割するというアイデアを示唆しています。 素晴らしいアイデア！ 10x10の問題の正方形は4つの5x5の正方形で、ナットのようにクリックします。 特定のポイントから開始する方法を学習する必要があるだけでなく、指定した場所で終了します。 これを行うには、インターフェイス関数を変更します

 knights5 ((m,n), st, fin) = head . filter (end fin) . knightsTo st $ delete st [(x,y) | x <- [m..m+4], y <- [n..n+4]] where end x xs = x == last xs
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

領域のサイズを固定し、入力時に5x5の正方形の左下隅の座標、目的のパスの開始点と終了点の座標を指定します。 そして、この関数を4回、目的のパラメーターに適用します。

 knights10 = concatMap knights5 [((1,1),(5,3),(5,5)), ((1,6),(3,6),(5,6)), ((6,6),(6,8),(6,6)), ((6,1),(8,5),(6,5))]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

出来上がり！





数秒待ってから、さらに複雑なタスクの解決策を見つけました。 馬のコースで見つかったパスの終わりから、最初に到達できます。 私たちの決定は周期的です。



実際、完全な幸福のために、適切なチェーンを構築して、大きなエリアを小さなエリアに分割するプロセスを自動化するだけです。 しかし、彼らが言うように、これはまったく別のタスクです。



パート2

パート3