Elixirで幅優先探索を実装してみた

目次

1. 目的
2. バージョン
3. 前置き
4. コード
5. 所感
6. 参考文献

目的

Elixirの勉強と幅優先探索の知識を実装によって身につけることです。

バージョン

Elixir 1.8.2

前置き

幅優先探索は本やネットの記事から知識としてはありましたが実装したことはありませんでした。机上で探索していくのは簡単ですが実装すると手が止まってしまう場面が多々ありました。実装することによって以前よりも頭の引き出しから取り出す速度は格段に上がっています。 　

Elixirのバージョンと実装コードです。終了条件の１つはstageの値が"GOAL"であれば終了して経路を出力します。なければ"goal stage is nothing"と経路を出力して終了します。 　

コード

    defmodule BreadthFirstSearch do
      def initStage do
        stage = %{}
        stage = Map.put(stage, "Frecency", "")
        stage = Map.put(stage, "Contraband", "")
        stage = Map.put(stage, "Seaside","")
        stage = Map.put(stage, "Arsenal", "")
        stage = Map.put(stage, "Payload", "")
        stage = Map.put(stage, "Hacienda", "")
        stage = Map.put(stage, "Nuketown", "GOAL")

        stage
      end

      def initGraph do
        graph = %{}
        graph = Map.put(graph, "start", ["Frecency", "Contraband", "Seaside"])
        graph = Map.put(graph, "Frecency", ["Payload"])
        graph = Map.put(graph, "Contraband", ["Arsenal", "Payload"])
        graph = Map.put(graph, "Seaside", ["Hacienda"])
        graph = Map.put(graph, "Arsenal", [])
        graph = Map.put(graph, "Payload", [])
        graph = Map.put(graph, "Hacienda", ["Nuketown"])
        graph = Map.put(graph, "Nuketown", [])

        graph
      end

      def main do
        stage = initStage()
        graph = initGraph()
        checked = []

        searchAtQueue(graph["start"], stage, graph, checked)
      end

      def searchAtQueue([head | tail], stage, graph, checked) do
        if head in checked == true do
          searchAtQueue(tail, stage, graph, checked)
        else
          if stage[head] == "GOAL" do
            IO.puts(head)
            IO.puts('goal stage is ' ++ head)
          else
            IO.puts(head)
            IO.puts(" ↓ ")
            tail = tail ++ graph[head]
            checked = checked ++ [head]
            searchAtQueue(tail, stage, graph, checked)
          end
        end
      end

      def searchAtQueue([], _, _, _) do
        IO.puts("goal stage is nothing")
      end
    end

所感

今回の実装でElixirのパターンマッチとリスト、再帰処理について少しは学べたかと思います。ですがif文が冗長に使ってしまっている感があるので今後改善していきたいと思います。 　

参考文献

• なっとく！アルゴリズム
• プログラミングElixir