人工智能及其应用 实验课 源代码
梵塔问题、传教士野人渡河问题、宽度优先和深度优先求解路径、八数码问题、A*算法实现15数码问题、使用A*算法求解最短路径、动物识别系统、自行设计故障诊断系统、使用遗传算法求解函数最大值、使用遗传算法求解旅行商问题
文章共33,445字 · 阅读需要大约112分钟
一键AI生成摘要，助你高效阅读
问答
·
实验一
梵塔问题
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll ans = 0;
void dfs(char a, char b, char c, int n)
{
if(n == 1)
{
ans++;
cout << a << " -> " << c << "\n";
}
else
{
dfs(a, c, b, n - 1);
ans++;
cout << a << " -> " << c << "\n";
dfs(b, a, c, n - 1);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
dfs('A', 'B', 'C', n);
cout << ans << "\n";
return 0;
}
传教士野人渡河问题
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int dx[] = {1, 0, 0, 2, 1};
const int dy[] = {1, 2, 1, 0, 0};
array<int, 3> ans[N], tot[N];
map<array<int, 3>, bool> v;
int sum, tt = -1;
int a, b;
// 本岸位置的 野人 和 传教士 数量 1 ： 本岸 -1 ：对岸
bool check(array<int, 3> t)
{
int y = t[0], c = t[1], f = t[2];
if(y < 0 || c < 0 || y > a || c > b) return 0;
if((c != 0 && y > c) || (b - c != 0 && a - y > b - c)) return 0;
return 1;
}
void dfs(array<int, 3> t)
{
int y = t[0], c = t[1], f = t[2];
if(y == 0 && c == 0 && f == -1)
{
sum++;
cout << sum << "\n";
for(int i = 0; i <= tt; i++)
{
cout << (ans[i][2] == 1 ? "去" : "回") << " ";
cout << "野人:" << ans[i][0] << " 传教士:" << ans[i][1] << "\n";
}
return;
}
array<int, 3> tmp;
for(int i = 0; i < 5; i++)
{
tmp = {y - f * dx[i], c - f * dy[i], -f};
if(check(tmp) && !v[tmp])
{
v[tmp] = 1;
ans[++tt] = {dx[i], dy[i], f};
dfs(tmp);
v[tmp] = 0;
--tt;
}
}
}
int main()
{
cout << "请分别输入野人数量和传教士数量:";
cin >> a >> b;
array<int, 3> t = {a, b, 1};
v[t] = 1;
dfs(t);
v[t] = 0;
return 0;
}
实验二
宽度优先和深度优先求解路径
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 2 * N;
const int inf = 0x3f3f3f3f;
int n, m;
int s, d;
int dis[N], vis[N], pre[N];
int e[M], h[N], ne[M], w[M], idx;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
vis[u] = 1;
if(u == d) return;
for(int i = h[u]; ~i; i = ne[i])
{
int to = e[i], val = w[i];
if(!vis[to] || dis[u] + val < dis[to])
{
dis[to] = dis[u] + val;
pre[to] = u;
dfs(to);
}
}
}
// 只能求不带权图
void bfs(int s)
{
queue<int> q;
vis[s] = 1;
q.push(s);
while(!q.empty())
{
int t = q.front();
q.pop();
if(t == d) return;
for(int i = h[t]; ~i; i = ne[i])
{
int to = e[i];
if(vis[to]) continue;
vis[to] = 1;
dis[to] = dis[t] + 1;
pre[to] = t;
q.push(to);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m >> s >> d;
for(int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
memset(dis, 0x3f, sizeof dis);
memset(pre, -1, sizeof pre);
dis[s] = 0;
// dfs(s);
bfs(s);
vector<int> path;
int t = d;
path.push_back(t);
while(pre[t] != -1)
{
path.push_back(pre[t]);
t = pre[t];
}
reverse(path.begin(), path.end());
cout << "最短的路径:\n";
for(int i = 0; i < int(path.size() - 1); i++)
cout << path[i] << " -> " << path[i + 1] << "\n";
cout << "最短路径:" << dis[d] << "\n";
return 0;
}
/* sample 1
8 10 1 8
1 2 1
1 5 1
2 5 1
2 3 1
5 3 1
5 6 1
3 4 1
3 7 1
3 8 1
4 8 1
*/
八数码问题
下面代码实现了N数码问题，不仅仅局限于八数码，但是求解效率有限
#include<bits/stdc++.h>
using namespace std;
using pis = pair<int, string>;
const int N = 500 * 500 + 5;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int n;
template <typename T>
struct Fenwick
{
vector<T> tr;
const int n;
Fenwick(int n): n(n), tr(n) {}
void insert(int x, T d)
{
for(; x < n; x += x & (-x))
tr[x] += d;
}
T sum(int x)
{
T res = 0;
for(; x; x -= x & (-x))
res += tr[x];
return res;
}
T RangeSum(int l, int r)
{
return sum(r) - sum(l - 1);
}
};
int f(string s)
{
int cnt = 0;
for(int i = 0; i < int(s.size()); i++)
if(s[i] != '0')
{
int cur = s[i] - '1';
cnt += abs(cur / n - i / n) + abs(cur % n - i % n);
}
return cnt;
}
void bfs(string start, string end)
{
char op[] = "URDL";
unordered_map<string, int> dis;
unordered_map<string, pair<char, string>> pre;
priority_queue<pis, vector<pis>, greater<pis>> q;
q.push({f(start), start});
dis[start] = 0;
while(!q.empty())
{
auto t = q.top();
q.pop();
string st = t.second;
if(st == end) break;
int x, y;
for(int i = 0; i < int(st.size()); i++)
if(st[i] == '0')
{
x = i / n, y = i % n;
break;
}
for(int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
string t = st;
swap(t[x * n + y], t[nx * n + ny]);
if(!dis.count(t) || dis[st] + 1 < dis[t])
{
dis[t] = dis[st] + 1;
pre[t] = {op[i], st};
q.push({dis[t] + f(t), t});
}
}
}
string move;
vector<string> state;
state.push_back(end);
while(end != start)
{
move += pre[end].first;
end = pre[end].second;
state.push_back(end);
}
reverse(move.begin(), move.end());
reverse(state.begin(), state.end());
for(int i = 0; i < int(move.size()); i++)
{
int cur = 0;
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
cout << (state[i][cur++] - '0') << " \n"[k == n - 1];
cout << "-----------------\n操作:" << move[i] << "\n";
if(i == int(move.size() - 1))
{
int nxt = i + 1;
cur = 0;
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
cout << (state[nxt][cur++] - '0') << " \n"[k == n - 1];
}
}
}
int main()
{
cout << "输入数码阶数:\n";
cin >> n;
vector<int> a(n * n), b(a);
int cur = 0;
cout << "输入初始状态和最终状态:\n";
for(int i = 1; i <= n * n; i++)
{
int x;
cin >> x;
a[cur++] = x;
}
cur = 0;
for(int i = 1; i <= n * n; i++)
{
int x;
cin >> x;
b[cur++] = x;
}
Fenwick<int> tra(n * n + 1), trb(n * n + 1);
int s = 0, d = 0, last = 0, row = -1;
for(int i = 0; i < n * n; i++)
{
if(a[i] == 0)
{
last ++;
row = i / n;
continue;
}
s += (i - last - tra.sum(a[i]));
tra.insert(a[i], 1);
}
last = 0;
for(int i = 0; i < n * n; i++)
{
if(b[i] == 0)
{
last ++;
row -= i / n;
continue;
}
d += (i - last - trb.sum(b[i]));
trb.insert(b[i], 1);
}
cout << s << " " << d << "\n";
if((n & 1 && s % 2 != d % 2) || (n % 2 == 0 && (s + row) % 2 != d % 2))
{
cout << "Can't arrive the state!\n";
return 0;
}
string start, end;
for(int i = 0; i < n * n; i++)
start += (char)(a[i] + '0');
for(int i = 0; i < n * n; i++)
end += (char)(b[i] + '0');
bfs(start, end);
return 0;
}
/* sample
3
2 3 4 1 5 0 7 6 8
1 2 3 4 5 6 7 8 0
2
0 1 3 2
1 2 3 0
4
1 2 3 4 5 7 11 8 9 6 12 15 13 10 14 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0
*/
实验三
A*算法实现15数码问题
和上题代码相同
#include<bits/stdc++.h>
using namespace std;
using pis = pair<int, string>;
const int N = 500 * 500 + 5;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int n;
template <typename T>
struct Fenwick
{
vector<T> tr;
const int n;
Fenwick(int n): n(n), tr(n) {}
void insert(int x, T d)
{
for(; x < n; x += x & (-x))
tr[x] += d;
}
T sum(int x)
{
T res = 0;
for(; x; x -= x & (-x))
res += tr[x];
return res;
}
T RangeSum(int l, int r)
{
return sum(r) - sum(l - 1);
}
};
int f(string s)
{
int cnt = 0;
for(int i = 0; i < int(s.size()); i++)
if(s[i] != '0')
{
int cur = s[i] - '1';
cnt += abs(cur / n - i / n) + abs(cur % n - i % n);
}
return cnt;
}
void bfs(string start, string end)
{
char op[] = "URDL";
unordered_map<string, int> dis;
unordered_map<string, pair<char, string>> pre;
priority_queue<pis, vector<pis>, greater<pis>> q;
q.push({f(start), start});
dis[start] = 0;
while(!q.empty())
{
auto t = q.top();
q.pop();
string st = t.second;
if(st == end) break;
int x, y;
for(int i = 0; i < int(st.size()); i++)
if(st[i] == '0')
{
x = i / n, y = i % n;
break;
}
for(int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
string t = st;
swap(t[x * n + y], t[nx * n + ny]);
if(!dis.count(t) || dis[st] + 1 < dis[t])
{
dis[t] = dis[st] + 1;
pre[t] = {op[i], st};
q.push({dis[t] + f(t), t});
}
}
}
string move;
vector<string> state;
state.push_back(end);
while(end != start)
{
move += pre[end].first;
end = pre[end].second;
state.push_back(end);
}
reverse(move.begin(), move.end());
reverse(state.begin(), state.end());
for(int i = 0; i < int(move.size()); i++)
{
int cur = 0;
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
cout << (state[i][cur++] - '0') << " \n"[k == n - 1];
cout << "-----------------\n操作:" << move[i] << "\n";
if(i == int(move.size() - 1))
{
int nxt = i + 1;
cur = 0;
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
cout << (state[nxt][cur++] - '0') << " \n"[k == n - 1];
}
}
}
int main()
{
cout << "输入数码阶数:\n";
cin >> n;
vector<int> a(n * n), b(a);
int cur = 0;
cout << "输入初始状态和最终状态:\n";
for(int i = 1; i <= n * n; i++)
{
int x;
cin >> x;
a[cur++] = x;
}
cur = 0;
for(int i = 1; i <= n * n; i++)
{
int x;
cin >> x;
b[cur++] = x;
}
Fenwick<int> tra(n * n + 1), trb(n * n + 1);
int s = 0, d = 0, last = 0, row = -1;
for(int i = 0; i < n * n; i++)
{
if(a[i] == 0)
{
last ++;
row = i / n;
continue;
}
s += (i - last - tra.sum(a[i]));
tra.insert(a[i], 1);
}
last = 0;
for(int i = 0; i < n * n; i++)
{
if(b[i] == 0)
{
last ++;
row -= i / n;
continue;
}
d += (i - last - trb.sum(b[i]));
trb.insert(b[i], 1);
}
cout << s << " " << d << "\n";
if((n & 1 && s % 2 != d % 2) || (n % 2 == 0 && (s + row) % 2 != d % 2))
{
cout << "Can't arrive the state!\n";
return 0;
}
string start, end;
for(int i = 0; i < n * n; i++)
start += (char)(a[i] + '0');
for(int i = 0; i < n * n; i++)
end += (char)(b[i] + '0');
bfs(start, end);
return 0;
}
/* sample
4
11 9 4 15 1 3 0 12 7 5 8 6 13 2 10 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0
*/
使用A*算法求解最短路径
自定义路线图，求解最短路径
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
constexpr int inf = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 1e5 + 5, M = N;
constexpr int mod = 1e9 + 7;
constexpr ld eps = 1e-8;
template <class T> void Min(T &a, const T b) { if (a > b) a = b; }
template <class T> void Max(T &a, const T b) { if (a < b) a = b; }
template <class T> void Add(T &a, const T b) { a += b; if(a >= mod) a -= mod; }
template <class T> void Sub(T &a, const T b) { a -= b; if(a < 0) a += mod; }
struct Node
{
int x, y, dis, f;
bool operator < (const Node a) const
{
return dis + f > a.dis + a.f;
}
};
void solve()
{
int n, m;
cin >> n >> m;
int sx, sy, fx, fy;
cin >> sx >> sy >> fx >> fy;
vector<vi> g(n + 1, vi(m + 1));
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> g[i][j];
// 浼颁环鍑芥暟
auto f = [&](int x, int y) -> int { return abs(x - fx) + abs(y - fy); };
priority_queue<Node> q;
vector<vi> vis(n + 1, vi(m + 1));
vector<vector<pii>> pre(n + 1, vector<pii>(m + 1, {-1, -1}));
q.push({sx, sy, 0, f(sx, sy)});
vis[sx][sy] = 1;
int ans = -1;
while(!q.empty())
{
auto t = q.top();
q.pop();
int x = t.x, y = t.y, d = t.dis;
if(x == fx && y == fy)
{
ans = d;
break;
}
for(int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
if(g[nx][ny] || vis[nx][ny]) continue;
vis[nx][ny] = 1;
pre[nx][ny] = {x, y};
q.push({nx, ny, d + 1, f(nx, ny)});
}
}
if(ans == -1)
{
cout << "Can't reach!\n";
return;
}
vector<pii> path;
int tx = fx, ty = fy;
while(pre[tx][ty] != make_pair(-1, -1))
{
path.emplace_back(tx, ty);
auto t = pre[tx][ty];
tx = t.first, ty = t.second;
}
path.emplace_back(sx, sy);
cout << "The shorted distance: " << ans << "\n";
reverse(path.begin(), path.end());
for(int i = 0; i < int(path.size()); i++)
{
auto [x, y] = path[i];
cout << "(" << x << "," << y << ")";
if(i != int(path.size()) - 1) cout << "->";
else cout << "\n";
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
/*
6 6
1 1 6 6
0 0 0 0 0 0
0 1 1 0 0 0
0 1 0 0 0 0
0 0 0 0 1 0
0 1 1 0 1 0
0 0 0 0 0 0
*/
实验四
动物识别系统
下面的代码有些迷，大多数是抄的
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using db = double;
const int ans_l = 25; //从第25个特征开始
const int ans_r = 31; //到第31个特诊为目标结论
const int object_middle_begin = 21; //中间结果起始位置
const int feature_num = 31; //31种特征
const int rule_num = 15; //15条规则
const int rule_pre = 4; //规则中每个结果最多有4个前提条件
string features[feature_num] = {
"有毛发", "产奶", "有羽毛", "会飞", "会下蛋",
"吃肉", "有犬齿", "有爪", "眼盯前方", "有蹄",
"反刍", "黄褐色", "有斑点", "有黑色条纹", "长脖",
"长腿","不会飞","会游泳","黑白二色","善飞",
"哺乳类","鸟类","食肉类","蹄类","金钱豹",
"虎","长颈鹿","斑马","鸵鸟","企鹅","信天翁"
};
int rule_prerequisite[rule_num][rule_pre] = {
{1, 0, 0, 0},
{2, 0, 0, 0},
{3, 0, 0, 0},
{4, 5, 0, 0},
{21, 6, 0, 0},
{7, 8, 9, 0},
{21, 10, 0, 0},
{21, 11, 0, 0},
{23, 12, 13, 0},
{23, 12, 14, 0},
{24, 15, 16, 13},
{24, 14, 0, 0},
{22, 15, 16, 4},
{22, 18, 19, 4},
{22, 20, 0, 0}
};
int rule_result[rule_num] = {21, 21, 22, 22, 23, 23, 24, 24, 25, 26, 27, 28, 29, 30, 31 };
bool backward_reasoning(int num, vi message);
bool inference(int num, vi message) //迭代推理机
{
int ii, ij, ik, im, in;
int hit_num = 0; //输入前提也规则前提重合数
int prerequisite_num; //规则前提数
vi message_c; //迭代前提
int num_c; //迭代前提数量
for (ik = 0; ik < num; ik++) //剪枝函数
{
if (message[ik] >= ans_l && message[ik] <= ans_r)
{
cout << "归并信息：" << features[message[ik] - 1] << "\n";
cout << "推理成功！" << "\n\n";
exit(0);
}
}
for (ii = 0; ii < rule_num; ii++) //遍历规则匹配
{
prerequisite_num = 0;
hit_num = 0;
for (ij = 0; ij < rule_pre; ij++) //计算规则集前提数
{
if (rule_prerequisite[ii][ij] == 0)
break;
prerequisite_num++;
}
for (ij = 0; ij < prerequisite_num; ij++)
{
for (ik = 0; ik < num; ik++)
{
if (rule_prerequisite[ii][ij] == message[ik])
hit_num++;
}
}
if (hit_num == prerequisite_num) //满足某个规则集全部前提
{
bool flag;
for (ik = 0; ik < num; ik++)
{
if (message[ik] == rule_result[ii])
break;
}
if (ik == num)
{
num_c = num - hit_num+1;
flag = true;
}
else
{
num_c = num - hit_num;
flag = false;
}
message_c.resize(num_c);
in = 0;
for (ik = 0; ik < num; ik++)
{
for (im = 0; im < hit_num; im++)
{
if (rule_prerequisite[ii][im] == message[ik])
break;
}
if (im < hit_num)
continue;
message_c[in++] = message[ik];
}
if (flag == true)
message_c[in] = rule_result[ii];
cout << "推导信息：";
for (int iz = 0; iz < num; iz++)
cout << features[message[iz]-1] << " ";
cout << "\n";
return inference(num_c, message_c);
}
}
cout << "归并信息：";
for (int iz = 0; iz < num; iz++)
cout << features[message[iz]-1] << " ";
cout << endl;
backward_reasoning(num,message);
return false;
}
bool backward_reasoning(int num, vi message) //反向推理
{
int ii,ij,ik;
int prerequisite_num = 0;
int hit_num = 0;
vi need_rule_number(rule_num);
vi hit_rule_number(rule_num);
float hit_rule_rate[rule_num];
float best_hit_rule_rate=0;
int best_hit_rule_number;
vi new_message;
for (int i = 0; i < rule_num; i++) //遍历规则匹配
{
prerequisite_num=0;
hit_num=0;
for (int j = 0; j < rule_pre; j++) //计算规则集前提数
{
if (rule_prerequisite[i][j] == 0) break;
prerequisite_num++;
}
need_rule_number[i] = prerequisite_num;
for (int j = 0; j < prerequisite_num; j++) //计算输入信息命中规则集中的前提数
{
for (int k = 0; k < num; k++)
{
if (rule_prerequisite[i][j] == message[k])
hit_num++;
}
}
hit_rule_number[i] = hit_num;
hit_rule_rate[i] = (float)hit_num / prerequisite_num; //命中率
int j;
for(j = 0; j < num; j++)
{
if(message[j] == rule_result[hit_rule_number[i]])
break;
}
if(hit_rule_rate[i] == 1 && j == num)
{
new_message.resize(num + 1);
for(int k = 0; k < num; k++)
new_message[k] = message[k];
new_message[num] = rule_result[hit_rule_number[i]];
num++;
return inference(num,new_message);
}
cout<<"rule "<<setw(2)<<i<<" -> "<<setw(8)<<features[rule_result[i]-1]
<<"命中率："<<hit_rule_rate[i]<<endl;
}
best_hit_rule_number=-1;
for(int i = 0; i < rule_num; i++)
{
if(best_hit_rule_rate < hit_rule_rate[i] && rule_result[i] >= object_middle_begin)
{
best_hit_rule_rate = hit_rule_rate[i];
best_hit_rule_number = i;
}
}
if(best_hit_rule_number == -1)
{
cout << "您输入的信息对本系统无效！按任意键退出...\n\n";
exit(0);
}
cout << "\n";
cout << "best_hit_rule_number=" << best_hit_rule_number << "\n";
cout << "best_hit_rule_rate=" << best_hit_rule_rate << "\n";
cout << "最佳匹配最终结果=" << features[rule_result[best_hit_rule_number] - 1] << "\n";
for(ii = 0; ii < need_rule_number[best_hit_rule_number]; ii++)
{
for(ij = 0; ij < num; ij++)
{
if(rule_prerequisite[best_hit_rule_number][ii] == message[ij])
break;
}
if(ij != num) continue;
else
{
if(rule_prerequisite[best_hit_rule_number][ii]<object_middle_begin)
{
cout<<endl<<"请问您持有的信息是否包含\"";
cout<<features[rule_prerequisite[best_hit_rule_number][ii]-1];
cout<<"\"?(y or n)"<<endl;
char input;
while(true)
{
cin>>input;
if(input=='n')
{
new_message.resize(num);
for(ik=0;ik<num;ik++)
new_message[ik]=message[ik];
break;
}
else if(input=='y')
{
new_message.resize(num + 1);
for(ik=0;ik<num;ik++)
new_message[ik]=message[ik];
new_message[num]=rule_prerequisite[best_hit_rule_number][ii];
num++;
return inference(num,new_message);
}
else cout<<"请重新输入（y or n）！";
}
}
else //询问是否有中间结果rule_prerequisite[best_hit_rule_number][ii]
{
int middle_result=rule_prerequisite[best_hit_rule_number][ii];
for(ii=0;ii<rule_num;ii++)
{
if(rule_result[ii] == middle_result)
{
for(ik = 0; ik < need_rule_number[ii]; ik++)
{
if(rule_prerequisite[ii][ik] >= object_middle_begin-1)
continue;
for(ij = 0; ij < num; ij++)
{
if(rule_prerequisite[ii][ik] == message[ij])
break;
}
if(ij != num) continue;
else
{
cout << "\n请问您持有的信息是否包含\"";
cout << features[rule_prerequisite[ii][ik]-1];
cout << "\"?(y or n)\n";
char input;
while(true)
{
cin >> input;
if(input == 'n') break;
else if(input == 'y')
{
new_message.resize(num + 1);
for(int q = 0; q < num; q++)
new_message[q] = message[q];
new_message[num] = rule_prerequisite[best_hit_rule_number][ii];
num++;
return inference(num, new_message);
}
else cout<<"请重新输入（y or n）！";
}
}
}
}
}
}
}
}
return true;
}
int main()
{
int num;
for(int i = 0; i < feature_num; i++)
{
cout << setiosflags(ios::left);
cout << setw(2) << i + 1 << ":" << setw(10) << features[i] << " ";
if(i % 4 == 3) cout << "\n";
}
cout << "\n\n" << "请输入初始特征个数：" << "\n";
cin >> num;
vector<int> message(num);
cout << "请输入已有信息：" << "\n";
for (int i = 0; i < num; i++)
cin >> message[i];
cout << endl << "初始信息：";
for (int i = 0; i < num; i++)
cout << features[message[i] - 1] << " ";
cout << "\n\n";
if(!inference(num, message))
cout << "你的输入无法得出结果！" << "\n";
return 0;
}
自行设计故障诊断系统
根据上面的代码改的，自己写的不太多
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using db = double;
const int ans_l = 17; //从第25个特征开始
const int ans_r = 22; //到第31个特征为目标结论
const int object_middle_begin = 15; //中间结果起始位置
const int feature_num = 22; //22种特征
const int rule_num = 8; //8条规则
const int rule_pre = 4; //规则中每个结果最多有4个前提条件
/*
前提条件：14
屏幕亮, 屏幕不亮, 键盘指示灯亮, 键盘指示灯不亮, 鼠标指示灯亮, 鼠标指示灯不亮,
电源指示灯亮, 电源指示灯不亮, 充电亮起, 键盘不响应, 鼠标不响应, 画面不响应,
画面花屏, 画面蓝屏
中间结论：2
电源问题, 所有指示灯亮
结论：6
电池没电, 鼠标故障, 键盘故障, 内存过小未响应, 系统程序故障, 显示器故障
规则：
屏幕亮 && 键盘指示灯亮 && 鼠标指示灯亮 && 电源指示灯亮 -> 所有指示灯亮
屏幕不亮 && 键盘指示灯不亮 && 鼠标指示灯不亮 && 电源指示灯不亮 -> 电源问题
电源问题 && 充电亮起 -> 电池没电
键盘指示灯亮 && 键盘不响应 -> 键盘故障
鼠标指示灯不亮 && 鼠标不响应 -> 鼠标故障
画面不响应 && 所有指示灯亮 -> 内存过小未响应
画面花屏 && 所有指示灯亮 -> 显示器故障
所有指示灯亮 && 画面蓝屏 -> 系统程序故障
*/
string features[feature_num] = {
"屏幕亮", "屏幕不亮", "键盘指示灯亮", "键盘指示灯不亮", "鼠标指示灯亮",
"鼠标指示灯不亮", "电源指示灯亮", "电源指示灯不亮", "充电亮起", "键盘不响应",
"鼠标不响应", "画面不响应", "画面花屏", "画面蓝屏", "电源问题",
"所有指示灯亮", "电池没电", "鼠标故障", "键盘故障", "内存过小未响应",
"系统程序故障", "显示器故障"
};
int rule_prerequisite[rule_num][rule_pre] = {
{1, 3, 5, 7},
{2, 4, 6, 8},
{15, 9, 0, 0},
{3, 10, 0, 0},
{6, 11, 0, 0},
{12, 16, 0, 0},
{13, 16, 0, 0},
{14, 16, 0, 0}
};
int rule_result[rule_num] = {16, 15, 17, 19, 18, 20, 22, 21};
bool backward_reasoning(int num, vi message);
bool inference(int num, vi message)
{
int ii, ij, ik, im, in;
int hit_num = 0; //输入前提也规则前提重合数
int prerequisite_num; //规则前提数
vi message_c; //迭代前提
int num_c; //迭代前提数量
for (ik = 0; ik < num; ik++) //剪枝函数
{
if (message[ik] >= ans_l && message[ik] <= ans_r)
{
cout << "归并信息：" << features[message[ik] - 1] << endl;
cout << "推理成功！" << endl<<endl;
exit(0);
}
}
for (ii = 0; ii < rule_num; ii++) //遍历规则匹配
{
prerequisite_num = 0;
hit_num = 0;
for (ij = 0; ij < rule_pre; ij++) //计算规则集前提数
{
if (rule_prerequisite[ii][ij] == 0)
break;
prerequisite_num++;
}
for (ij = 0; ij < prerequisite_num; ij++)
{
for (ik = 0; ik < num; ik++)
{
if (rule_prerequisite[ii][ij] == message[ik])
hit_num++;
}
}
if (hit_num == prerequisite_num) //满足某个规则集全部前提
{
bool flag;
for (ik = 0; ik < num; ik++)
{
if (message[ik] == rule_result[ii])
break;
}
if (ik == num)
{
num_c = num - hit_num+1;
flag = true;
}
else
{
num_c = num - hit_num;
flag = false;
}
message_c.resize(num_c);
in = 0;
for (ik = 0; ik < num; ik++)
{
for (im = 0; im < hit_num; im++)
{
if (rule_prerequisite[ii][im] == message[ik])
break;
}
if (im < hit_num)
continue;
message_c[in++] = message[ik];
}
if (flag == true)
message_c[in] = rule_result[ii];
cout << "推导信息：";
for (int iz = 0; iz < num; iz++)
cout << features[message[iz]-1] << " ";
cout << "\n";
return inference(num_c, message_c);
}
}
cout << "归并信息：";
for (int iz = 0; iz < num; iz++)
cout << features[message[iz]-1] << " ";
cout << endl;
backward_reasoning(num,message);
return false;
}
bool backward_reasoning(int num, vi message) //反向推理
{
int ii,ij,ik;
int prerequisite_num = 0;
int hit_num = 0;
vi need_rule_number(rule_num);
vi hit_rule_number(rule_num);
float hit_rule_rate[rule_num];
float best_hit_rule_rate=0;
int best_hit_rule_number;
vi new_message;
for (int i = 0; i < rule_num; i++) //遍历规则匹配
{
prerequisite_num=0;
hit_num=0;
for (int j = 0; j < rule_pre; j++) //计算规则集前提数
{
if (rule_prerequisite[i][j] == 0) break;
prerequisite_num++;
}
need_rule_number[i] = prerequisite_num;
for (int j = 0; j < prerequisite_num; j++) //计算输入信息命中规则集中的前提数
{
for (int k = 0; k < num; k++)
{
if (rule_prerequisite[i][j] == message[k])
hit_num++;
}
}
hit_rule_number[i] = hit_num;
hit_rule_rate[i] = (float)hit_num / prerequisite_num; //命中率
int j;
for(j = 0; j < num; j++)
{
if(message[j] == rule_result[hit_rule_number[i]])
break;
}
if(hit_rule_rate[i] == 1 && j == num)
{
new_message.resize(num + 1);
for(int k = 0; k < num; k++)
new_message[k] = message[k];
new_message[num] = rule_result[hit_rule_number[i]];
num++;
return inference(num,new_message);
}
cout<<"rule "<<setw(2)<<i<<" -> "<<setw(8)<<features[rule_result[i]-1]
<<"命中率："<<hit_rule_rate[i]<<endl;
}
best_hit_rule_number=-1;
for(int i = 0; i < rule_num; i++)
{
if(best_hit_rule_rate < hit_rule_rate[i] && rule_result[i] >= object_middle_begin)
{
best_hit_rule_rate = hit_rule_rate[i];
best_hit_rule_number = i;
}
}
if(best_hit_rule_number == -1)
{
cout << "您输入的信息对本系统无效！按任意键退出...\n\n";
exit(0);
}
cout << "\n";
cout << "best_hit_rule_number=" << best_hit_rule_number << "\n";
cout << "best_hit_rule_rate=" << best_hit_rule_rate << "\n";
cout << "最佳匹配最终结果=" << features[rule_result[best_hit_rule_number] - 1] << "\n";
for(ii = 0; ii < need_rule_number[best_hit_rule_number]; ii++)
{
for(ij = 0; ij < num; ij++)
{
if(rule_prerequisite[best_hit_rule_number][ii] == message[ij])
break;
}
if(ij != num) continue;
else
{
if(rule_prerequisite[best_hit_rule_number][ii]<object_middle_begin)
{
cout<<endl<<"请问您持有的信息是否包含\"";
cout<<features[rule_prerequisite[best_hit_rule_number][ii]-1];
cout<<"\"?(y or n)"<<endl;
char in;
while(true)
{
cin >> in;
if(in == 'n')
{
new_message.resize(num);
for(ik = 0; ik < num; ik++)
new_message[ik] = message[ik];
break;
}
else if(in == 'y')
{
new_message.resize(num + 1);
for(ik = 0; ik < num; ik++)
new_message[ik] = message[ik];
new_message[num] = rule_prerequisite[best_hit_rule_number][ii];
num++;
return inference(num, new_message);
}
else cout<<"请重新输入（y or n）！";
}
}
else //询问是否有中间结果rule_prerequisite[best_hit_rule_number][ii]
{
int middle_result=rule_prerequisite[best_hit_rule_number][ii];
for(ii=0;ii<rule_num;ii++)
{
if(rule_result[ii] == middle_result)
{
for(ik = 0; ik < need_rule_number[ii]; ik++)
{
if(rule_prerequisite[ii][ik] >= object_middle_begin-1)
continue;
for(ij = 0; ij < num; ij++)
{
if(rule_prerequisite[ii][ik] == message[ij])
break;
}
if(ij != num) continue;
else
{
cout << "\n请问您持有的信息是否包含\"";
cout << features[rule_prerequisite[ii][ik]-1];
cout << "\"?(y or n)\n";
char input;
while(true)
{
cin >> input;
if(input == 'n') break;
else if(input == 'y')
{
new_message.resize(num + 1);
for(int q = 0; q < num; q++)
new_message[q] = message[q];
new_message[num] = rule_prerequisite[best_hit_rule_number][ii];
num++;
return inference(num, new_message);
}
else cout<<"请重新输入（y or n）！";
}
}
}
}
}
}
}
}
return true;
}
int main()
{
int num;
for(int i = 0; i < feature_num; i++)
{
cout << setiosflags(ios::left);
cout << setw(2) << i + 1 << ":" << setw(10) << features[i] << " ";
if(i % 4 == 3) cout << "\n";
}
cout << "\n\n" << "请输入初始特征个数：" << "\n";
cin >> num;
vector<int> message(num);
cout << "请输入已有信息：" << "\n";
for (int i = 0; i < num; i++)
cin >> message[i];
cout << endl << "初始信息：";
for (int i = 0; i < num; i++)
cout << features[message[i] - 1] << " ";
cout << "\n\n";
if(!inference(num, message))
cout << "你的输入无法得出结果！" << "\n";
return 0;
}
实验五
使用遗传算法求解函数最大值
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 20>;
using ld = long double;
using pdd = pair<ld, ld>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
const int person_num = 500;
const ld vary_probability = 0.9;
const int epoch = 10;
const int length = 20;
const int iteration = 25;
vector<arr> init(int tot = 1000, int len = 20)
{
vector<arr> persons;
map<arr, bool> vis;
while((int)persons.size() != tot)
{
arr person;
for(int i = 0; i < 20; i++)
{
int bit = rnd(0, 1);
person[i] = bit;
}
if(!vis[person])
{
persons.push_back(person);
vis[person] = 1;
}
}
return persons;
}
// 将20位的编码转换成x,y的十进制解
pdd decode(arr single)
{
int x = 0, y = 0;
for(int i = 0; i < 10; i++)
x = x * 2 + single[i];
for(int i = 10; i < 20; i++)
y = y * 2 + single[i];
return {10.0 * x / 1024, 10.0 * y / 1024};
}
// 计算x, y对应的函数值
ld calc(arr single)
{
auto [x, y] = decode(single);
ld up = 6.452 * (x + 0.125 * y) *
(cos(x) - cos(2 * y)) * (cos(x) - cos(2 * y));
ld down = sqrt(0.8 + (x - 4.2) * (x - 4.2) + 2 * (y - 7) * (y - 7));
ld ans = up / down + 3.226 * y;
return ans;
}
int choose(vector<ld> val)
{
ld temp = rnd(0, 1000000) / 1000000.0;
vector<ld> val_psum;
ld tot = 0;
for(int i = 0; i < int(val.size()); i++)
tot += val[i];
ld s = 0;
for(int i = 0; i < int(val.size()); i++)
{
s += val[i] / tot;
val_psum.push_back(s);
}
int id = 0;
while(temp > val_psum[id]) id++;
return id;
}
arr cross(arr fa, arr mo)
{
int cross_pos = rnd(0, 19);
// unordered_map<int, int> vis;
arr child;
for(int i = 0; i < cross_pos; i++)
child[i] = fa[i];
for(int i = cross_pos; i < 20; i++)
child[i] = mo[i];
// vis[cross_pos] = 1;
// while(calc(child) < 40.0)
// {
// // printf("Restart cross\n");
// while(vis[cross_pos] && vis.size() < 20)
// cross_pos = rnd(0, 19);
// vis[cross_pos] = 1;
// for(int i = 0; i < cross_pos; i++)
// child[i] = fa[i];
// for(int i = cross_pos; i < 20; i++)
// child[i] = mo[i];
// if((int)vis.size() >= 20)
// {
// child = fa;
// break;
// }
// }
return child;
}
arr vary(arr single)
{
ld probability = (ld)rnd(0, 99) / 100.0;
arr temp = single;
if(probability < vary_probability)
{
int pos = rnd(0, 19);
temp[pos] ^= 1;
if(calc(temp) > calc(single))
return temp;
}
return single;
}
int main()
{
ld max_fval = 0;
arr max_xy;
for(int e = 1; e <= epoch; e++)
{
vector<arr> population = init(person_num, length);
printf("----------------------The %d th epoch--------------------\n", e);
for(int iter = 1; iter <= iteration; iter++)
{
printf("The %d th generation\n", iter);
vector<arr> temp_population;
vector<ld> val;
for(int i = 0; i < int(population.size()); i++)
val.push_back(calc(population[i]));
int mx_id = max_element(val.begin(), val.end()) - val.begin();
temp_population.push_back(population[mx_id]);
for(int i = 1; i <= person_num; i++)
{
int fa_id = choose(val);
int mo_id = choose(val);
arr child = cross(population[fa_id], population[mo_id]);
child = vary(child);
temp_population.push_back(child);
}
population = temp_population;
ld mx = 0;
for(int i = 0; i < int(population.size()); i++)
{
ld tval = calc(population[i]);
mx = max(mx, tval);
if(tval > max_fval)
{
max_xy = population[i];
max_fval = tval;
}
}
printf("The %d th Max f(x, y): %.6Lf\n", iter, mx);
}
}
pdd t = decode(max_xy);
printf("x = %.6Lf , y = %.6Lf\n", t.first, t.second);
printf("%.6Lf", max_fval);
return 0;
}
使用遗传算法求解旅行商问题
我的图是二维的表格形式，故代码简化了一部分
/*
10
1 1
1 4
1 6
1 8
3 8
5 1
8 1
8 2
8 4
8 8
*/
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
using pii = pair<int, int>;
using ld = long double;
using ll = long long;
const int epoch = 50;
const int person_num = 100;
const ld vary_probability = 0.3;
const int iteration = 20;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
vector<vector<ld>> d;
ld dis(pii a, pii b)
{
return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) +
1.0 * (a.y - b.y) * (a.y - b.y));
}
vector<vector<int>> init(int tot, int len)
{
vector<vector<int>> persons;
map<vector<int>, bool> vis;
vector<int> person(len);
iota(person.begin(), person.end(), 0);
while(int(persons.size()) != tot)
{
// random_shuffle(person.begin(), person.end());
shuffle(person.begin(), person.end(), rng);
if(!vis[person])
{
persons.emplace_back(person);
vis[person] = 1;
}
}
return persons;
}
ld calc(vector<int> person)
{
ld sum = 0;
int n = person.size();
for(int i = 0; i < n; i++)
{
int p = (i - 1 + n) % n;
sum += d[person[p]][person[i]];
}
return sum;
}
int choose(vector<ld> val)
{
ld temp = rnd(0, 100000) / 100000.0;
vector<ld> val_psum;
ld tot = 0;
for(int i = 0; i < int(val.size()); i++)
{
val[i] = 1.0 / val[i];
tot += val[i];
}
ld s = 0;
for(int i = 0; i < int(val.size()); i++)
{
s += val[i] / tot;
val_psum.emplace_back(s);
}
int id = 0;
while(temp > val_psum[id] && id < int(val_psum.size())) id++;
return id;
}
vector<int> cross(vector<int> fa, vector<int> mo)
{
int l = rnd(0, int(fa.size()) - 1);
int r = rnd(0, int(fa.size()) - 1);
pii t = minmax(l, r);
l = t.x, r = t.y;
// 3 5 6 [7 1 2] 4 0
// 3 1 0 [5 4 7] 6 2
vector<int> conflict, p1(fa.size(), -1), p2(p1), child(fa.size());
vector<bool> vis1(fa.size()), vis2(vis1);
for(int i = 0; i < int(fa.size()); i++)
{
child[i] = fa[i];
p1[fa[i]] = i;
}
for(int i = l; i <= r; i++)
vis1[fa[i]] = vis2[mo[i]] = 1;
for(int i = l; i <= r; i++)
{
child[i] = mo[i];
p2[mo[i]] = i;
if(!vis1[mo[i]])
conflict.emplace_back(mo[i]);
}
for(int i = 0; i < int(conflict.size()); i++)
{
int id = p1[conflict[i]];
while(vis2[child[id]])
child[id] = fa[p2[child[id]]];
}
// for(int i = 0; i < int(child.size()); i++)
// cout << child[i] << " \n"[i == int(child.size()) - 1];
return child;
}
vector<int> mutation(vector<int> person)
{
ld prob = (ld)rnd(0, 99) / 100.0;
vector<int> temp = person;
if(prob < vary_probability)
{
int l = rnd(0, person.size() - 1), r = rnd(0, person.size() - 1);
if(l != r) swap(temp[l], temp[r]);
if(calc(temp) > calc(person))
return temp;
}
return person;
}
int main()
{
// freopen("1.txt", "r", stdin);
// printf("Please output the number of cities:");
int n;
scanf("%d", &n);
vector<int> path;
ld min_path = 1e9;
vector<pii> cities(n);
for(int i = 0; i < n; i++)
scanf("%d%d", &cities[i].x, &cities[i].y);
d.resize(n, vector<ld>(n));
for(int i = 0; i < n; i++)
for(int j = i; j < n; j++)
d[i][j] = d[j][i] = dis(cities[i], cities[j]);
for(int e = 1; e <= epoch; e++)
{
vector<vector<int>> population = init(person_num, n);
for(int iter = 1; iter <= iteration; iter++)
{
// printf("The %d th generation\n", iter);
vector<vector<int>> temp_population;
vector<ld> val(population.size());
for(int i = 0; i < int(population.size()); i++)
val[i] = calc(population[i]);
int mn_id = min_element(val.begin(), val.end()) - val.begin();
// 上一代最优种群保留到下一代
temp_population.emplace_back(population[mn_id]);
vector<int> child;
for(int i = 1; i < person_num; i++)
{
int fa_id = choose(val);
int mo_id = choose(val);
while(fa_id == mo_id)
mo_id = choose(val);
child = cross(population[fa_id], population[mo_id]);
assert(child.size() > 0);
child = mutation(child);
temp_population.emplace_back(child);
}
population = temp_population;
ld mn = 1e9;
for(int i = 0; i < int(population.size()); i++)
{
ld tval = calc(population[i]);
mn = min(mn, tval);
if(tval < min_path)
{
path = population[i];
min_path = tval;
}
}
// printf("The %d th min path distance: %.6Lf\n", iter, mn);
}
printf("The %d th epoch min distance: %.6Lf\n", e, min_path);
}
printf("The path is:\n");
for(int i = 0; i < int(path.size()); i++)
cout << path[i] << " \n"[i == int(path.size()) - 1];
printf("The min distance: %.6Lf\n", min_path);
return 0;
}
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
3
0- 0
已为社区贡献2条内容
所有评论(0)