广度优先搜索与启发式

1.三个强盗和三个商人同时来到渡口，准备渡河。岸边只有一条能坐二人的小船，并无艄公。三个强盗暗暗商定：不论在何处(即左岸，右岸或船上)，只要他们的人(强盗)比对方多，就把商人杀死。为了使商人安全过河，应如何渡。

2.八八年全国竞赛题：

一个瓶中装有80毫升化学溶剂，实验中需把它平分成两份。没有量具，只有两个杯子，其中一个杯子的容量是50毫升，另一个杯子的容量是30毫升。编程，找出平分80毫升容液的最少步骤。

3.有2N+2个盒子排成一排，其中有两个相邻的空盒，有N盒子含有符号A， N个盒子含有符号B，任意两个非空相邻盒子中的内容可移入空盒中，但不得交换两符号前后顺序。将全部A放到全部B的左边，不管相邻空盒在何处。找出交换次数最少的方案来。

4.在N*3的方格棋盘中，两端各放N枚黑色和白色的棋子。棋子跳动依同际象棋马步跳法。试编程序求解让计算机跳动最少步数，把黑，白两色棋子换位。

说明：棋子依马步跳动一次计一步。连跳计一步。但连跳中不允许有多余的跳动次数。

5.灯盘由4*4的方格组成，其编号如图所示。每个格子里有一个灯，除第3，5，12，14格以外的格子里都装有一个按键。在图1中按键以[]表示。为了方便，灯片与键号都以格号表示。按键控制灯盘使相应灯反相。

所谓反相指的是：灯由亮变暗或由暗变亮。十二个按键的控制作用如表1所示。

┎──┰──┰──┰──┒

┃1 □┃2 □┃3 ┃4 □┃

┠──╂──╂──╂──┨

┃5 ┃6 □┃7 □┃8 □┃

┠──╂──╂──╂──┨

┃9 □┃10□┃11□┃12┃

┠──╂──╂──╂──┨

┃13□┃14┃15□┃16□┃

┖──┸──┸──┸──┚

图1

┎──┰─────────┒ 用1表示灯亮，用0表示灯暗。灯盘的状态