状态转移法求解夫妻过河问题

摘要

本文研究夫妻问题。主要运用“状态转移法”解决夫妻过河问题，并用Python编程实现，输出求解过程和结果。分析夫妻对数n和船载人数m和是否有解的关系，给出了该问题的一般提法和解法。

目录
3.1 约束条件 1
3.2 终止条件 1
4.1 编程输出结果： 2
4.2 一般提法 2

第1章问题重述

夫妻过河问题是阿拉伯早期的一道数学题，题目如下：
3对夫妻要过河，河中有一小船，可容纳2人。每个丈夫都不愿让自己的妻子和另一个男人在一起，除非自己也在场。问该如何渡河？

第2章符号说明

在这里插入图片描述

第3章模型搭建

3.1 约束条件

根据题意，给出如下约束条件：

在这里插入图片描述

?? 注意：约束四在编程中需使用！不能忽略

3.2 终止条件

$s_n=(0,0)$ ，即 n 轮时，原本河一岸的夫妻全部渡河成功。优化目标是让 n 取最小。

第4章结果分析

4.1 编程输出结果：

3对夫妻
--- 去0男2女 --->
3男1女
--- 回0男1女 --->
3男2女
--- 去0男2女 --->
3男0女
--- 回0男1女 --->
3男1女
--- 去2男0女 --->
1对夫妻
--- 回一夫妻 --->
2对夫妻
--- 去2男0女 --->
0男2女
--- 回0男1女 --->
0男3女
--- 去0男2女 --->
0男1女
--- 回0男1女 --->
0男2女
--- 去0男2女 --->
0对夫妻

4.2 一般提法
n 对夫妻过河，船只能坐 m 个人，m < n，只有当n/2 < m < n 时，问题才有解。