アルゴリズム | A*探索（A-Star探索）

概要

A*探索（A-Star探索）

内容

ゴールが分かっている場合にゴールまでの推定値を利用して最短経路を解く。
推定距離は実際の値と同じかそれより小さい必要がある。
典型的な例としてはゴールまで何も障害物が無いと想定して、直線距離を推定値にする。

アルゴリズム

・スタートとゴールを決める
・計算中リストと訪問済みリストを作成する
・スタート地点から訪問可能なノードを計算中リストに追加、訪問済みリストは空で初期化
・計算中リストが空なら処理終了。
・計算中リストから訪問可能なリストの内、推定値が最小の値を取得
・最小の値を持つ地点がゴールなら終了
・ゴール以外の場合は、訪問済みリストに移動先の値を挿入。また移動先候補に対して以下を行う
・移動先候補への期待値を計算する

f(m) = g*(n) + h*(m) + COST(n,m) 。
n=次の移動箇所
m=次の移動箇所からの移動先候補
g*(n)＝スタートからnまでの最小コスト
h*(m)＝mからゴールまでの最小コスト
コストは移動コストだが今回のサンプルはすべて同一距離とするためこの部分は無視する。

・移動先候補が計算中リスト、訪問可能なリストのどちらにも存在しないなら計算中リストに追加する
・移動先候補が計算中リストにある場合、格納済みのf (m) と新たに計算したf(m)を比較してf(m)の方が小さければ置き換える。親もnに変更する。
・移動先候補が訪問済みリストにある場合、格納済みのf (m) と新たに計算したf(m)を比較してf(m)の方が小さければ置き換える。親もnに変更する。
・次への移動を繰り返す
・ゴールまで到達したら最後の訪問済みリストからParentをたどると経路が分かる

ソースコード

# encoding: utf-8
require "pp"

class Point
  attr_accessor :x, :y, :parent, :expected, :total_expected
  def initialize(x, y, parent = nil, expected = nil, total_expected = nil)
    @x, @y, @parent, @expected, @total_expected = x, y, parent, expected, total_expected
  end

  def distance(point)
    x_diff = x - point.x
    y_diff = y - point.y
    x_diff.abs + y_diff.abs
  end

  def is_same_position?(x, y)
    return true if @x == x && @y == y
    false
  end
end

class Maze
  attr_accessor :nexts, :closed_list, :current
  START = Point.new(1, 5, "start")
  GOAL = Point.new(2, 0, "goal")

  MAP = [
    ['■','■', 'Ｇ', '□', '□'],
    ['□','□', '■', '■', '□'],
    ['□','□', '■', '□', '□'],
    ['□','■', '■', '■', '□'],
    ['□','□', '□', '□', '□'],
    ['■','Ｓ', '■', '□', '□']
  ]

  def initialize
    @nexts, @closed_list = [], []
  end

  def solve
    print_map
    @current = START
    @closed_list << START

    cnt = 0
    loop do
      print_map(@current)
      set_next_points @current
      @current = get_next
      cnt += 1
      break if GOAL.is_same_position? @current.x, @current.y
    end
    print_map(@current)
    puts "GOAL"
  end

  private
  def print_map(current = nil)
    copy = MAP.clone
    copy.each_with_index do |line, y|
      line.each_with_index do |column, x|
        if (!current.nil?) && current.is_same_position?(x, y)
          print "◎"
        else
          print column
        end
      end
      puts
    end
    puts
  end

  def set_next_points(point)
    left, right, up, down = nil

    up = Point.new(point.x, point.y - 1, point) unless point.y == 0
    down = Point.new(point.x, point.y + 1, point) unless point.y == MAP.size - 1
    left = Point.new(point.x - 1, point.y, point) unless point.x == 0
    right = Point.new(point.x + 1, point.y, point) unless point.x == MAP[point.x].size - 1

    append_if_movable(MAP, left)
    append_if_movable(MAP, right)
    append_if_movable(MAP, up)
    append_if_movable(MAP, down)
  end

  def append_if_movable(map, point)
    return if point == nil
    return unless (map[point.y][point.x] == "□") || (map[point.y][point.x] == "Ｇ")

    point.expected = START.distance point.parent
    point.total_expected = GOAL.distance point

    n = include_point?(@nexts, point)
    if n
      if n.expected > point.expected
        @nexts.delete n
        @nexts << point
      end
    else
      @nexts << point
    end

    c = include_point?(@closed_list, point)
    if c
      if c.expected > point.expected
        @closed_list.delete n
        @closed_list << point
      end
    end
  end

  def include_point?(points, point)
    points.each do |po|
      return po if po.is_same_position?(point.x, point.y)
    end
    nil
  end

  def get_next
    min = nil
    targets = @nexts.select{|n|!n.is_same_position?(@current.x, @current.y)}
    targets = targets.select{|n|n.parent == @current}

    targets.each do |n|
      next if include_point?(@closed_list, n)
      if min.nil?
        min = n
        next
      end
      min = n if n.total_expected < min.total_expected
    end
    min = @current.parent if min.nil?
    @closed_list << min
    min
  end
end

Maze.new.solve

実行結果

□＝＞通路
■＝＞壁
◎＝＞現在地

■■Ｇ□□
□□■■□
□□■□□
□■■■□
□□□□□
■Ｓ■□□

■■Ｇ□□
□□■■□
□□■□□
□■■■□
□□□□□
■◎■□□

■■Ｇ□□
□□■■□
□□■□□
□■■■□
□◎□□□
■Ｓ■□□

■■Ｇ□□
□□■■□
□□■□□
□■■■□
□□◎□□
■Ｓ■□□

■■Ｇ□□
□□■■□
□□■□□
□■■■□
□□□◎□
■Ｓ■□□

■■Ｇ□□
□□■■□
□□■□□
□■■■□
□□□□◎
■Ｓ■□□

■■Ｇ□□
□□■■□
□□■□□
□■■■◎
□□□□□
■Ｓ■□□

■■Ｇ□□
□□■■□
□□■□◎
□■■■□
□□□□□
■Ｓ■□□

■■Ｇ□□
□□■■□
□□■◎□
□■■■□
□□□□□
■Ｓ■□□

■■Ｇ□□
□□■■□
□□■□◎
□■■■□
□□□□□
■Ｓ■□□

■■Ｇ□□
□□■■◎
□□■□□
□■■■□
□□□□□
■Ｓ■□□

■■Ｇ□◎
□□■■□
□□■□□
□■■■□
□□□□□
■Ｓ■□□

■■Ｇ◎□
□□■■□
□□■□□
□■■■□
□□□□□
■Ｓ■□□

■■◎□□
□□■■□
□□■□□
□■■■□
□□□□□
■Ｓ■□□

GOAL