Q&A
学校の課題か何かでしょうか。課題代行や宿題代行のサイトではないので、質問の表現には気をつけていただけたらと。 https://teratail.com/help/question-tips#questionTips1-1 >作業依頼のような投稿をして、課題や仕事を無償でやってもらえる場ではありません。
前提・実現したいこと
(Javascript)将棋のコマとして「銅」というコマを新しく考える．このコマは斜め左上，下，右のいずれかに一マス移動することができる．今，大きさn x n の将棋盤の適当な位置から銅がスタートして，この将棋盤のすべてのマスをちょうど一回だけ訪れる回り方を求めることにする．銅はスタートした位置に戻ってくる必要はない．
このような条件を満たすときマスの番号を順に入れた配列の配列を返すような関数 bronze(n) を定義せよ．
マスの番号は0からn＾2 - 1とし，左上から順に横方向にスキャンしながら番号付けし，右下で終わるようにせよ．
javascript
1function bronze(n) 2{ 3 4 var LEFTUP = 0 5 var RIGHT = 1 6 var DOWN = 2 7 8 function make_masu(n) 9 { 10 var state = [] 11 var i 12 for(i = 0;i < n * n;i++) state[i] = 0 13 14 return state 15 } 16 17 function move(state,now,move) 18 { 19 var now_x = now % n 20 var now_y = Math.floor(now / n) 21 22 if (move == DOWN && now_y > n - 1){ 23 state[now + n] = 1 24 now = now + n 25 } else if (move == LEFTUP && 0 < now_y && 0 < now_x){ 26 state[now - n - 1] = 1 27 now = now - n - 1 28 } else if (move == RIGHT && now_x < n - 1){ 29 state[now + 1] = 1 30 now = now + 1 31 } 32 return state 33 } 34 function next_move(state,now) 35 { 36 37 } 38 function search(start) 39 { 40 41 } 42}
マスの状態をstateで与えてstateが1の場所は一度訪れたことがある場所という感じで考えているのですが,探索の仕方のアイデアが思いつかないです。
回答4件
0
ベストアンサー
探索の仕方（アルゴリズム）を考えるところから課題でしょうから、アルゴリズムの見つけ方について考えてみましょう。
端的な回答
- 1x1の場合、2x2の場合、3x3の場合について自分で総当たりで答えを作ってみる。
- その際に自分が考えたことをプログラムに落とし込み、総当たりでたどり着いた答えと同じ答えをを返すプログラム作ってみる。（簡単な1x1の場合から順にプログラムの処理を足していく）
- そのプログラムが確実に総当たり出来ているか確認する
と、答えにたどり着けます。
以下、考え方的なもの
まず、この問題が何を求めているかを正確に定義するところから始めないと何を考えればいいかわからなくなります。
課題の定義
私の理解としてはこの課題は
「NxNのマス目があり、一定のルールでのみ動ける銅がある場合に、Nを定義した場合に一筆書き出来るルートを返す関数を作成せよ」
です。
解が複数あった場合や、解が無い場合の挙動は定義されていないので好きに考えて良いという事でしょう。
「解が無いケースは想定しない」、「複数ある場合は最初に見つかったものだけを返す」とすれば簡単そうです。
また、計算量について指定は無いのでいくら時間がかかっても答えが出ればOKと考えて良いハズです。
スタート地点を「訪れた」と判定するかは曖昧ですが恐らく訪問扱いにするんだと思います。
（このあたりは問題の日本語の不備を指摘して条件をこちらで定義してから回答しましょう。出題者の性格や能力に問題があれば減点されるかもしれませんが、不正確な前提でプログラムを作るという悪癖をつけるよりはマシです）
- 授業中に前提条件の説明などがあった場合はそれを加味してください。
ゴールの定義
とりあえず簡単そうなところをゴールとしましょう。
探索で簡単なのは総当たりです。
（Nの範囲が指定されていないので、総当たり以外の方法だとアルゴリズムが論理的に正しいである証明を添付する必要が発生するでしょう。）
これによってゴールは
- 定められた範囲について、定められた動き方をする駒について全パターンの移動を試行する
- 終了条件を満たした場合は正解として移動ルートを返却する。
の両方を満たすプログラムの作成ということになりました。
ゴールの分解
ゴールについて思いつく限り条件を詳細化していきます。
- 定められた範囲について、定められた動き方をする駒について全パターンの移動を施行する
→「全パターン」を構成する要素とは？
→「全」とは？どれだけ試行したら全パターンと言える？
- 試行中に終了条件を満たした場合は正解として移動ルートを返却する
→何を持って終了条件とするのか？
ゴールの分解は割と難しいというか、アルゴリズムそのものになるので、先に具体例から考えてみましょう。
具体例を考えてみる
どうすれば総当たり出来るかについて、具体例を考えてみて具体例から汎用的なアルゴリズムを考えてみましょう。
いきなり9x9で考えると訳が分からなくなると思います。
まずは最小の1x1で考えてみましょう。
1x1だと何も考えなくても
スタート地点のみを訪れるルートが正解で、「全パターン」は1パターンだけだとわかります。
この場合、どこにも移動しなくても修了条件を満たしていることもわかります論点がわかります。
ではここで、
1x1の場合に正解として返すべき値はなんでしょうか？
なぜ全パターンが一つだけだと判断できたでしょうか？
1x1の場合の「終了条件」は何でしょうか？
この三つをプログラムに落とし込んでみて下さい。
作ったプログラムにbronze(1)とした場合に正しい正解を返してくれればOKです。
2x2の場合は脳内だけだと難しそうですが、ノートにでも書いて解いてみましょう。（左上への移動を╔と書きます）
- 左上スタート→解無し
初手→だと左下に行けず、初手↓だと右上に行けない
- 右上スタート→ ↓╔↓
初手は↓以外には移動できず、2手目は╔にしか移動できず3手目は→が訪問済みなので行けないので↓のみ
- 左下スタート→ →╔→
初手は→にしか移動できない、2手目は╔にしか移動できない。3手目は↓は訪問済みなので行けない
- 右下スタート→解無し
初手は╔にしか行けず、2手目は↓に行っても→に行ってもその後は移動できない
1x1で書いたプログラムは正しい2x2の条件を与えた場合に正しい答えを返してくれているでしょうか？
返してくれない場合は何か条件が足りないので、自分がノートに書いたときに何を持って判断したかを思い出して、プログラムに反映します。
という感じで3x3,4x4,,,と条件を設定して、答えが正しいかどうかを判定していきましょう。
投稿2018/06/20 11:21
編集2018/06/20 11:32
総合スコア18713
0
総当たり
総当たりでもいいと思いますが、
- 二次元座標マップ(二次元配列)として変数 map を作り、全要素値を false にする。要素値は通過フラグである(通過済 = true, 未通過 =false)。
- 現在の座標として、変数 x, y を作る
- 初期座標をランダムに決定し、変数 x, y を初期化。変数 map の該当座標値を true にする
- 移動先として「左上」「下」「右」をランダムに決定する
- 移動座標の map 値が true なら 4. へ戻る。座標が false なら true に変更し、変数 x, y を初期化
-
- で3回 4. へ戻る動作が発生したら終了
三手先をシミュレーション
三手先をシミュレーションすると、直前の二手によって、移動先の「左上」「下」「右」の中で移動できない選択肢がある事に気が付きます。
- なぜ移動できないのか
- どういう条件になると移動できないのか
上記を論理的に考え、アルゴリズムに落とし込むだけでも最適化は可能だと思います。
2手前の移動方向と1手前の移動方向が異なる時,この2つに使われていない移動方向に移動することが出来ないですね(すでに訪問済みであるため)。
そうですね。
- 直前のニ手を変数で持っておく
- 移動可能な方向を変数で持っておく
['left-up', 'right', 'down']
このようにすれば、変数値を変更する事で移動可能な方向を制御出来ます。
座標による詰み
例えば、上から3行目の左端から右端まで、右方向に移動し続けたとします。
次に「左上」に移動すれば、3行目より下に行けなくなり、「下」に移動すれば、3行目より上に行けなくなります。
つまり、同一行で全ての列が通過済の状況になると、上下のどちらかの全座標が通過済でない限りは詰みます。
各行の通過済の列数を記録しておけば、このような事態は防げます。
列に関しても、同様ですね。
Re: okamot さん
投稿2018/06/20 22:37
編集2018/06/21 03:55
総合スコア18162
0
すでに tanat さんが、2 × 2 のとき（以後、これを[2,2] と書きます）に解が限定されることは示されていますから、これを拡張します。
[2,2]の解があるときのパターンから、拡張して、
・基点が左下である場合は [2,n] は解ける（[2,2]の後に左上、→と続けられる）
・基点が右上である場合は [m,2] は解ける（[2,2]の後に左上、↓と続けられる）
ことは分かります。
さらに、
・基点が左下である場合は、[3w+1,n] は解けない （ただし、wは0以上の整数）
これは[2,n]を書き切った後、右上にいるので、そこから→↓(×n）で[3,n] が解けることが分かります。そこからさらに→へ移動するとまた [2,n] のパターンになるので、横が 3w+1 でないときに解けることになります。
・基点が右上である場合は、[m,3h+1] は解けない（ただし、hは0以上の整数）
であることも分かります。
※[m,2]を書き切ると左下にいるので、そこから↓→（×n）で[m,3]が書け、そこからさらに下で[m,2]のパターンが再現される
って、これで解けるパターンが限定されたので、あとはそれに当てはまっていれば手順通りに埋めていくだけですね。
投稿2018/06/21 01:47
総合スコア13703
もう少し他に解けるパターンがありました。
起点が左下である場合、[m,3h] は解ける
[2,3h] を書ききった後（右上にいる）に、→、→×(m-2）↓↓(┌↓)×(m-2)で[m-2,3]を埋めていくパターンが作れます。ただしこのパターンの終端は右下ではないので、そこからさらにつなげることは出来ません。
0
有向グラフのハミルトン路問題と思われます。すいません。力任せ探索でしか私は解けませんでした。組合せ爆発になるのでn=7以上は時間がかかって解けていません。
CoffeeScript
1bronze = (n) -> 2 masuToPoint = (m) -> 3 [m %% n, m // n] 4 5 pointToMasu = ([x, y]) -> 6 return -1 unless 0 <= x < n 7 return -1 unless 0 <= y < n 8 x + y * n 9 10 masuMax = n**2 - 1 11 masuList = [0..masuMax] 12 masuNextList = for i in masuList 13 [x, y] = masuToPoint(i) 14 [ 15 pointToMasu([x - 1, y - 1]) 16 pointToMasu([x + 1, y]) 17 pointToMasu([x, y + 1]) 18 ].filter (m) -> 0 <= m <= masuMax 19 20 hamiltonianPath = (current, passed) -> 21 passed.delete(current) 22 return true if passed.size == 0 23 masuNextList[current] 24 .filter (next) -> passed.has(next) 25 .some (next) -> hamiltonianPath(next, new Set(passed)) 26 27 (i for i in masuList when hamiltonianPath(i, new Set(masuList))) 28 29for i in [1..6] 30 beginTime = new Date 31 result = bronze(i) 32 endTime = new Date 33 diffMsec = endTime.getTime() - beginTime.getTime() 34 console.log "#{i} (#{diffMsec} msec): #{bronze(i)}"
JavaScriptのコードが欲しい場合はTry CoffeeScriptで自分で変換してください。
計算量はO(n^2*3^(n^2))ぐらい？大きすぎる…。
さらに最適化を目指すためのアイデア
- 0からn^2-1への対角線で鏡像になっているので、求めるのは半分だけで良い。(残り半分は自動的に決まる)
効果は、たかが半分、されど半分。
2. メモ化。
JavaScriptのMapはNaNを除き===での比較になるため、ArrayやSetのオブジェクトは中身が同じでも異なると判断されてしまいます。。一度一意の文字列に変換するという方法で実装してみましたが、逆に遅くなってしまいました。
3. 最後まで探索しなくても、打ち切りのパターンがあるはず。
どういう条件で打ち切りできるのか、よくわかりませんでした。残りを区切る壁みたいのが出来たら、打ち切れるんだけど、どうやって検出するんだろう。
4. ハミルトン閉路ではない。
もし、ハミルトン閉路であれば、全てが可能という回答になります。しかし、そうではなさそうです。
5. スタック数がO(n^2)。
再帰させない方法はわかりませんでした。あるのかな？
6. 探索順。
単純に順番を変えてもほとんど変わりませんでした。よくわかりません。
7. パターンを見いだす。
奇数と偶数でそれぞれパターンはありそうですが、よくわかりません。
8. 2x2で埋める。
2x2の場合は右上と左下にあるときだけ埋められる。つまり、このパターンでうめていければ？
9. なんかのアルゴリズム。
たぶんありそうだけど、不勉強なので、わかりません。
私にはお姉さんを救うことは出来ないようです。
投稿2018/06/20 13:46
編集2018/06/20 13:48
総合スコア21735
回答ありがとうございます。ハミルトン路というのは初めて聞いたので調べてみたのですがこの問題はたしかに同じような問題ですね。自分はすべてのマスを訪れる通りが1つもない開始位置で探索を打ち切ろうと思ってたんですけど難しそうです。
あなたの回答
tips
プレビュー
