酒と泪とRubyとRailsと

Ruby on Rails と Objective-C は酒の肴です!

アルゴリズムの勉強: 幅優先探索[Ruby/Python][AOJ 129]

プログラミングの基礎固めと、Pythonの勉強を兼ねてアルゴリズムを勉強中です。今回は『幅優先探索』を勉強しました。AIZU Online Judgeで対応している問題は、『Seven Puzzle』です。基礎的なアルゴリズムのはずですが、ちゃんと組み込むのにかなり苦労しました。また複数言語を勉強しているおかげで、より効率的な組み方をいろんな言語で考えられるのは楽しいですね^^


概要

深さ優先探査の説明は『通勤・通学中に理解する深さ優先探索と幅優先探索』がわかりやすいです。

要点は次の通り。

根ノードで始まり隣接した全てのノードを探索。階層(根ノードからの距離が近い順)にルートを調べる

サンプル問題(AOJ)

Seven Puzzle
Aizu Online Judge。1-7までの数字と、1つ空白のあるパズルをとく問題。

Rubyのサンプルソース

ループで幅優先探査をして全パターンを求める場合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def swap(str, a, b)
  tmp = str.dup
  tmp[a], tmp[b] = tmp[b], tmp[a]
  return tmp
end

def breadth_first_search(answers, queue, move_list)
  loop do
    move_num, search = queue.shift
    break unless search

    a = search.index('0')
    move_list[a].each do |b|
      next_str = swap(search, a, b)
      next if answers[next_str]
      answers[next_str] = move_num + 1
      queue.push([move_num + 1, next_str])
    end
  end
  return answers
end

move_list = [[1, 4], [0, 2, 5], [1, 3, 6], [2, 7], [0, 5], [1, 4, 6], [2, 5, 7], [3, 6]].freeze
goal = '01234567'
answers = {goal => 0}
queue = [[0, goal]]
answers = breadth_first_search(answers, queue, move_list)

while gets
  s = $_.chomp.gsub(' ', '')
  puts answers[s]
end

もう一つ、無名関数と構造体を使って幅優先探索を行う問題。手当たり次第調べるような単純なアルゴリズムの場合は、再帰を使うとネストしすぎてハマりました。再帰をもう少し効果的に使えるようになりたい!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def to_xy(str, target)
  str.chars.each_with_index do |s, i|
    if target == s.to_i
      x = i%4
      y = i < 4 ? 0 : 1
      return x, y, i
    end
  end
end

def move_zero(str, mx, my)
  zx, zy, zi = to_xy(str, 0)
  (1..7).each do |i|
    sx, sy, si = to_xy(str, i)
    if (zx + mx) == sx and (zy + my) == sy
      ns = str.dup
      ns[zi], ns[si] = ns[si], ns[zi]
      return ns
    end
  end
end

rule = Struct.new('Rule', :can_move?, :move)
rules = [
    rule.new(lambda { |str| x, _, _ = to_xy(str, 0); x <= 2 }, lambda { |str| move_zero(str,  1,  0) }),
    rule.new(lambda { |str| _, y, _ = to_xy(str, 0); y == 0 }, lambda { |str| move_zero(str,  0,  1) }),
    rule.new(lambda { |str| x, _, _ = to_xy(str, 0); x >= 1 }, lambda { |str| move_zero(str, -1,  0) }),
    rule.new(lambda { |str| _, y, _ = to_xy(str, 0); y == 1 }, lambda { |str| move_zero(str,  0, -1) })
]

goal = '01234567'
map_list = [goal]
answers = {goal => 0}
loop do
  search_map = map_list.shift
  break unless search_map
  rules.each do |rule|
    next unless rule.can_move?.call(search_map)
    next_map = rule.move.call(search_map)
    next if answers[next_map]
    answers[next_map.to_s] = answers[search_map] + 1
    map_list.push(next_map)
  end
end

while s = gets
  puts answers[s.chomp.split.join]
end

Pythonのサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
MOVE = [[1, 4], [0, 2, 5], [1, 3, 6], [2, 7], [0, 5], [1, 4, 6], [2, 5, 7], [3, 6]]
answers = {"01234567": 0}

def swap(field, a, b):
  tmp = list(field)
  tmp[a], tmp[b] = tmp[b], tmp[a]
  return "".join(tmp)

def breadth_first_search(answers):
  q = [[0, "01234567"]]

  while len(q) != 0:
    g, field = q.pop(0)
    a = field.find("0")

    for b in MOVE[a]:
      tmp = swap(field, a, b)

      if not tmp in answers:
        answers[tmp] = g+1
        q.append([g+1, tmp])

  return answers

answers = breadth_first_search(answers)

while True:
  try:
    print answers[raw_input().replace(" ", "")]
  except:
    break

Aizu Online Judgeのサンプルソース

当面はAOJを解きながら、アルゴリズムの再勉強をしていくつもりです。Ruby/PythonでのAOJの回答は下のリポジトリに保存しておきます。もしツッコミとかあれば是非^^

morizyun/aoj-ruby-python - GitHub

最近解いたAOJの問題

AOJタグのついた最近解いた問題一覧

おすすめの書籍