幅優先探索 | アルゴリズム[Ruby/Python][AOJ 0129]

『幅優先探索』をRuby/Pythonで解いてみました。AIZU Online Judgeで対応している問題は『Seven Puzzle』です。

🏀 概要

深さ優先探査の説明は『通勤・通学中に理解する深さ優先探索と幅優先探索』、
『アルゴリズム図鑑：iOS & Androidアプリ』が分かりやすかったです。

要点は次のとおり。

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

🐯 サンプル問題(AOJ)

Seven Puzzle

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

😀 Rubyコード

• 01234567がそろった状態(ゴール)からスタートして、0を移動させる
• 幅優先探索で過去に到達していない状態になったら、手数(移動数)を記録
• すでに到達済の状態であれば、スキップ(幅優先探索なら手数が同等かそれ以上となるため)

MOVE_LIST = [
    [1, 4],
    [0, 2, 5],
    [1, 3, 6],
    [2, 7],
    [0, 5],
    [1, 4, 6],
    [2, 5, 7],
    [3, 6]
]

goal = '01234567'
step_hash = { goal => 0 }
queue = [[goal, 0]]

def swap(str, a, b)
  tmp = str.dup
  tmp[a], tmp[b] = tmp[b], tmp[a]
  tmp
end

loop do
  figure, step_count = queue.shift
  break if figure.nil? || step_count.nil?

  current_idx = figure.index('0')
  MOVE_LIST[current_idx].each do |new_idx|
    new_figure = swap(figure, current_idx, new_idx)
    next if step_hash[new_figure]

    step_hash[new_figure] = step_count + 1
    queue << [new_figure, step_count + 1]
  end
end

loop do
  str = gets.to_s.split(' ').join('')
  break if str.length <= 0  puts step_hash[str]end
  puts step_hash[str]
end

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

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)  endendwhile s = gets  puts answers[s.chomp.split.join]end
    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コード

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

🎃 Javaコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
  private static String GOAL = "01234567";
  private static int[][] MOVE_LIST = {
      {1, 4},
      {0, 2, 5},
      {1, 3, 6},
      {2, 7},
      {0, 5},
      {1, 4, 6},
      {2, 5, 7},
      {3, 6}
  };

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    Map answers = breathFirstSearch();

    while (true) {
      String map = br.readLine();
      if (map == null) {
        break;
      }
      System.out.println(answers.get(removeSpace(map)));
    }
  }

  private static String removeSpace(String map) {
    String[] newMap = map.split(" ");
    return Arrays.asList(newMap).stream().collect(Collectors.joining());
  }

  private static Map breathFirstSearch() {
    Map answers = new HashMap<>();
    answers.put(GOAL, 0);

    Queue queues = new ArrayDeque<>();
    queues.add(GOAL);

    while (true) {
      if (queues.size() == 0) {
        break;
      }

      String search = queues.remove();

      int index = search.indexOf('0');
      for (int nextId : MOVE_LIST[index]) {
        String[] newMap = search.split("");
        newMap[index] = newMap[nextId];
        newMap[nextId] = "0";
        String nextMap = Arrays.stream(newMap).collect(Collectors.joining());
        if (answers.get(nextMap) == null) {
          int count = answers.get(search);
          answers.put(nextMap, count + 1);
          queues.add(nextMap);
        }
      }
    }

    return answers;
  }
}

👽 GitHubリポジトリ

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

morizyun/aoj-ruby-python - GitHub

🖥 VULTRおすすめ

「VULTR」はVPSサーバのサービスです。日本にリージョンがあり、最安は512MBで2.5ドル/月($0.004/時間)で借りることができます。4GBメモリでも月20ドルです。 最近はVULTRのヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります！

📚 おすすめの書籍