0%

人工智能第二章作业

  • 这篇文章将不加解释的给出人工智能课的个人作业答案.
  • 如果有疑问可以去我的Gitea站提交issue给我.
  1. 在 3 X 3 的空格内,用1,2,…, 9 的9个数字填入9个空格内,使得每行数字组成的十进制数平方根为整数。试用一般图搜索搜索算法求解。

    • 由于使用广度优先搜索时需要存储每次的数组状态,占用空间过多,所以选择使用深度优先搜索,先将数组填满后判断是否符合答案要求(即每三位是一个完全平方数),符合则输出。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    #include <iostream>
    #include <cmath>

    using namespace std;

    int n = 9, num[9];
    bool vis[9];

    bool check(int a) {
    int t = sqrt(a);
    return a == t * t;
    }
    void dfs(int i) {
    if (i == n) {
    int a = num[0] * 100 + num[1] * 10 + num[2];
    int c = num[3] * 100 + num[4] * 10 + num[5];
    int b = num[6] * 100 + num[7] * 10 + num[8];
    if (check(a) && check(b) && check(c)) {
    for (int j = 0; j < n; ++j) {
    printf("%d ", num[j]);
    }
    printf("\n");
    }
    return;
    }
    for (int j = 1; j <= n; ++j) {
    if (vis[j]) { continue; }
    vis[j] = true;
    num[i] = j;
    dfs(i + 1);
    vis[j] = false;
    }
    }

    int main() {
    dfs(0);
    return 0;
    }
  2. 分析宽度优先搜索和深度优先搜索的优缺点,举出他们的正例和反例。

种类 优点 缺点
宽度优先搜索 可以直接获得到达每一个状态的最优路径。对于某一已确定状态,无需对其再次更新。 在解所处深度很深时状态数极大,会导致时间过长。队列中需要存储一层的数据,空间占用较大。
深度优先搜索 在仅需一组可行解时搜索效率较高,并可利用剪枝与启发式搜索的方式进一步提高效率。栈中仅需存储一条递归路径上的数据,占用空间较少。 当搜索到某状态时,不能保证结果是最佳的,要对全图进行搜索后才能获得最佳结果;当搜索路径较深时可能会导致栈溢出。
  1. 有一个农夫带一只狐狸、一只小羊和一个菜篮过河。假设农夫每次只能带一样东西过河,考虑安全,无农夫看管时,狐狸和小羊不能在一起,小羊和菜篮不能在一起。试设计求解该问题的状态空间,并画出状态空间图。
    2-3

欢迎关注我的其它发布渠道