计算智能上机题4

计算智能上机题4

上机题：

1.邮票问题：设有n种不同面值的邮票，每封信规定最多能贴m张邮票，写出算法对于给定的n、m ，求出邮资的最大连续区间。（n=4，m=5时，区间为[1，71]）

2.0-1背包问题：求从n种物品中选取若干物品装载容量为m的背包的最佳方案（x1，x2……xn）。其中第i个物品的重量为wi，价值为pi(i=1……n)。在åxiwi£m的前提下，最大。

3.八后问题：在8×8的棋盘上摆放8个无法相互攻击的皇后。要求找出所有解。

（回溯）

4.骑士游历问题：让国际象棋中的马在8×8的棋盘上从中间某个位置出发，64步跳完所有方格。（回溯）

5.翻转烙饼排序问题：采用每次只能翻转最上面的若干个数字的方法将n个数排序。要求总的翻转次数最少。（动态规划）

6.24点问题：4张1~10的扑克牌，通过四则运算得到24。（穷举）

7.求最大最小值问题：找出给定数组中最大和最小的结点。要求最多用1.5×n次比较。

8.对于n2的矩阵，找出其中n个最小的数，且来自不同的行和列。

练习题：（运用A*算法）

1.设计估计函数，并画出九宫问题下述状态到目标状态的搜索树。

21 6

4 8

75 3

2.滑块游戏

White

White

White

Black

Black

Black

Empty

平移，可以隔一个走，两个走。耗散值：移动，1；隔1，1；跳2,2;

① 用最少的步数②用最少的耗散值

评估函数可以是任意计算机可以做的。找规律且目标不唯一。即空格在的位置不同。A*重点在评估函数，可加深理解评估函数。