【アルゴリズム】rubyによる深さ優先検索

Question

##環境

• Ruby2.0
• Mac OS X El Captain ver:10.11.4

##前提・実現したいこと
深さ優先検索アルゴリズムを用いて、Rubyで問に対する解答を出したい。競技プログラミングの問題を一部修正しています。
##問
H×Wのマス目があり、各マス(aij)に整数値が書かれている。始めにあるマスにいて、そのマスの上下左右に隣接しているマスのうち、今いるマス目より大きな整数が書かれたマスに移動できる。
ありうる経路の数を10E9+7(=1000000007:素数)で割った余りを求めよ。
###制約

• 1≦h,w≦1000
• 1≦aij≦10E9

###入力

h w # グリッドの大きさ
a11 .. a1W # aijはマス目の数字
:
aH1 .. aHW

##発生している問題
グリッドが大きくなると、時間内に解けない。（どのオーダーでタイムリミットなるか把握できていませんが。。）
##該当のソースコード

MOD=100_000_007
ans=0
# 高さ、幅の読み取り
h,w=gets.chomp.split.map(&:to_i)
# マス目を格納する2次元配列及び、経路数を格納する2次元配列を用意
@grid=Array.new(h+2).map{Array.new(w+2,0)}
@comb=Array.new(h+2).map{Array.new(w+2,0)}
# マス目のよみとり
(1..h).each do |i|
	@grid[i]=gets.chomp.split.map(&:to_i).unshift(0).push(0)
end

def dfs(i,j)
	# 動かない場合もあるのでres=1
	res=1
	# 既に探索した木ならその値を返す
	return @comb[i][j] if @comb[i][j]>0
	# 上下左右のほうが大きければ移動する
	res+=dfs(i,j-1) if @grid[i][j]<@grid[i][j-1]
	res+=dfs(i,j+1) if @grid[i][j]<@grid[i][j+1]
	res+=dfs(i-1,j) if @grid[i][j]<@grid[i-1][j]
	res+=dfs(i+1,j) if @grid[i][j]<@grid[i+1][j]

	# 移動経路数を2次元配列に格納し、値を返す
	@comb[i][j]=res%MOD
	return @comb[i][j]
end

(1..h).each do |i|
	(1..w).each do |j|
		ans+=dfs(i,j)
		# MODより大きければ引く
		if ans>MOD
			ans-=MOD
		end
	end
end
puts ans

どこを修正すると速くなるのか教えていただきたいです。
よろしくお願い致します。。

Answer 1

AtCorder ABC 037 D問題であってますでしょうか？

http://abc037.contest.atcoder.jp/submissions/750568
頑張ってTLEを残り2個まで減らしました。あとは、よろしくお願いします(えっ)。REの1個は再帰呼び出しが深すぎてスタックオーバーフローだと思われますので、これを解消するにはyubaさんが言うような方法にするなど、戦略から書き変えないと無理です。(末尾再帰にしてスタックを使わない最適化に変える事もできないことは無いかも知れませんが、Rubyで末尾再帰最適化はちょっとめんどくさい)

工夫した点は主にArray#[]を極力なくすことです。まず、二次元配列ではなく一次元配列にします。Fixnumの四則演算に比べると配列へのアクセスは遅いのでそれだけで20〜30%は短くなるようです。あとは、計算結果を随時変数に入れるとか、なるべく計算しないように頑張ります。

Rubyで高速を目指すなら、profileの使い方を覚えると良いでしょう。ネックになっているところがだいたいつかめるようになります。私も競プロをRubyでといて遊んだりしますが、まぁ、時間がシビアな問題はだいたい解けません。しかし、それを乗り越える楽しさ…があるような気もしないではないと思ってます。

C++で解いた方が速いと言っても、高速すぎて単純な総当たりでも解けちゃうことがあったりすると興ざめですものね。

---

おまけ
AtCoderは問題が表示されないので、簡易な問題作成ツールを作りました。良かったら検証に使ってください。

h = 1000
w = 1000
puts [h, w].join(' ')
h.times do
  puts w.times.each.map{rand(10**9) + 1}.join(' ')
end

Comments

[NaoTsukamoto]

コメントありがとうございます。
当問題で間違いありません。TLE残り2つ、、素晴らしいです。。
確かに、2次元配列⇒1次元配列は早くなりそうです。ありがとうございます。末尾再帰最適化はいまのところお手上げです。
profile使って検証してみたいと思います。

Atcoderの話に戻りますが、Rubyで大規模データを使ったD問題に対するACがないので、やはり厳しいのかなと。。ただ、なんとか、、！と思い、やるのもある意味楽しいです。仰っている意味は僅かながら理解できる気がします。。

ありがとうございました。

Answer 2

質問された内容と違いますが・・・

コンパイルが必要な言語使ったほうが、コンパイル時に最適化してもらえるからよいです。

特にデータのサイズが大きくなって計算量が大きくなった時にLL言語は、よほどチューニングしても正当できないことがあるようです。

同じ解法をつかって、書いた言語の問題でパスしないのはもったいないです。

Comments

[NaoTsukamoto]

コメントありがとうございます。
仰るとおりで、コンパイル型の言語では同じ解法でもパスしますので確実だと私も感じています。
なんとかLLであるRubyで実行してみたんですけどこのとおりです。

[iwamoto_takaaki]

競技プログラミング初心者の方かと勘違いしました。大変失礼しました。
ruby縛り面白そうなので、挑戦してみます。うまく行ったら報告します。

Answer 3

その問題、たぶん探索で解くべきではありません。線形計画法を用いるべきです。
表に、「ここからの経路はn通り」というデータをわかるところから埋めていき、最終的にスタート地点にその数字を埋めることができたら完了とします。

1. 問題の表と同じ大きさの表を作り、すべてに「経路数=0」を入れておきます。
2. すべての座標を、整数値の降順にソートします。
3. ソートしたキューから一つずつ座標を取り出して次のことを行います。

●周囲の4点のうち、自分より整数値の大きい座標の経路数の合計を自分の経路数とします。
●いま埋めた座標がスタート地点であるならループを抜けます。

Comments

[NaoTsukamoto]

コメントありがとうございます。線形計画法を用いて書きましたが、同じくタイムオーバーになります。。。

[yuba]

ぐっ残念

[HogeAnimalLover]

私もこのやり方の方がスマートだとは思います。もちろん、データの偏りにも依るので、かなり偏っているのですかねえ・・・

[yuba]

お気付きの方おられると思いますが、この通りのアルゴリズムだと0しか出てきませんね。
記述が足りていなくて、「四方がすべて自分より小さければ、経路数は1とする」が必要でした。

[yuba]

あと、「線形計画法」ではなくて「動的計画法」でした。線形計画法は高校の数学で軽くやった経営最適化のやつです。