data.priority-mapを使ってダイクストラ法で迷路を解く

(このエントリは Clojure Contrib Library Advent Calendar 14日目の記事です。)

はじめに

今回はdata.priority-mapについてです。以前はclojure.contrib.priority-mapと呼ばれていました。
data.priority-mapは優先度つきマップ(priority map)の実装を提供します。優先度つきマップは,Clojureコアが提供するソートされたマップ(sorted map)と非常に類似したデータ構造です。両者の違いは,ソートされたマップがキーによってソートされるのに対し,優先度つきマップは値によってソートされるという点です。

今回は,data.priority-mapの基本的な使い方と,優先度つきマップの応用例としてダイクストラ法を使って迷路を解く例を見ます。

インストール

data.priority-mapを使う際は,Leiningenを使ってる場合,project.cljの:dependenciesに

[org.clojure/data.priority-map "0.0.4"]

を追加します。2013年12月現在の最新版は0.0.4です。

使い方

優先度つきマップを作るにはclojure.data.priority-map/priority-mapという関数を使います。この関数はClojureコアのarray-mapやsorted-mapと同じように使うことができます。

user=> (require '[clojure.data.priority-map :as p])
nil
user=> (def xs (p/priority-map :a 3 :b 1 :c 4 :d 1 :e 5))
#'user/xs
user=> xs
{:b 1, :d 1, :a 3, :c 4, :e 5}
user=>

Clojureコアが提供するその他のマップと同じように,優先度つきマップへのエントリの追加やキーに対応する値を引くことができます。

user=> (assoc xs :f 0)
{:f 0, :b 1, :d 1, :a 3, :c 4, :e 5}
user=> (conj xs [:f 0])
{:f 0, :b 1, :d 1, :a 3, :c 4, :e 5}
user=> (xs :c)
4
user=> (:c xs)
4
user=> 

優先度の一番高い値をもつエントリを取得するにはpeekを使います。また,優先度の一番高い値をもつエントリを除くにはpopを使います。

user=> (peek xs)
[:b 1]
user=> (pop xs)
{:d 1, :a 3, :c 4, :e 5}
user=>

比較関数を指定して優先度つきマップを作るには,clojure.data.priority-map/priority-map-byを使います。

user=> (def ys (p/priority-map-by > :a 3 :b 1 :c 4 :d 1 :e 5))
#'user/ys
user=> ys
{:e 5, :c 4, :a 3, :b 1, :d 1}
user=> (peek ys)
[:e 5]
user=> 

マップに持たせる値から優先度を計算する方法をカスタマイズしたい場合は,clojure.data.priority-map/priority-map-keyfnが使えます。以下の例では,2つ組を表すベクタを値としてマップに持たせ,各ベクタの2つめの要素を優先度として扱っています。

user=> (def zs (p/priority-map-keyfn second :a ["a" 2] :b ["b" 7] :c ["c" 1] :d ["d" 8] :e ["e" 2]))
#'user/zs
user=> zs
{:c ["c" 1], :a ["a" 2], :e ["e" 2], :b ["b" 7], :d ["d" 8]}
user=> (peek zs)
[:c ["c" 1]]
user=> 

data.priority-mapの使い方が分かったところで,優先度つきマップを使った応用例として,ダイクストラ法を使った迷路の解法を見てみましょう。
お題となる迷路は,以前にこのブログでも話題として出した以下のブログ記事からとってきました。

以下のサンプルプログラムでは,ダイクストラ法による解法と合わせて,以前に書いた単純な幅優先探索による解法(を一部書き直したもの)も比較のために示しています。

(ns contrib-calendar.data.priority-map
  (:require [clojure.data.priority-map :as p]
            [clojure.java.io :refer [reader]])
  (:import clojure.lang.PersistentQueue))

(defn value-at
  ([maze [y x]] (value-at maze y x))
  ([maze y x] ((maze y) x)))

(defn nrows [maze]
  (count maze))

(defn ncols [maze]
  (count (maze 0)))

(defn neighbors [maze [y x]]
  (for [[dy dx] [[0 1] [1 0] [0 -1] [-1 0]]
        :let [y (+ y dy), x (+ x dx)]
        :when (not= \* (value-at maze y x))]
    [y x]))

; 幅優先探索による解法
(defn breadth-first-search
  ([maze start] (breadth-first-search maze (conj PersistentQueue/EMPTY [start [start]]) #{}))
  ([maze candidates visited]
   (let [[pos path] (peek candidates)]
     (cond (nil? pos) nil
           (= (value-at maze pos) \G) path
           :else
           (recur maze
                  (into (pop candidates)
                        (for [neighbor (neighbors maze pos)
                              :when (not (visited neighbor))]
                          [neighbor (conj path neighbor)]))
                  (conj visited pos))))))

; ダイクストラ法による解法
(defn dijkstra-algorithm
  ([maze start] (dijkstra-algorithm maze (p/priority-map-keyfn count start [start]) #{}))
  ([maze candidates visited]
   (let [[pos path] (peek candidates)]
     (cond (nil? pos) nil
           (= (value-at maze pos) \G) path
           :else
           (recur maze
                  (merge-with #(if (> (count %1) (count %2)) %2 %1)
                              (pop candidates)
                              (->> (for [neighbor (neighbors maze pos)
                                         :when (not (visited neighbor))]
                                     [neighbor (conj path neighbor)])
                                   (into {})))
                  (conj visited pos))))))

(defn search-start [maze]
  (first (for [y (range (nrows maze)), x (range (ncols maze))
               :when (= \S (value-at maze y x))]
           [y x])))

(defn print-solution [maze path]
  (let [ncols (ncols maze), path? (apply hash-set path)]
    (doseq [y (range (nrows maze)), x (range ncols)
            :let [v (value-at maze y x)]]
      (if (and (path? [y x]) (not (#{\S \G} v)))
        (print \$)
        (print v))
      (when (= x (dec ncols)) (newline)))))

(defn -main [& args]
  (with-open [r (reader (first args))]
    (let [maze (vec (map vec (line-seq r)))
          start (search-start maze)
          bench (fn [strategy]
                  (let [solution (time (strategy maze start))]
                    (print-solution maze solution)))]
      (print "breadth first search: ")
      (bench breadth-first-search)
      (newline)
      (print "dijkstra algorithm: ")
      (bench dijkstra-algorithm)
      (newline))))

以下が実行例です。

$ cat maze.txt
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
$ lein run -m contrib-calendar.data.priority-map maze.txt
breadth first search: "Elapsed time: 902.255 msecs"
**************************
*S* * $$$$               *
*$* *$$* $*************  *
*$* $$*  $$************  *
*$$$$*    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$* $$$$$$$$$$$$$G  *
*  *  $$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************

dijkstra algorithm: "Elapsed time: 38.862 msecs"
**************************
*S* * $$$                *
*$* *$$*$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

$

ダイクストラ法を使った場合の方が単純な幅優先探索よりも効率的に最短経路を探索できているのが分かります。よく見ると,得られる解が両者でところどころ違っているのもおもしろいですね。

おわりに

今回は,data.priority-mapが提供する優先度つきマップの使い方と,その応用例としてダイクストラ法で迷路を解く例を見ました。