问题：
有N个传教士和N个野人来到河边渡河，河岸有一条船，每次至多可供k人乘渡。问传教士为了安全起见，应如何规划摆渡方案，使得任何时刻，河两岸以及船上的野人数目总是不超过传教士的数目(否则不安全，传教士有可能被野人吃掉)。即求解传教士和野人从左岸全部摆渡到右岸的过程中，任何时刻满足M(传教士数)≥C(野人数)和M+C≤k的摆渡方案。
class MissionariesAndCannibals: NSObject {
//传教士和野人数为N，船搭载人数为K
var N:Int = 3
var K:Int = 2
//河岸状态
struct RiverSide {
var missionaries:Int
var cannibals:Int
var ship:Int
}
//加权河岸状态
struct SuperRiverSide {
var current:RiverSide
var currentStepId:Int //在allStates数组中的位置
var preStepId:Int //在allStates数组中的位置
var numOfStep:Int
var checked:Bool
}
//所有加权河岸状态
var allStates:[SuperRiverSide]=[]
//设置题目参数
func reInit(newN:Int, newK:Int) {
N = newN
K = newK
}
// MARK: - 初始状态
init(newN:Int, newK:Int) {
N = newN
K = newK
}
//MARK: - 目标测试
func testTarget(riverSide:RiverSide) -> Bool {
if riverSide.cannibals == 0 && riverSide.missionaries == 0 {
return true;
}else{
return false;
}
}
//MARK: - 开始运算
//采用递归最优先算法RBFS
func start() {
var riverSide = RiverSide.init(missionaries: N, cannibals: N, ship: 1)
var superRiverSide = SuperRiverSide.init(current: riverSide, currentStepId: 0, preStepId: -1, numOfStep: 1, checked: false)
allStates.append(superRiverSide)
goNextState()
}
//MARK: - 扩展一个字节点
func findUnderState(superRiverSide:SuperRiverSide){
// print("\(superRiverSide.current.missionaries) \(superRiverSide.current.cannibals) \(superRiverSide.current.ship)")
if superRiverSide.current.ship==1 {
//船在此岸
/*
船约束条件：1) missionaries>=cannibals || missionaries=0
2) K > missionaries+cannibals > 0
*/
var maxMissioneriesInShip:Int = superRiverSide.current.missionaries
if maxMissioneriesInShip > K{
maxMissioneriesInShip = K
}
for numOfMissionariesInShip in 0...maxMissioneriesInShip
{
// missionaries>=cannibals || missionaries=0
var maxOfMissionariesInShip:Int = numOfMissionariesInShip
if maxOfMissionariesInShip > superRiverSide.current.cannibals{
maxOfMissionariesInShip = superRiverSide.current.cannibals
}
if numOfMissionariesInShip == 0{
maxOfMissionariesInShip = superRiverSide.current.cannibals
}
// K > missionaries+cannibals
if maxOfMissionariesInShip + numOfMissionariesInShip > K {
maxOfMissionariesInShip = K-numOfMissionariesInShip
}
for numOfCannibalsInShip in 0...maxOfMissionariesInShip
{
// missionaries+cannibals > 0
if numOfCannibalsInShip + numOfMissionariesInShip==0{
continue
}
let newRiverSide:RiverSide=RiverSide.init(missionaries: superRiverSide.current.missionaries-numOfMissionariesInShip, cannibals: superRiverSide.current.cannibals-numOfCannibalsInShip, ship: 0)
if testTarget(riverSide: newRiverSide){
//print("sucess")
printState(superRiverSide:superRiverSide)
return
//成功
}else{
if testStep(riverSide: newRiverSide){
if !checkSuperRiverSide(riverSide: newRiverSide){
let newSuperRiverSide = SuperRiverSide.init(current: newRiverSide, currentStepId: allStates.count, preStepId: superRiverSide.currentStepId, numOfStep: superRiverSide.numOfStep+1, checked: false)
allStates .append(newSuperRiverSide)
}
}
}
}
}
}else{
//船在对岸
var maxMissioneriesInShip:Int = N-superRiverSide.current.missionaries
if maxMissioneriesInShip > K{
maxMissioneriesInShip = K
}
for numOfMissionariesInShip in 0...maxMissioneriesInShip
{
//
var maxOfMissionariesInShip:Int = numOfMissionariesInShip
if maxOfMissionariesInShip > N-superRiverSide.current.cannibals{
maxOfMissionariesInShip = N-superRiverSide.current.cannibals
}
if numOfMissionariesInShip == 0{
maxOfMissionariesInShip = N-superRiverSide.current.cannibals
}
//
if maxOfMissionariesInShip + numOfMissionariesInShip > K {
maxOfMissionariesInShip = K-numOfMissionariesInShip
}
for numOfCannibalsInShip in 0...maxOfMissionariesInShip
{
//
if numOfCannibalsInShip + numOfMissionariesInShip==0{
continue
}
let newRiverSide:RiverSide=RiverSide.init(missionaries: superRiverSide.current.missionaries+numOfMissionariesInShip, cannibals: superRiverSide.current.cannibals+numOfCannibalsInShip, ship: 1)
if testStep(riverSide: newRiverSide){
if !checkSuperRiverSide(riverSide: newRiverSide){
let newSuperRiverSide = SuperRiverSide.init(current: newRiverSide, currentStepId: allStates.count, preStepId: superRiverSide.currentStepId, numOfStep: superRiverSide.numOfStep+1,checked: false)
allStates.append(newSuperRiverSide)
}
}
}
}
}
let newSuperRiverSide = SuperRiverSide.init(current: superRiverSide.current, currentStepId: superRiverSide.currentStepId, preStepId: superRiverSide.preStepId, numOfStep: superRiverSide.numOfStep, checked: true)
allStates.replaceSubrange(Range(newSuperRiverSide.currentStepId...newSuperRiverSide.currentStepId), with:[newSuperRiverSide])
goNextState()
}
//MARK: - 找到权值最低且未扩展的子节点
func goNextState() {
var nextState = allStates[0];
for superRiverSide in allStates {
if superRiverSide.checked==false{
nextState=superRiverSide
break
}
}
if (nextState.checked == true){
print("no more state")
return
}
for superRiverSide in allStates {
if superRiverSide.checked==false{
if superRiverSide.numOfStep < nextState.numOfStep{
nextState=superRiverSide
}
}
}
findUnderState(superRiverSide:nextState)
}
//MARK: - 查找状态是否已被记录
func checkSuperRiverSide(riverSide:RiverSide) -> Bool {
for superRiverSide in allStates {
if superRiverSide.current.missionaries == riverSide.missionaries{
if superRiverSide.current.cannibals == riverSide.cannibals{
if superRiverSide.current.ship == riverSide.ship{
return true
}
}
}
}
return false
}
//MARK: - 检测动作是否合规
/*
河岸约束条件：1) missionaries>=cannibals || missionaries=0
2) N-missionaries>=N-cannibals || N-missionaries=0
*/
func testStep(riverSide:RiverSide) -> Bool {
if riverSide.missionaries == 0 {
return true
}
if riverSide.missionaries == N{
return true
}
if (riverSide.missionaries == riverSide.cannibals){
return true
}
return false
}
//MARK: - 打印结果
func printState(superRiverSide:SuperRiverSide){
if superRiverSide.preStepId != -1 {
var preState=allStates[superRiverSide.preStepId]
printState(superRiverSide:preState)
}
print("左岸：\(superRiverSide.current.missionaries) \(superRiverSide.current.cannibals) 右岸：\(N-superRiverSide.current.missionaries) \(N-superRiverSide.current.cannibals)")
}
}
网友评论