Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

[C69]

キューでフィールドを管理したところMLEになってしまうので別のやり方があるのでしょうか
すべて探索では到底間に合わないので逆向きに考えてみましたが枝刈りできる状態が思いつきません

よろしければソースを見せてもらえないでしょうか
  • 2010-12-27 14:43
  • roxion
  • URL
  • 編集

[C70]

幅優先ではなくて,深さ優先で探索するとメモリは必要なくて,枝刈りも何もなしでいけると思います.
(AOJだと怪しいかもしれないけど,JOIの想定解法はそれです)

自分のは試行錯誤のため,ちょっとメモ化使って枝刈りしてるソースになります.
http://ideone.com/30vgT
  • 2010-12-27 18:22
  • rsujskf
  • URL
  • 編集

[C71]

お忙しい中ありがとうございます
深さ優先探索だったのですね・・・
よく考えてみればありえない状態が多めなので少し時間をかければうまくいきますね

ありがとうございました
  • 2010-12-27 19:52
  • roxion
  • URL
  • 編集

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1463-9e640ed4
この記事にトラックバックする(FC2ブログユーザー)

Aizu 0548 - Reindeer with no sense of direction (方向音痴のトナカイ) (この記事を編集する[管理者用])

Source

第9回日本情報オリンピック 予選1 (2009年12月13日)
Aizu 0548

問題概要

日本語の問題文があるので簡単に書く.
10*10以下のマップの中に,1個の教会と23個以下の家がある.
教会からスタートして,全ての家を訪れて,教会に戻ってくるパターンの数を求める問題.
ただし,移動するときには,上下左右のどこかに向かって直線に移動することしか出来ない.
一度訪れた家の上は通ることが出来ない.
答えは2000000以下であることが保証されている.

解法

逆向きに考えると,最初に出会った家で曲がらないと駄目で,一度たどり着いた家を消していく感じになる.
逆向きに考えたほうが枝分かれが少なく探索が早く終る.

コメント

[C69]

キューでフィールドを管理したところMLEになってしまうので別のやり方があるのでしょうか
すべて探索では到底間に合わないので逆向きに考えてみましたが枝刈りできる状態が思いつきません

よろしければソースを見せてもらえないでしょうか
  • 2010-12-27 14:43
  • roxion
  • URL
  • 編集

[C70]

幅優先ではなくて,深さ優先で探索するとメモリは必要なくて,枝刈りも何もなしでいけると思います.
(AOJだと怪しいかもしれないけど,JOIの想定解法はそれです)

自分のは試行錯誤のため,ちょっとメモ化使って枝刈りしてるソースになります.
http://ideone.com/30vgT
  • 2010-12-27 18:22
  • rsujskf
  • URL
  • 編集

[C71]

お忙しい中ありがとうございます
深さ優先探索だったのですね・・・
よく考えてみればありえない状態が多めなので少し時間をかければうまくいきますね

ありがとうございました
  • 2010-12-27 19:52
  • roxion
  • URL
  • 編集

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1463-9e640ed4
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。