人工智能及其应用 实验课 源代码_人工智能免费源代码

实验一

梵塔问题

#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;
}

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

传教士野人渡河问题

#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;
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

实验二

宽度优先和深度优先求解路径

#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
*/
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

八数码问题

下面代码实现了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
*/
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

实验三

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
*/
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

使用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
*/
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

实验四

动物识别系统

下面的代码有些迷，大多数是抄的

#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;
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303

自行设计故障诊断系统

根据上面的代码改的，自己写的不太多

#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;
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318

实验五

使用遗传算法求解函数最大值

#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;
}


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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

使用遗传算法求解旅行商问题

我的图是二维的表格形式，故代码简化了一部分

/*
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;
}

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228