本履歴

購入した古本の履歴と時々プログラミング

数学パズル本に敢てプログラムで挑戦(4)

これも有名な問題で、Youtubeなどに解説動画がたくさんある。

www.youtube.com

7. Bridge Crossing at Night

4人の人が懐中電灯で橋を夜間渡るのだが、4人それぞれは渡るのに1分、2分、5分、10分かかり、橋は同時に2人までしか渡れない。二人同時に渡る時はかかる時間は遅い方の時間。渡る時に懐中電灯は必須。この時全員が渡る時間を最小化せよ

ついに来た。幅優先探索ではうまくいかないパターンが。これも、懐中電灯の位置が左と右どちらか、4名がそれぞれ橋の左右どちらにいるかの5bitで状態を表すことが出来る。それを頂点としてグラフを作り、ダイクストラの最短経路アルゴリズムを適用する。結果は17分で正解だった。ダイクストラの最短路アルゴリズムはこのblogでコードを紹介していたはず。このグラフのエッジは橋の移動を表すけど、その重みがかかる時間になり、それを最小化する、すなわち最短経路を求めることに繋がる。実装したプログラムはグラフを大域的に最初に生成して、それを既存のダイクストラアルゴリズムに渡している。グラフ問題でいつも迷うのはこのように最初にグラフを大域的に生成しちゃうか、頂点に辿り着くたびにそこから出る辺を生成するか。頂点の数が少なければ問題ないが、頂点数が沢山ありかつほとんど訪れないなら無駄になるから。ちなみに、このプログラムでかかる時間を変えると、グラフの辺の重みが変わるのでまた違ったルートが最短路になるし、peopleの数を4人から増やすとまた違う大きいグラフになるので面白い。でも多分、この[1,2,5,10]が盲点なルートなのだと思う。これはプログラムでは分からない点。

#ダイクストラアルゴリズムは略

def to_code(people_pos, light_pos)
  code = 0
  people_pos.each{|b|code = 2 * code + b}
  2 * code + light_pos
end

def pos_from(code, size)
  light_pos = code & 1
  people_pos = []
  size.times{
    code /= 2
    people_pos << (code & 1)
  }
  [people_pos.reverse, light_pos]
end

def generate_edge_cost(people)
  #flashlightの位置(左...0,右...1)とpeopleそれぞれの位置のビットで管理
  size = people.size
  node_num = 2 ** (size + 1)
  edges = Array.new(node_num){Array.new}
  costs = Array.new(node_num){Hash.new(INF)}
  node_num.times{|code|
    people_pos, light_pos = pos_from(code, size)
    candidate = []
    people_pos.each_with_index{|b, idx|candidate << idx if b == light_pos}

    #how many can cross the bridge at the same time
    1.upto(2){|n|
      candidate.combination(n).each{|indices|
        pos = people_pos.dup
        indices.each{|idx|pos[idx] = 1 - light_pos}
        next_code = to_code(pos, 1 - light_pos)
        edges[code] << next_code
        costs[code][next_code] = indices.map{|idx|people[idx]}.max      
      }
    }
  }
  [edges, costs]
end

people = [1, 2, 5, 10]
edges,costs = generate_edge_cost(people)
d, prec = dijkstra(edges, costs)
goal = to_code([1] * people.size, 1)
puts d[goal]