Algorithm

幅優先探索(Breadth first search) で迷路を解いてみる

幅優先探索(Breadth first search)で迷路を解いてみました。 wikipedia に記述されている幅優先探索(Breadth first search)は以下の手順で探索します。 根ノードを空のキューに加える。 ノードをキューの先頭から取り出し、以下の処理を行う。 ノードが探索…

Ruby で迷路

「はてなブックマーク - 人生を書き換える者すらいた。: 人材獲得作戦・4 試験問題ほか」の「startから距離で塗りつぶして、あとはgoalから距離が減る方向に辿る(koizuka)」を参考に解いてみました。 maze_string = "**************************\n" + "*S* …

ダイクストラ法(最短経路問題)

Dijkstraのアルゴリズムの FigureSP03-01をRubyで書いてみました。 Infinity = 9999 class Node attr_reader :status, :node_distance, :temporary_distance, :decision_distance, :id, :parent, :nodes def initialize(id, distance, parent) @id = id @nod…

ヒープソートをやってみる。

常に子よりも親が大きい(小さい)値の二分木をヒープという。 今度はヒープを使ったソート、ヒープソートをやってみます。 def heap(array,n) if n > 0 parent = (n - 1) / 2 # 親の位置 if array[n] > array[parent] tmp = array[n] array[n] = array[pare…

常に子よりも親が大きい(小さい)値の二分木をヒープという。

常に子よりも親が大きい(小さい)値の二分木をヒープという。2分木を配列で表現すると各要素の位置関係は n の親は n - 1 / 2 n の左の子は 2 * n + 1 n の右の子は 2 * (n + 1) となる。 0 | +--+--+ 1 2 | | +-+-+ +-+-+ | | | | 3 4 5 6 [0,1,2,3,4,5,6]…