ズッキーニのプログラミング実験場

プログラミング + アカデミック + 何か面白いこと。 記載されているものは基本的に私が所属する団体とは関係がありません。

   Jun 15

[Algorithm]深さ優先探索 で迷路を解く

by zuqqhi2 at 2014年6月15日
Pocket

目的

深さ優先探索 で迷路を解く。
maze

迷路の表現方法

各地点の表現

maze-encode

迷路自体の表現(モデル化)

maze-tree

木とは

tree-model

深さ優先探索で迷路を解く

深さ優先探索というアルゴリズムで迷路を解くことが出来る。
深さ優先探索とは以下の流れで各nodeを処理する方法である。
maze-depthfast1

maze-depthfast2

maze-depthfast3

maze-depthfast4

maze-depthfast5

maze-depthfast6

maze-depthfast7

maze-depthfast8

maze-depthfast9

maze-depthfast10

maze-depthfast11

maze-depthfast12

maze-depthfast13

プログラム

ルートの表示方法

maze-route

コード

Go言語での実装

package main

import (
  "bufio"
  "fmt"
  "os"
)

type Point struct {
  X int
  Y int
}

type Content struct {
  Type string
  IsChecked bool
}

type Node struct {
  Parent *Node
  Pos Point
}

type Stack struct {
  Values []*Node
  Size int
}
func (s *Stack) Length() int {
  return s.Size
}
func (s *Stack) Push(n *Node) {
  s.Values[s.Size] = n
  s.Size += 1
}
func (s *Stack) Pop() *Node {
  if s.Size > 0 {
    s.Size -= 1
    return s.Values[s.Size]
  }
  return nil
}

func IsWay(maze [][]Content, x int, y int) bool {
  if x >= 0 && x <= 11 && y >= 0 && y <= 11 && maze[y][x].Type != "WALL" && maze[y][x].IsChecked == false {
    return true
  } else {
    return false
  }
}

var endNode *Node
func SolveMaze(maze [][]Content, start Node) {
  stack := Stack{make([]*Node, 1000), 0}
  stack.Push(&start)

  cur := &start
  for ; maze[cur.Pos.Y][cur.Pos.X].Type != "END"; cur=stack.Pop() {
    fmt.Printf("(%v,%v) Stack Size : %v\n", cur.Pos.X, cur.Pos.Y, stack.Length())
    maze[cur.Pos.Y][cur.Pos.X].IsChecked = true
    if IsWay(maze, cur.Pos.X, cur.Pos.Y-1) {
      child := Node{cur, Point{cur.Pos.X, cur.Pos.Y-1}}
      stack.Push(&child)
    }
    if IsWay(maze, cur.Pos.X, cur.Pos.Y+1) {
      child := Node{cur, Point{cur.Pos.X, cur.Pos.Y+1}}
      stack.Push(&child)
    }
    if IsWay(maze, cur.Pos.X-1, cur.Pos.Y) {
      child := Node{cur, Point{cur.Pos.X-1, cur.Pos.Y}}
      stack.Push(&child)
    }
    if IsWay(maze, cur.Pos.X+1, cur.Pos.Y) {
      child := Node{cur, Point{cur.Pos.X+1, cur.Pos.Y}}
      stack.Push(&child)
    }
  }

  endNode = cur
}


func main() {
  MAX_X := 11
  MAX_Y := 11

  // File open
  var fp *os.File
  fp, err := os.Open("maze.txt")
  if err != nil {
    panic(err)
  }
  defer fp.Close()

  // Convert maze string to array of point
  var startX, startY int
  maze := make([][]Content, MAX_Y+1)
  for y:= 0; y <= MAX_Y; y++ {
    maze[y] = make([]Content, MAX_X+1)
  }
  counter := 0
  y := -1
  scanner := bufio.NewScanner(fp)
  for scanner.Scan() {
    y += 1
    x := -1
    for _, char := range scanner.Text() {
      x += 1
      switch char {
        case 'S':
          maze[y][x] = Content{"START", false}
          startX = x
          startY = y
        case 'G':
          maze[y][x] = Content{"END", false}
        case '.':
          maze[y][x] = Content{"WAY", false}
        case '#':
          maze[y][x] = Content{"WALL", false}
      }
      counter += 1
    }
  }
  if err := scanner.Err(); err != nil {
    panic(err)
  }
  fmt.Println(maze)

  // Convert maze to binary tree
  start := Node{nil, Point{startX, startY}}
  SolveMaze(maze, start)
  fmt.Println(endNode)

  // Print Route
  cur := endNode
  for ; cur.Parent != nil; cur = cur.Parent {
    fmt.Println(cur.Pos)
  }
  fmt.Println(cur.Pos)
}

実行結果

{9 11}  # End
{9 10}
{8 10}
{7 10}
{6 10}
{6 9}
{6 8}
{7 8}
{8 8}
{9 8}
{9 7}
{9 6}
{8 6}
{7 6}
{6 6}
{6 5}
{6 4}
{6 3}
{6 2}
{5 2}
{4 2}
{3 2}
{2 2}
{2 1}
{2 0}  # Start

Related Posts

  • 2014年6月22日 [Algorithm]貪欲法 目的 以下の問題を貪欲法で解く. できるだけ少ない枚数で指定された金額を支払う場合,何枚になるか. 貪欲法 その時々で最善と思われる行動を取る方法のこと. 利点は単純で計算速度が速く,最善の定義を問題に対して適切に設定するとそれなりに良い解が得られる. […]
  • 2015年3月25日 Coqによる 証明駆動開発 超入門 証明駆動開発 とは 証明駆動開発 とは証明によってプログラムが期待通りの性質を有しているかを確かめながら開発する手法のこと。 ユニットテストの一部で使用可能な方法。 証明駆動開発 […]
  • <!--:ja-->[Go]フィボナッチ数列を出力させてみる<!--:--><!--:en-->[Go]Output Fibonacci Series<!--:-->2013年6月29日 [Go]フィボナッチ数列を出力させてみる Go言語でフィボナッチ数列を出力させてみる。 実行。 Output Fibonaaci Series with Go. Run.
  • <!--:ja-->[Plotinum][Go]Go言語でグラフを書いてみる<!--:--><!--:en-->[Plotinum][Go]Draw chart with Go lang<!--:-->2014年6月29日 [Plotinum][Go]Go言語でグラフを書いてみる 概要 Plotinumというライブラリを使うことでGo言語でグラフを描画することが出来るらしい。 このライブラリを使ってグラフを描いて保存するプログラムを書いてみる。 インストール 以下のコマンドを叩くだけ。非常に簡単。 サンプルプログラム ここに公式の […]
  • 2014年7月6日 [Go][LeastSquareMethod]最小二乗法 でデータを多項式で当てはめる 前提知識 偏微分 行列の基本変形 最小二乗法 20140706 zuqqhi2-lsm-v1 from Hidetomo Suzuki プログラム 実行結果 今回の場合、結果を見る限りn=10(go […]
  • <!--:ja-->[Go]ubuntuにインストールする<!--:--><!--:en-->[Go]Install Go language on ubuntu<!--:-->2013年6月28日 [Go]ubuntuにインストールする Go インストール インストール aptで普通にインストールできる。 テストプログラム ワークスペース作成 ワークスペースを作成・設定してプログラム作成を行うのが管理しやすい。 そのためまずは、ワークスペースを作成する。 これは簡単に […]
Pocket

You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.