スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#雑記 n-クイーン問題 パラレル化

有名どころのn-クイーン問題をやってみました。
 
まずはn=5の場合を考えます。
次の図のようにそれぞれのマスをint*intであるタプルで表します。
 
(0,0)(0,1)(0,2)(0,3)(0,4)
(1,0)(1,1)(1,2)(1,3)(1,4)
(2,0)(2,1)(2,2)(2,3)(2,4)
(3,0)(3,1)(3,2)(3,3)(3,4)
(4,0)(4,1)(4,2)(4,3)(4,4)
 
タプルには自動的に大小関係が入ります。例えば(i,j) > (3,3)を満たすマス(i,j)は(3,4)と(4,?)である5行目のマスすべてです。
また、このタプルをSetに入れて処理するのですが、Setに入れると自動的にソートされるので、for in doで取り出すと、左上から右へ、右端まで行くと、次の行の左端、そこから右へ...という順でマスが取り出されます。
またマスの大きさの小さい順にクイーンを置いていくというルールを作って、これに従ってクイーンを置いていくことにします。
 
ではまず、すべてのマスを生成してSetにいれます。
 
> let allPSet =
    [for i in 0 .. 4 do
        for j in 0 .. 4 do 
            yield (i,j)]
    |> Set.ofList ;;
 
val allPSet : Set<int * int> =
  set
    [(0, 0); (0, 1); (0, 2); (0, 3); (0, 4); (1, 0); (1, 1); (1, 2); (1, 3);
     ...]
 
 
ここで次のような関数を定義します。
 
> let removePs (i1,j1) set =
    Seq.filter (fun (i,j) ->((i,j) > (i1,j1) && i <> i1 && j <> j1 && i+j <> i1+j1 && i-j <> i1-j1)) set;;
 
val removePs : int * int -> seq<int * int> -> seq<int * int>
 
これはどんな関数かというとマス(i,j)に対して、「「大きさを比較したときに(i,j)より大きい」かつ「(i,j)と行が異ななっている」かつ「(i,j)と列が異なっている」かつ「(i,j)とななめ関係にない」」という、(i,j)にクイーンを置いた時に次に置くマスの候補の集合を返す関数になります。
(注意)「大きさを比較したときにそれより大きく」というのは、マスの大小関係で小さい順にクイーンを置くというルールから来ます。
 
ちょっと使ってみます。
> removePs (0,3) allPSet
|> Seq.iter (fun x -> printf "%A" x);;
(1, 0)(1, 1)(2, 0)(2, 2)(2, 4)(3, 1)(3, 2)(3, 4)(4, 0)(4, 1)(4, 2)(4, 4)val it : unit = ()
 
(0,3)に置いた時に次におけるマスの一覧になっています。
 
では次に再帰的に調べる部分を定義します。
 
> let rec search madeSet remSet count =  //madeSetは置いたマスのSet,remSetはまだおける場所、
                                         //countは置いたクイーンの個数
    [ if count = 4 then
        yield madeSet
      else
        for (i1,j1) in remSet do
          let newRemSet  = removePs (i1,j1) remSet  
          yield! (search (Set.add (i1,j1) madeSet)  newRemSet (count + 1))
    ];;
 
val search : Set<int * int> -> seq<int * int> -> int -> Set<int * int> list
 
では使ってみます。
 
> search  Set.empty allPSet 0;;
val it : Set<int * int> list =
  [set [(0, 0); (1, 2); (2, 4); (3, 1); (4, 3)];
   set [(0, 0); (1, 3); (2, 1); (3, 4); (4, 2)];
   set [(0, 1); (1, 3); (2, 0); (3, 2); (4, 4)];
   set [(0, 1); (1, 4); (2, 2); (3, 0); (4, 3)];
   set [(0, 2); (1, 0); (2, 3); (3, 1); (4, 4)];
   set [(0, 2); (1, 4); (2, 1); (3, 3); (4, 0)];
   set [(0, 3); (1, 0); (2, 2); (3, 4); (4, 1)];
   set [(0, 3); (1, 1); (2, 4); (3, 2); (4, 0)];
   set [(0, 4); (1, 1); (2, 3); (3, 0); (4, 2)];
   set [(0, 4); (1, 2); (2, 0); (3, 3); (4, 1)]]
 
では、これにn-クイーン化と少しの枝刈りとパラレル化を加えます。
 
なおパラレル化にともなう作業の分割のため、最初の行で、どの列にクイーンをおくか(1個目のクイーンをどこにおくか)で、作業を分割するようにしています。
 
以下コード
 
//上と同じ
let removePs (i1,j1) set =
    Seq.filter (fun (i,j) ->((i,j) > (i1,j1) && i <> i1 && j <> j1 && i+j <> i1+j1 && i-j <> i1-j1)) set
 
let solve parallellFlag n =
  let allPSet =
        [for i in 0 .. (n-1) do
           for j in 0 .. (n-1) do 
             yield (i,j)]
        |> Set.ofList 
 
//最初の行だけのSet
  let row0Set =
        Seq.filter (fun (i,_) -> i = 0) allPSet
    
  let rec search madeSet remSet count =
      [ if count = n then
            yield madeSet
        else
          if (Seq.length remSet)  >= (n - count) then  //##枝刈り1
              for (i1,j1) in remSet do
                if i1 = count  then  //##枝刈り2
                    let newRemSet  = removePs (i1,j1) remSet  
                    yield! (search (Set.add (i1,j1) madeSet)  newRemSet (count + 1))
       ]
 
  if parallellFlag = false then
    Array.map (fun x -> [yield!(search (Set.ofList [x]) (removePs x allPSet) 1)]) (Array.ofSeq row0Set) 
     |> List.ofArray
     |> List.concat
  else
    Array.Parallel.map (fun x -> [yield!(search (Set.ofList [x]) (removePs x allPSet) 1)]) (Array.ofSeq row0Set) 
     |> List.ofArray
     |> List.concat
 
 
なお「枝刈り1」では「残ってる候補マスの個数」が「残っているクイーンの個数」以上である。
「枝刈り2」では、n個目のクイーンは上からn行目に置く。
という意味合いで枝を刈ってます。
 
最後のArray.....の部分は、「パラレルとパラレルでないものの違いがArray.mapとArray.Parallel.mapのどちらを使うかの違いでけであること」を強調するために、パラレルとパラレルでないものを同じ形式で書いてあります。
 
ではn=8から、パラレルとパラレルでないもの両方で実行してみます。
 
> List.length (solve true 8);;
リアル: 00:00:00.103、CPU: 00:00:00.234、GC gen0: 17, gen1: 1, gen2: 0
val it : int = 92
> List.length (solve false 8);;
リアル: 00:00:00.257、CPU: 00:00:00.265、GC gen0: 17, gen1: 1, gen2: 0
val it : int = 92
 
> List.length (solve true 9);;
リアル: 00:00:00.573、CPU: 00:00:01.531、GC gen0: 96, gen1: 1, gen2: 1
val it : int = 352
> List.length (solve false 9);;
リアル: 00:00:01.407、CPU: 00:00:01.406、GC gen0: 95, gen1: 0, gen2: 0
val it : int = 352
 
> List.length (solve true 10);;
リアル: 00:00:02.929、CPU: 00:00:08.234、GC gen0: 537, gen1: 1, gen2: 0
val it : int = 724
> List.length (solve false 10);;
リアル: 00:00:07.939、CPU: 00:00:07.906、GC gen0: 535, gen1: 1, gen2: 0
val it : int = 724
 
> List.length (solve true 11);;
リアル: 00:00:19.686、CPU: 00:00:53.859、GC gen0: 3289, gen1: 3, gen2: 0
val it : int = 2680
> List.length (solve false 11);;
リアル: 00:00:49.092、CPU: 00:00:48.921、GC gen0: 3277, gen1: 6, gen2: 1
val it : int = 2680
 
immutableな値しか使っていないので、全体としての速度は早くありません。
また、パラレル版は非パラレル版に比べて約2から4倍速くなっています。
(ちなみにCPUはクワッドコアです。)
 
n = 12からはパラレル版のみで
 
> List.length (solve true 12);;
リアル: 00:02:17.579、CPU: 00:06:14.953、GC gen0: 21568, gen1: 16, gen2: 2
val it : int = 14200
 
> List.length (solve true 13);;
リアル: 00:17:12.789、CPU: 00:45:18.578、GC gen0: 147371, gen1: 1035, gen2: 10
val it : int = 73712
 
ということでn = 13が限界です。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。