問題
４人が壊れそうな橋を渡ろうとしている。全員橋の同じ側にいる。暗闇の中で懐中電灯は一つしかない。
橋は一度に最大２人まで渡ることができ、渡るときは（１人であれ２人であれ）懐中電灯を持っていなければならない。
橋を渡る時間は以下のとおりとする。
メンバー
|
橋を渡るのにかかる時間
|
A
|
１分
|
B
|
２分
|
C
|
５分
|
D
|
１０分
|
橋を１７分以内にわたることはできるか？
方針
最初に立てる方針は、最も橋を渡る時間が短いメンバーAに大活躍してもらうことでしょう。懐中電灯を持って戻る役割をすべてAにやってもらうのです。このとき、左岸から右岸にわたる総時間は（２＋５＋１０）分、右岸から左岸に戻る総時間は（１＋１）分で、総時間が１９分となります。
よってこの方針が最善であるとすれば、この問題の答えは「１７分以内に全員が渡るのは不可能である」ということになります。
Aに大活躍してもらう例
方向
|
メンバー
|
時間
|
左→右
|
A,B
|
２
|
右→左
|
A
|
１
|
左→右
|
A,C
|
５
|
右→左
|
A
|
１
|
左→右
|
A,D
|
１０
|
１９
|
本当にそうでしょうか？
コードでシミュレーションしてみると、１７分で渡り切れるパターンがみつかります。
コード
swift3
//
// main.swift
// BridgeCrossingAtNight
//
// Created by 山崎真一郎 on 2017/02/18.
// Copyright © 2017 山崎真一郎. All rights reserved.
//
import Foundation
enum Member {
case MemA, MemB, MemC, MemD
}
func SpendTime(mem:Member) -> Int
{
switch mem {
case .MemA:
return 1
case .MemB:
return 2
case .MemC:
return 5
case .MemD:
return 10
}
}
func SpendTimeFor2(mem1:Member, mem2:Member) -> Int
{
return max(SpendTime(mem: mem1), SpendTime(mem: mem2))
}
func LeftSide2RightSide(
leftSideMember:inout Array<Member>,
rightSideMember:inout Array<Member>,
mem1:Member, mem2:Member) -> Int
{
if leftSideMember.count == 0
{
return 0
}
leftSideMember.remove(at: leftSideMember.index(of: mem1)!)
leftSideMember.remove(at: leftSideMember.index(of: mem2)!)
rightSideMember.append(mem1)
rightSideMember.append(mem2)
return SpendTimeFor2(mem1: mem1, mem2: mem2)
}
func RightSide2LeftSide(
leftSideMember:inout Array<Member>,
rightSideMember:inout Array<Member>,
mem:Member) -> Int
{
if rightSideMember.count == 0
{
return 0
}
rightSideMember.remove(at: rightSideMember.index(of: mem)!)
leftSideMember.append(mem)
return SpendTime(mem: mem)
}
func BridgeCross(leftSideMember:Array<Member>, rightSideMember:Array<Member>)
{
// L:4 R:0
for cnt1 in 0...(leftSideMember.count - 2)
{
for cnt2 in (cnt1 + 1)...(leftSideMember.count - 1)
{
var _leftSideMember = leftSideMember
var _rightSideMember = rightSideMember
var _sumTime = LeftSide2RightSide(
leftSideMember: &_leftSideMember,
rightSideMember: &_rightSideMember,
mem1: leftSideMember[cnt1],
mem2: leftSideMember[cnt2])
// L:2 R:2
for cnt3 in 0...(_rightSideMember.count - 1)
{
var __leftSideMember = _leftSideMember
var __rightSideMember = _rightSideMember
_sumTime += RightSide2LeftSide(
leftSideMember: &__leftSideMember,
rightSideMember: &__rightSideMember,
mem: _rightSideMember[cnt3])
// L:3 R:1
for cnt4 in 0...(__leftSideMember.count - 2)
{
for cnt5 in (cnt4 + 1)...(__leftSideMember.count - 1)
{
var ___leftSideMember = __leftSideMember
var ___rightSideMember = __rightSideMember
_sumTime += LeftSide2RightSide(
leftSideMember: &___leftSideMember,
rightSideMember: &___rightSideMember,
mem1: __leftSideMember[cnt4],
mem2: __leftSideMember[cnt5])
// L:1 R:3
for cnt6 in 0...(___rightSideMember.count - 1)
{
var ____leftSideMember = ___leftSideMember
var ____rightSideMember = ___rightSideMember
_sumTime += RightSide2LeftSide(
leftSideMember: &____leftSideMember,
rightSideMember: &____rightSideMember,
mem: ___rightSideMember[cnt6])
// L2 R:2
_sumTime += SpendTimeFor2(
mem1: ____leftSideMember[0],
mem2: ____leftSideMember[1])
if (_sumTime <= 17)
{
print("left->right:\(leftSideMember[cnt1]),\(leftSideMember[cnt2])")
print("right->left:\(_rightSideMember[cnt3])")
print("left->right:\(__leftSideMember[cnt4]),\(__leftSideMember[cnt5])")
print("right->left:\(___rightSideMember[cnt6])")
print("left->right:\(____leftSideMember[0]),\(____leftSideMember[1])")
print(_sumTime)
}
}
}
}
}
}
}
}
var leftSizeMember = Array<Member>()
leftSizeMember.append(Member.MemA)
leftSizeMember.append(Member.MemB)
leftSizeMember.append(Member.MemC)
leftSizeMember.append(Member.MemD)
var rightSizeMember = Array<Member>()
BridgeCross(leftSideMember: leftSizeMember, rightSideMember: rightSizeMember)
実行結果
left->right:MemA,MemB
right->left:MemA
left->right:MemC,MemD
right->left:MemB
left->right:MemA,MemB
17
Program ended with exit code: 0
このとき、確かに１７分で渡り切れています。
１７分以内にわたり切るパターン
方向
|
メンバー
|
時間
|
左→右
|
A,B
|
２
|
右→左
|
A
|
１
|
左→右
|
C,D
|
１０
|
右→左
|
B
|
２
|
左→右
|
A,B
|
２
|
１７
|
ポイントは、CとDを一緒に渡らせて、５分のタイムロスを無くすことです。
部分（１回の往復）の最適化に捉われてしまうと、全体の最適パターンに気付けないことはよくありますね！
