幅優先探索 | アルゴリズム[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

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

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コード

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のヘビーユーザーになので、「ここ」から会員登録してもらえるとサービス開発が捗ります!

📚 おすすめの書籍