人工智能基础-动态规划

动态规划与运筹学

田忌赛马中,使用下等马对战上等马,使用上等马和中等马对战中等马和下等马,这就是运筹学的一个应用

运筹学是应用数学的一个分支,用来解决决策问题,使用数学的方法来做出最佳安排,它在博弈论中也占据着重要地位

动态规划是运筹学的一个分支,是计算最佳决策的过程,它的主要思想是“分解”和“记忆”,分解,即把一个问题分为多个相似的子问题；记忆,即保存已经计算出的结果,防止重复计算

适用条件

最优性原理

若当前问题的决策是最优决策,那么子问题的决策也必须是最优决策

无后效性原理

子问题的决策无法直接影响父问题的决策.无论子问题的决策是否是最佳决策,都不会影响到父问题的决策,但是如果子问题的决策不是最佳决策,那么父问题的决策也一定不是最佳决策

重叠性原理

父问题可以分解成多个子问题,而子问题同样也可以分解成多个子问题,这些子问题可能会出现重复,为了减少计算次数,需要在计算后保存子问题的解,在下次遇到时就可以直接使用

斐波那契数列

问题描述

求出前两项都为1的斐波那契数列的第50项

问题分解

用f(n)来表示第n个斐波那契数,则f(n)=f(n-1)+f(n-2),且当n=1,2时,f(n)=1

代码实现

斐波那契数列

#include <iostream>
#include <stdio.h>
#include <string.h>
 
long long fib[51]{};
 
long long Fibonacci(int i);
 
int main(){
    //打印第50个斐波那契数
    printf("%lld\n", Fibonacci(50));
    return 0;
}
 
//返回第i个斐波那契数列的数
long long Fibonacci(int i){
    if(fib[i] != 0) return fib[i];
    if(i <= 2){
        fib[i] = 1;
    } else{
        fib[i] = Fibonacci(i-1) + Fibonacci(i-2);
    }
    return fib[i];
}

数塔问题

问题描述

Description
设有一个三角形的数塔,顶点结点为根结点,每个结点有一个整数数值.从顶点出发,在每一个结点可以选择向左下走或者向右下走,一直走到底层,要求找出一条路径,使得路径上的和最大.
Input
输入数塔层数n
输入n层数塔
Output
输出最大和
Sample Input
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
Sample Output
max=86

问题分解

设第i层,第j个数为a[i][j], 向下走的最大和为f(i, j),则f(i, j)=a[i, j] + max{f(i+1,j),f(i+1,j+1)}

代码实现

数塔问题

#include <iostream>
#include <stdio.h>
#include <string.h>
 
using namespace std;
 
int n;
int **arr;//由于不知道n的范围,采用指针方式定义
int **res;//储存已经计算过的结果
 
int f(int i, int j);
 
int main() {
    cin >> n;//输入层数
    arr = new int *[n];
    res = new int *[n];
    for(int i=0;i<n;i++){
        arr[i] = new int [n];
        res[i] = new int [n]{};//在定义指针的同时初始化数组为0
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            cin >> arr[i][j];//输入数字
        }
    }
    cout << "max=" << f(0,0);
    return 0;
}
 
int f(int i, int j){
    if(res[i][j] != 0) return res[i][j];
    if(i >= n-1){//已经到达最底层
        res[i][j] = arr[i][j];
    }else{
        res[i][j] = arr[i][j] + max(f(i+1,j),f(i+1,j+1));;
    }
    return res[i][j];
}

最长公共子序列

问题描述

Description
给定两个字符串,输出两个字符串的最长公共子序列长度
Input
输入2个字符串(保证字符串长度不超过500)
文件有多组数据以‘#’号结束
Output
输出最长公共子序列长度
Sample Input
abc
abc
abcd
acdef
#
Sample Output
3 3

问题分解

设函数f(i,j)返回字符串a的第i个字符开始,字符串b的第j个字符开始的最长公共序列长度.当i==j时,f(i,j)=f(i-1,j-1)+1,否则,f(i,j)=max{f(i,j-1),f(i-1,j)}

代码实现

最长公共子序列

#include <iostream>
#include <stdio.h>
#include <string.h>
 
using namespace std;
 
char a[501];//序列A
char b[501];//序列B
int len_a,len_b;
int res[501][501];
 
int f(int i, int j);
 
int main() {
    while (cin >> a && a[0] != '#' && cin >> b) {
        //初始化res数组
        for (int i = 0; i < 501; i++) {
            for (int j = 0; j < 501; j++) {
                res[i][j] = -1;
            }
        }
        len_a = strlen(a);
        len_b = strlen(b);
        cout << f(0,0) << endl;
    }
    return 0;
}
 
int f(int i, int j) {
    if(i >= len_a || j >= len_b) return 0;
    if (res[i][j] != -1) return res[i][j];
    if (a[i] == b[j]) {
        res[i][j] = f(i + 1, j + 1) + 1;
    } else {
        res[i][j] = max(f(i + 1, j), f(i, j + 1));
    }
    return res[i][j];
}

01背包

详见 01背包问题-回溯与动态规划解法

导弹拦截问题

问题描述

Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统.
Input
输入多个数据m：(m<=30000)
389 207 155 300 299 170 158 65
Output
6(最多能拦截的导弹数)
2(要拦截所有导弹最少要配备的系统数)
Sample Input
389 207 155 300 299 170 158 65
Sample Output
6
2

问题分解

拦截弹一次比一次低,说明每次导弹的高度会越来越低,把拦截的导弹按序号排序,它们的高度会是一个下降序列,所以最多能拦截的导弹数就是最长下降子序列的长度

同理,每次计算出最长下降子序列之后,移除这条子序列,重复计算,所以最少配备的系统数就是下降子序列的数量,显然,下降子序列的数量就是最长上升子序列的长度,因为在上升子序列里,每一项都一定分布在不同的下降序列里

设导弹数量为len, f(i)表示从i开始的最长下降子序列长度,只需要从它后面的导弹里找出导弹j,使得height(i) >= height(j),且f(j)+1>=f(i),则f(i)的值就是f(j)+1

g(i)表示从i开始的最长上升子序列长度,它与f(i)同理,只是要把条件改成height(i) < height(j)

代码实现

导弹拦截问题

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <sstream>
#include <string>
 
using namespace std;
 
int temp;
int height[1000];
int len = 0;
 
int res_f[1000]{};
int res_g[1000]{};
 
int f(int i);//最长下降子序列
int g(int i);//最长上升子序列
 
int max_f = 1, max_g = 1;//记录最大值
 
int main() {
    string s;
    getline(cin, s);
    istringstream istr(s);
    //读取导弹高度
    while (istr >> temp) {
        height[len] = temp;
        len++;
    }
    //求最大值
    for (int i = 0; i < len; i++) {
        if (f(i) > max_f) max_f = f(i);
        if (g(i) > max_g) max_g = g(i);
    }
    cout << max_f << endl << max_g << endl;
    return 0;
}
 
int f(int i) {
    if (res_f[i] != 0) return res_f[i];
    res_f[i] = 1;//因为它自己就是一个序列,所以初始值为最小值为1
    if (i < len - 1) {
        for (int j = i + 1; j < len; j++) {
            if (height[i] >= height[j] && f(j) + 1 >= res_f[i]) res_f[i] = f(j) + 1;
        }
    }
    return res_f[i];
}
 
int g(int i) {
    if (res_g[i] != 0) return res_g[i];
    res_g[i] = 1;//因为它自己就是一个序列,所以初始值为最小值为1
    if (i < len - 1) {
        for (int j = i + 1; j < len; j++) {
            if (height[i] < height[j] && g(j) + 1 >= res_g[i]) res_g[i] = g(j) + 1;
        }
    }
    return res_g[i];
}