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

Question

「プログラマ脳を鍛える数学パズル」という本に載っている
「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)

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

Answer 1

著者の方に逆方向の

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

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

Comments

[退会済みユーザー]

・・あらら、どういう理屈なのか考えてたのに・・・本酷いですね。
探索の仕方がもの凄く無駄ですし（何故毎回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も成立しますね

[pyxis]

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

奇数の場合を自分も考えてみたのですが、
色々最短になるパターンはあると思うのですが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が奇数の場合)

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