質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.04%

「プログラマ脳を鍛える数学パズル」の Q59 について教えて下さい

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 669

score 15

「プログラマ脳を鍛える数学パズル」という本に載っている
「Q59 ハンカチ落としの総走行距離」の解答コードで腑に落ちない部分があるので
どなたか教えていただけないでしょうか?

問題は以下です。
長文のためキャプチャ画像である事ご容赦下さい。

イメージ説明

解答のコードは以下です 

@n = 8
# 鬼を含んだ配列。
@all = (0..@n).to_a

#開始時の位置は1を固定した1通り。終了は1を順にずらしたモノ全て。

# 開始時の配置
start = {}
start[(1..@n).to_a] = []

# 終了時の配置
goal = {}
@n.times{|i|
  goal[(1..@n).to_a.reverse.rotate(i)] = []
}

# 移動距離を求める
def dist(log) #log:ハンカチを落とした位置の記録
  return 0 if log.size == 0
  check = log.clone
  pre = check.shift
  sum = @n + pre
  check.each{|c|
    # %@n することにより0をまたぐ場合とそうでない場合をまとめて書ける
    sum += @n + (c + @n - pre) % @n 
    pre = c
  }
  sum
end

# 探索(directionがtrueのとき順方向、falseのとき逆方向)
def search(child, direction)
  child.clone.each{|key, value|
    oni = (@all - key)[0] # 使われていないのが鬼
    @n.times{|i|  #全ての位置に鬼を座らせる
      k = key.clone
      k[i] = oni  #新たに鬼が座った配置
      v = value + [i]  #ハンカチを落とした位置のログ
      if child.has_key?(k) then
        if direction then # 順方向
          child[k] = v if dist(v) < dist(child[k])
        else              # 逆方向
          child[k] = v if dist(v.reverse) < dist(child[k].reverse)
        end
      else
        child[k] = v
      end
    }
  }
end

cnt = 0
while (start.keys & goal.keys).size == 0 do
  if cnt % 2 == 0 then # 偶数のときは順方向に探索
    search(start, cnt % 2 == 0)
  else                 # 奇数のときは逆方向に探索
    search(goal, cnt % 2 == 0)
  end
  cnt += 1
end

# 両方向からの探索結果が合流した場合、最短の移動距離を算出
min = 98
(start.keys & goal.keys).each{|c|
  d = dist(start[c] + goal[c].reverse)
  min = [min, d].min
}

puts min


幅優先探索でスタートとゴールから双方向探索して経路が重なるモノの中から最短になるモノを求めていることは
理解できました。
腑に落ちないのはsearch関数内の逆方向における次の部分です。

child[k] = v if dist(v.reverse) < dist(child[k].reverse)

ここで用いられているdist関数はスタート位置が0である設定で書かれているのですが、
実際に順方向から辿ってきた場合、逆方向のスタート位置は0とは限らず、
1から7のいずれかである場合もあります。
例えば0からスタートの場合

dist([0]) < dist([2])

ですが1からスタートの場合

dist([0]) > dist([2])

と大小関係が逆転し、距離に誤差が出ると思います。
その為に解答コードの最後の

(start.keys & goal.keys).each{|c|
  d = dist(start[c] + goal[c].reverse)
  min = [min, d].min
}


では、

d = dist(start[c]) + dist(goal[c].reverse)


とせずに

d = dist(start[c] + goal[c].reverse)


と、ハンカチの落とした位置をスタートからゴールにまで新たに繋げ直して
dist関数に入れて正確な距離を出しているのだと思います。

なぜ

child[k] = v if dist(v.reverse) < dist(child[k].reverse)


では誤差を無視することが出来るのでしょうか?

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

check解決した方法

0

著者の方に逆方向の

dist(v.reverse) と dist(child[k].reverse)

はスタート位置により大小が逆転する場合があることを伝えたところ
修正を検討するとのことでした。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/01/17 22:42 編集

    ・・あらら、どういう理屈なのか考えてたのに・・・本酷いですね。
    探索の仕方がもの凄く無駄ですし(何故毎回distを最初から計算し直す)

    「プログラム脳」ならこんな探索プログラム組むより一般項考えた方が早いんじゃなかろうかと思います。

    以下一般項。
    あってるとは思うのですが間違いがあったらどなたか指摘していただけると嬉しいです。

    奇数でも偶数でも話はほとんど一緒なので偶数の場合だけ示すと
    N(偶数かつ4以上)人の場合入れ替えるべきペアはN/2-1で、1ペア入れ替えるのに合計3周。最初の0番の1周を加えて
    ⇒少なくとも3N(N/2-1)+Nの移動距離が必要
    N/2-1ペアあるので、各ペアの入れ替え間に移動が必要、これがロスレスに行われても1周かかるので
    A[N] = 3N(N/2-1)+N+(N/2-2)*N=2N(N-2)

    あとは各ペアの入れ替え間移動をロスレスに行うことができるかの検討。
    これは実際に可能で、例えばN=6であれば3と6を軸に反転するものとして
    0⇒1(最初の移動), [023456], dist=6
    1⇒4 (対角位置に移動), [023156], dist=15
    4⇒2 (目的位置に移動), [043156], dist=25
    2⇒1 (目的位置に移動), [043256], dist=33
    1⇒5 (隣に移動, N=6の場合目的地), [043216], dist=40
    5⇒0 (目的地に移動), [543216], dist=48
    1だけ特殊な移動をしていますが、これが各ペアの入れ替え間の移動の役割を担っており、全体的に見ればロスレスになっています。
    8以上の場合も同様に
    1を対角に移動⇒入れ替え⇒1を隣に移動⇒入れ替え⇒1を隣に移動⇒入れ替え⇒・・・
    で成立するはず。

    奇数の場合は同様に考えて4N[N/2]かな・・・?([]は切り捨て)
    結果的にN=1,2も成立しますね

    キャンセル

  • 2020/01/18 14:04 編集

    一般項を求める事ができるのですね、参考になりました。

    奇数の場合を自分も考えてみたのですが、
    色々最短になるパターンはあると思うのですがNotionalKettleさんの書かれた
    偶数の時と似たところで考えると、1の対角の右隣の数字(5人なら3)を固定して
    初めに1をその左隣に移動させる場合で考えました。

    ・初めの0の移動距離が
    N

    ・入れ替えになるペア数が(N-1)/2、入れ替えの最短距離が3周分、一周の距離がNなので
    (N-1)/2 * 3 * N

    ・1をずらす回数が{(N-1)/2-1}回で、その度1周分の長さNが加算されるので
    N * {(N-1)/2-1}

    これらを足すと 2N(N-1) となり


    NotionalKettleさんが出された
    4N[N/2] = 4N(N-1)/2 = 2N(N-1) (Nが奇数の場合)

    と一致し、この一般項で合ってると思います。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.04%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る