酒と泪と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

ハッカソンハウス遊びに来ませんか？

ハッカソンハウス
クリエーターが無料で、自由に開発に集中できるスペース「Hackathon House」を作りました。 『ハッカソンハウス - カレンダー』にOPENしている日時を書いていますので、是非遊びに来てください！ (場所はHPのお問い合わせからご連絡ください)

なぜ始めたのか？

僕はアメリカの有名なインキュベーション・オフィスを少しだけ訪問させて頂いたことがあります。あそこはプロダクトの可能性を目一杯引き出してくれる夢のような空間でした。僕はあんな場所を日本にも作りたいとずっと想い続けてきました。この企画を一緒にやっているくりしーさんは、『サウス・バイ・サウスウエスト』を通して、「あのワクワクする空間、熱気溢れるカオスな空間を日本でも創りたい。」というビジョンで一緒にやっています！

書籍や開発ガジェット拡充へのご協力をお願いします！

新しい技術を学ぶきっかけづくりのために、利用者から要望のあった3Dプリンターやリープモーション、書籍などを購入しています。Oculus VRも予約中っす。 この先もガジェットや書籍を取り揃えていきたいので、『Amazon ほしい物リスト』 へのご協力よろしくお願いします！

Campfireありがとうございました！

『Campfire』無事にサクセスしました。ご協力ありがとうございました！



押さえておきたい書籍

いかがだったでしょうか？
もし説明がわかりにくかったり、間違っている場所があればぜひ一言！

Comments