~cytrogen/blog-public

blog-public/posts/d235.html -rw-r--r-- 123.3 KiB
88eebf3d — Cytrogen Deploy 2026-02-19 08:34:27 4 days ago 
                                                                                
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
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
<!DOCTYPE html><html lang="zh" data-theme="dark"><head><meta charset="utf-8"><meta name="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1"><title>CS50AI Python 笔记 · Cytrogen 的个人博客</title><meta name="description" content="仅作个人用途。CS50AI 课程的笔记。"><link rel="icon" href="../favicon.png"><link rel="canonical" href="https://cytrogen.icu/posts/d235.html"><link rel="webmention" href="https://webmention.io/cytrogen.icu/webmention"><link rel="me" href="https://m.otter.homes/@Cytrogen"><link rel="me" href="https://github.com/cytrogen"><meta name="fediverse:creator" content="@Cytrogen@m.otter.homes"><link rel="preload" href="../fonts/opensans-regular-latin.woff2" as="font" type="font/woff2" crossorigin="anonymous"><style>@font-face {
  font-family: 'Open Sans';
  src: url('../fonts/opensans-regular-latin.woff2') format('woff2');
  font-weight: 400;
  font-style: normal;
  font-display: swap;
  unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02BB-02BC, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2122, U+2191, U+2193, U+2212, U+2215, U+FEFF, U+FFFD;
  size-adjust: 107%;
  ascent-override: 97%;
  descent-override: 25%;
  line-gap-override: 0%;
}
</style><script>(function() {
  try {
    // 优先级：用户选择 > 系统偏好 > 默认浅色
    const saved = localStorage.getItem('theme');
    const theme = saved || 
      (window.matchMedia && window.matchMedia('(prefers-color-scheme: dark)').matches ? 'dark' : 'light');
    
    document.documentElement.setAttribute('data-theme', theme);
    document.documentElement.style.colorScheme = theme;
  } catch (error) {
    // 失败时使用默认主题，不阻塞渲染
    document.documentElement.setAttribute('data-theme', 'light');
  }
})();
</script><link rel="stylesheet" href="../css/ares.css"><script data-netlify-skip-bundle="true">(function() {
  document.addEventListener('DOMContentLoaded', function() {
    const theme = document.documentElement.getAttribute('data-theme');
    const pageWrapper = document.getElementById('page-wrapper');
    if (pageWrapper && theme) {
      pageWrapper.setAttribute('data-theme', theme);
    }
  });
})();

</script><!-- hexo injector head_end start -->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.css">

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hexo-math@4.0.0/dist/style.css">
<!-- hexo injector head_end end --><meta name="generator" content="Hexo 8.1.1"><link rel="alternate" href="atom.xml" title="Cytrogen 的个人博客" type="application/atom+xml">
</head><body><div id="page-wrapper"><a class="skip-link" href="#main-content">跳到主要内容</a><div class="wrap"><header><a class="logo-link" href="../index.html"><img src="../favicon.png" alt="logo"></a><div class="h-card visually-hidden"><img class="u-photo" src="https://cytrogen.icu/favicon.png" alt="Cytrogen"><a class="p-name u-url u-uid" href="https://cytrogen.icu">Cytrogen</a><p class="p-note">Cytrogen 的个人博客，Cytrogen's Blog</p><a class="u-url" rel="me noopener" target="_blank" href="https://m.otter.homes/@Cytrogen">Mastodon</a><a class="u-url" rel="me noopener" target="_blank" href="https://github.com/cytrogen">GitHub</a></div><nav class="site-nav"><div class="nav-main"><div class="nav-primary"><ul class="nav-list hidden-mobile"><li class="nav-item"><a class="nav-link" href="../index.html">首页</a></li></ul><div class="nav-tools"><div class="language-menu"><button class="language-toggle" type="button"><svg class="icon icon-globe" width="16" height="16" viewBox="0 0 16 16" fill="currentColor" aria-hidden="true" focusable="false"><path d="M0 8a8 8 0 1 1 16 0A8 8 0 0 1 0 8zm7.5-6.923c-.67.204-1.335.82-1.887 1.855A7.97 7.97 0 0 0 5.145 4H7.5V1.077zM4.09 4a9.267 9.267 0 0 1 .64-1.539 6.7 6.7 0 0 1 .597-.933A7.025 7.025 0 0 0 2.255 4H4.09zm-.582 3.5c.03-.877.138-1.718.312-2.5H1.674a6.958 6.958 0 0 0-.656 2.5h2.49zM4.847 5a12.5 12.5 0 0 0-.338 2.5H7.5V5H4.847zM8.5 5v2.5h2.99a12.495 12.495 0 0 0-.337-2.5H8.5zM4.51 8.5a12.5 12.5 0 0 0 .337 2.5H7.5V8.5H4.51zm3.99 0V11h2.653c.187-.765.306-1.608.338-2.5H8.5zM5.145 12c.138.386.295.744.468 1.068.552 1.035 1.218 1.65 1.887 1.855V12H5.145zm.182 2.472a6.696 6.696 0 0 1-.597-.933A9.268 9.268 0 0 1 4.09 12H2.255a7.024 7.024 0 0 0 3.072 2.472zM3.82 11a13.652 13.652 0 0 1-.312-2.5h-2.49c.062.89.291 1.733.656 2.5H3.82zm6.853 3.472A7.024 7.024 0 0 0 13.745 12H11.91a9.27 9.27 0 0 1-.64 1.539 6.688 6.688 0 0 1-.597.933zM8.5 12v2.923c.67-.204 1.335-.82 1.887-1.855A7.97 7.97 0 0 0 10.855 12H8.5zm3.68-1h2.146c.365-.767.594-1.61.656-2.5h-2.49a13.65 13.65 0 0 1-.312 2.5zm2.802-3.5a6.959 6.959 0 0 0-.656-2.5H12.18c.174.782.282 1.623.312 2.5h2.49zM11.27 2.461c.247.464.462.98.64 1.539h1.835a7.024 7.024 0 0 0-3.072-2.472c.218.284.418.598.597.933zM10.855 4a7.966 7.966 0 0 0-.468-1.068C9.835 1.897 9.17 1.282 8.5 1.077V4h2.355z"></path></svg><span>中文</span></button><div class="language-dropdown"></div></div></div><div class="nav-controls"><div class="more-menu hidden-mobile"><button class="more-toggle" type="button"><span>更多</span><svg class="icon icon-chevron-down" width="12" height="12" viewBox="0 0 12 12" fill="currentColor" aria-hidden="true" focusable="false"><path d="M6 8.825c-.2 0-.4-.1-.5-.2l-3.3-3.3c-.3-.3-.3-.8 0-1.1s.8-.3 1.1 0l2.7 2.7 2.7-2.7c.3-.3.8-.3 1.1 0s.3.8 0 1.1l-3.3 3.3c-.1.1-.3.2-.5.2z"></path></svg></button><div class="more-dropdown"><ul class="dropdown-list"><li class="dropdown-item"><a class="nav-link" href="../archives/index.html">归档</a></li><li class="dropdown-item"><a class="nav-link" href="../categories/index.html">分类</a></li><li class="dropdown-item"><a class="nav-link" href="../tags/index.html">标签</a></li><li class="dropdown-item"><a class="nav-link" href="../about/index.html">关于</a></li><li class="dropdown-item"><a class="nav-link" href="../sitemap/index.html">领地地图</a></li></ul></div></div><div class="theme-switcher"><button class="theme-toggle" type="button" role="switch" aria-pressed="false" aria-label="切换主题"><div class="theme-icon moon-icon"><svg class="icon icon-moon" width="16" height="16" viewBox="0 0 16 16" fill="currentColor" aria-hidden="true" focusable="false"><path d="M6 .278a.768.768 0 0 1 .08.858 7.208 7.208 0 0 0-.878 3.46c0 4.021 3.278 7.277 7.318 7.277.527 0 1.04-.055 1.533-.16a.787.787 0 0 1 .81.316.733.733 0 0 1-.031.893A8.349 8.349 0 0 1 8.344 16C3.734 16 0 12.286 0 7.71 0 4.266 2.114 1.312 5.124.06A.752.752 0 0 1 6 .278z"></path></svg></div><div class="theme-icon sun-icon"><svg class="icon icon-sun" width="16" height="16" viewBox="0 0 16 16" fill="currentColor" aria-hidden="true" focusable="false"><path d="M8 11a3 3 0 1 1 0-6 3 3 0 0 1 0 6zm0 1a4 4 0 1 0 0-8 4 4 0 0 0 0 8zM8 0a.5.5 0 0 1 .5.5v2a.5.5 0 0 1-1 0v-2A.5.5 0 0 1 8 0zm0 13a.5.5 0 0 1 .5.5v2a.5.5 0 0 1-1 0v-2A.5.5 0 0 1 8 13zm8-5a.5.5 0 0 1-.5.5h-2a.5.5 0 0 1 0-1h2a.5.5 0 0 1 .5.5zM3 8a.5.5 0 0 1-.5.5h-2a.5.5 0 0 1 0-1h2A.5.5 0 0 1 3 8zm10.657-5.657a.5.5 0 0 1 0 .707l-1.414 1.415a.5.5 0 1 1-.707-.708l1.414-1.414a.5.5 0 0 1 .707 0zm-9.193 9.193a.5.5 0 0 1 0 .707L3.05 13.657a.5.5 0 0 1-.707-.707l1.414-1.414a.5.5 0 0 1 .707 0zm9.193 2.121a.5.5 0 0 1-.707 0l-1.414-1.414a.5.5 0 0 1 .707-.707l1.414 1.414a.5.5 0 0 1 0 .707zM4.464 4.465a.5.5 0 0 1-.707 0L2.343 3.05a.5.5 0 1 1 .707-.707l1.414 1.414a.5.5 0 0 1 0 .708z"></path></svg></div></button></div><details class="mobile-menu-details hidden-desktop"><summary class="hamburger-menu" aria-label="nav.menu"><svg class="icon icon-bars" width="16" height="16" viewBox="0 0 16 16" fill="currentColor" aria-hidden="true" focusable="false"><path d="M2.5 12a.5.5 0 0 1 .5-.5h10a.5.5 0 0 1 0 1H3a.5.5 0 0 1-.5-.5zm0-4a.5.5 0 0 1 .5-.5h10a.5.5 0 0 1 0 1H3a.5.5 0 0 1-.5-.5zm0-4a.5.5 0 0 1 .5-.5h10a.5.5 0 0 1 0 1H3a.5.5 0 0 1-.5-.5z"></path></svg><span class="menu-text">nav.menu</span></summary><div class="mobile-menu-dropdown"><ul class="mobile-nav-list"><li class="mobile-nav-item"><a class="mobile-nav-link" href="../index.html">首页</a></li><li class="mobile-nav-item"><a class="mobile-nav-link" href="../archives/index.html">归档</a></li><li class="mobile-nav-item"><a class="mobile-nav-link" href="../categories/index.html">分类</a></li><li class="mobile-nav-item"><a class="mobile-nav-link" href="../tags/index.html">标签</a></li><li class="mobile-nav-item"><a class="mobile-nav-link" href="../about/index.html">关于</a></li><li class="mobile-nav-item"><a class="mobile-nav-link" href="../sitemap/index.html">领地地图</a></li></ul></div></details></div></div></div></nav></header><main class="container" id="main-content" tabindex="-1"><div class="post"><article class="post-block h-entry"><div class="post-meta p-author h-card visually-hidden"><img class="author-avatar u-photo" src="../favicon.png" alt="Cytrogen"><span class="p-name">Cytrogen</span><a class="u-url" href="https://cytrogen.icu">https://cytrogen.icu</a></div><a class="post-permalink u-url u-uid visually-hidden" href="https://cytrogen.icu/posts/d235.html">永久链接</a><div class="p-summary visually-hidden"><p>仅作个人用途。CS50AI 课程的笔记。</p></div><div class="visually-hidden"><a class="p-category" href="../categories/%E7%BC%96%E7%A8%8B%E7%AC%94%E8%AE%B0/">编程笔记</a><a class="p-category" href="../tags/Python/">Python</a><a class="p-category" href="../tags/CS50/">CS50</a></div><h1 class="post-title p-name">CS50AI Python 笔记</h1><div class="post-info"><time class="post-date dt-published" datetime="2023-09-05T14:00:00.000Z">9/5/2023</time><time class="dt-updated visually-hidden" datetime="2026-02-09T17:16:54.681Z"></time></div><div class="post-content e-content"><html><head></head><body><p>仅作个人用途。CS50AI 课程的笔记。</p>
<span id="more"></span>
<h1 id="0-search"><a class="markdownIt-Anchor" href="#0-search"></a> 0. Search</h1>
<p>什么能够制造 AI：</p>
<ol>
<li>搜索：寻找问题的解决方案</li>
<li>知识：展示信息和相关知识</li>
<li>不确定性：使用概率来解决不确定的事件</li>
<li>优化：不单是找到解决问题的正确方案，而是找到更好更棒的解决方案</li>
<li>学习：基于对数据和经验的获取而提高性能</li>
<li>神经网络：一种受人脑启发的程序结构，能够有效地执行任务</li>
<li>语言：处理由人类产生和理解的自然语言</li>
</ol>
<h2 id="搜索"><a class="markdownIt-Anchor" href="#搜索"></a> 搜索</h2>
<p>搜索问题设计了一个代理，它：</p>
<ul>
<li>被赋予一个初始状态</li>
<li>被赋予一个目标状态</li>
<li>返回一个如何从前者到后者的解决方案</li>
</ul>
<h2 id="解决搜索问题"><a class="markdownIt-Anchor" href="#解决搜索问题"></a> 解决搜索问题</h2>
<p>解决方案是从初始状态到目标状态的一连串行动。</p>
<p>而最佳解决方案，是一个在所有解决方案中具有最低路径成本的解决方案。</p>
<p>在搜索过程中，数据通常被存储在一个节点（node）中。节点是一个数据结构，包含：</p>
<ul>
<li>
<p>一个状态</p>
</li>
<li>
<p>父节点</p>
</li>
<li>
<p>应用于父节点状态的行动，以达到当前节点的目的</p>
</li>
<li>
<p>从初始状态到这个节点的路径成本</p>
</li>
</ul>
<p>节点包含的信息对搜索算法的目的很有用。不过节点仅持有信息。为了实际搜索，我们使用前沿（frontier），即管理节点的机制。</p>
<p>前沿开始时包含一个初始状态和一个空的已探索集合，然后重复直到达到一个解决方案：</p>
<ol>
<li>
<p>如果前沿是空的：</p>
<ul>
<li>停止。这个问题没有解决方案</li>
</ul>
</li>
<li>
<p>从前沿中移除一个节点，该节点会被考虑</p>
</li>
<li>
<p>如果节点持有目标状态：</p>
<ul>
<li>返回解决方案。停止</li>
</ul>
<p>否则：</p>
<ol>
<li>扩展节点（找到所有可以从这个节点到达的新节点）</li>
<li>将产生的节点添加到前沿</li>
<li>将当前节点添加到已探索集合中</li>
</ol>
</li>
</ol>
<p>上述没有提到哪个节点应该被移除。这个选择对解决方案的质量和实现的速度都有影响。有多种方法可以解决哪些节点应该被首先考虑：</p>
<ol>
<li>堆栈/深度优先搜索（stack/depth-first search）</li>
</ol>
<ul>
<li>在尝试另一个方向之前会穷尽每一个方向</li>
<li>前沿被作为一个堆栈数据结构来管理</li>
<li>「后进先出」</li>
<li>当节点被添加到前沿之后，第一个要移除和考虑的节点是最后被添加的节点</li>
<li>在第一个方向上尽可能地深入，而把所有其他方向留给以后</li>
</ul>
<blockquote>
<p>例子：你在寻找钥匙</p>
<ol>
<li>选择从裤子开始搜索</li>
<li>先翻遍每一个口袋</li>
<li>当裤子的每个口袋里都找完了，再停止对裤子的搜索</li>
<li>搜索其他地方</li>
</ol>
</blockquote>
<p>优点：</p>
<ul>
<li>在最好的情况下，速度最快</li>
</ul>
<p>缺点：</p>
<ul>
<li>找到的解决方案有可能并不是最优的</li>
<li>在最坏的情况下，可能在找到解决方案之前就探索了所有可能的路径，导致花费了更长的时间</li>
</ul>
  <figure class="highlight python"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">remove</span>(<span class="params">self</span>):</span><br><span class="line">    <span class="keyword">if</span> <span class="variable language_">self</span>.empty():</span><br><span class="line">        <span class="comment"># 如果前沿是空的，终止搜索</span></span><br><span class="line">        <span class="keyword">raise</span> Exception(<span class="string">"空前沿"</span>)</span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="comment"># 保存最新添加的节点</span></span><br><span class="line">        node = <span class="variable language_">self</span>.frontier[-<span class="number">1</span>]</span><br><span class="line">        <span class="comment"># 从前沿里移除最新添加的节点</span></span><br><span class="line">        <span class="variable language_">self</span>.frontier = <span class="variable language_">self</span>.frontier[:-<span class="number">1</span>]</span><br><span class="line">        <span class="keyword">return</span> node</span><br></pre></td></tr></tbody></table></figure>
<ol start="2">
<li>队列/广度优先搜索（queue/breadth-first search）</li>
</ol>
<ul>
<li>
<p>同时遵循多个方向</p>
</li>
<li>
<p>在每个可能的方向上走一步，然后在每个方向上走第二步</p>
</li>
<li>
<p>前沿被作为一个队列数据结构来管理</p>
</li>
<li>
<p>「先进先出」</p>
</li>
<li>
<p>所有的新节点都是排队增加的</p>
</li>
<li>
<p>节点被考虑的依据是哪一个先被添加</p>
</li>
</ul>
<blockquote>
<p>例子：你又在找钥匙</p>
<ol>
<li>从裤子开始搜索</li>
<li>从裤子右边口袋里寻找</li>
<li>在抽屉里看一看</li>
<li>在桌子上看</li>
<li>用尽了所有的位置之后，回到裤子，寻找下一个口袋</li>
</ol>
</blockquote>
<p>优点：</p>
<ul>
<li>保证能找到最优解</li>
</ul>
<p>缺点：</p>
<ul>
<li>运行的时间比最小时间长</li>
<li>在最坏的情况下，这个算法需要尽可能长的时间来运行</li>
</ul>
  <figure class="highlight python"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">remove</span>(<span class="params">self</span>):</span><br><span class="line">    <span class="keyword">if</span> <span class="variable language_">self</span>.empty():</span><br><span class="line">        <span class="comment"># 如果前沿为空，终止搜索</span></span><br><span class="line">        <span class="keyword">raise</span> Exception(<span class="string">'空前沿'</span>)</span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="comment"># 保存第一个被添加的节点</span></span><br><span class="line">        node = <span class="variable language_">self</span>.frontier[<span class="number">0</span>]</span><br><span class="line">        <span class="comment"># 从前沿中移除第一个节点</span></span><br><span class="line">        <span class="variable language_">self</span>.frontier = <span class="variable language_">self</span>.frontier[<span class="number">1</span>:]</span><br><span class="line">        <span class="keyword">return</span> node</span><br></pre></td></tr></tbody></table></figure>
<ol start="3">
<li>
<p>贪婪的最佳优先搜索（greedy best-first search）</p>
<p>广度优先和深度优先都是无信息的搜索算法。这些算法不利用任何它们没有通过自己的探索而获得的关于问题的知识。然而，关于问题的一些知识实际上是可用且常用的。</p>
<ul>
<li>扩展了最接近目标的节点</li>
<li>该行为由启发式函数（heuristic function）决定</li>
<li>函数估计下一个节点离目标有多近，但可能是错误的</li>
</ul>
</li>
<li>
<p>A* 搜索（A* search）</p>
<p>作为贪婪的最佳优先算法的发展，A* 搜索不仅考虑了启发式函数 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>h</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">h(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">h</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，还考虑了直到当前位置的累计成本 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>g</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">g(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.03588em;">g</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>。结合这两个值，该算法确定解决方案的成本更精准，还会优化其在路上的选择。</p>
<p>该算法会一直跟踪 <code>到现在位置的路径成本 + 到目标的估计成本</code>。一旦超过之前某个选项的估计成本，该算法就会抛弃当前的路径，回到之前的选项，从而避免自己走一条被 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>h</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">h(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">h</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span> 错误地标记为最佳、实际为漫长且低效的路径。</p>
<p>这个算法也依赖着启发式。某些情况下，效率要比贪婪的最佳优先搜索低，甚至低于无信息的算法。为了使 A* 搜索成为最优，启发式函数应该是：</p>
<ul>
<li>
<p>可接受的 / 永远不会高估真实成本</p>
</li>
<li>
<p>一致性</p>
</li>
<li>
<p><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>h</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>&lt;</mo><mo>=</mo><mi>h</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mo mathvariant="normal" lspace="0em" rspace="0em">′</mo></msup><mo stretchy="false">)</mo><mo>+</mo><mi>c</mi></mrow><annotation encoding="application/x-tex">h(n) &lt;= h(n') + c</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal">h</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">&lt;</span></span><span class="base"><span class="strut" style="height:0.36687em;vertical-align:0em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.001892em;vertical-align:-0.25em;"></span><span class="mord mathnormal">h</span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.751892em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">′</span></span></span></span></span></span></span></span></span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord mathnormal">c</span></span></span></span></p>
</li>
</ul>
</li>
<li>
<p>对抗性搜索（adversarial search）</p>
<p>该搜索中，算法面临着一个试图实现相反目标的对手。例如井字棋。</p>
<ol>
<li>
<p>极小化极大（minimax）</p>
<p>对抗性搜索中的一种算法：</p>
<ul>
<li>将一方的获胜条件表示为 <code>-1</code>，另一方的获胜条件为 <code>+1</code></li>
<li>进一步的行动将由这些条件驱动</li>
</ul>
<blockquote>
<p>井字棋 AI：</p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>s</mi><mn>0</mn></msub></mrow><annotation encoding="application/x-tex">s_0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">s</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">0</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> 代表初始状态（一个空的 3x3 棋盘）</li>
<li><code>Players(s)</code>：参数 <code>s</code> 是一个状态；返回哪个玩家的回合（X 或者 O）</li>
<li><code>Actions(s)</code>：参数 <code>s</code> 是一个状态；返回当前状态所有有效的移动（棋盘上哪些格子是空闲的）</li>
<li><code>Results(s,a)</code>：参数 <code>s</code> 和 <code>a</code> 分别是一个状态和一个行动；返回一个全新的状态（在状态 <code>s</code> 上执行行动 <code>a</code> 后的棋盘）</li>
<li><code>Terminal(s)</code>：参数 <code>s</code> 是一个状态；检查是否是棋盘中最后一次行动（是否有人胜出或平局）；如果游戏结束返回 <code>True</code>，反之返回 <code>False</code></li>
<li><code>Utility(s)</code>：参数 <code>s</code> 是一个临终状态；返回该状态的效用值：<code>-1</code>、<code>0</code>、<code>1</code></li>
</ul>
</blockquote>
<p><img src="/posts/d235/Minimax_Tictactoe.png" alt="Minimax in Tic Tac Toe"></p>
<ol>
<li>根据状态（本回合轮到谁），该算法可以知道当前的玩家在进行优化游戏时是否会选择导致了一个较低 / 较高数值的状态的行动</li>
<li>在最小化和最大化之间交替进行</li>
<li>为每个可能的行动所导致的状态创造值</li>
</ol>
 <figure class="highlight plaintext"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">Function Max-Value(state):</span><br><span class="line">v = -∞</span><br><span class="line">if Terminal(state):</span><br><span class="line">	return Utility(state)</span><br><span class="line">for action in Actions(state):</span><br><span class="line">	v = Max(v,Min-Value(Result(state,action)))</span><br><span class="line">	return v</span><br><span class="line"></span><br><span class="line">      Function Min-Value(state):</span><br><span class="line">          v = ∞</span><br><span class="line">          if Terminal(state):</span><br><span class="line">              return Utility(state)</span><br><span class="line">          for action in Actions(state):</span><br><span class="line">              v = Min(v,Max-Value(Result(state,action)))</span><br><span class="line">              return v</span><br></pre></td></tr></tbody></table></figure>
</li>
<li>
<p>Alpha-beta 剪枝（alpha-beta pruning）</p>
</li>
</ol>
<p>作为优化极小化极大的一种方式，Alpha-beta 剪枝跳过了一些明显不利的递归计算。</p>
<p>在确定了一个行动的值后，如果有初步证据表明之后的行动可以使对手得到比已经确定的行动更好的分数，那么就没有必要进一步研究这个行动，因为它将决定性地比之前确定的行动更不利。</p>
<blockquote>
<p>例子：</p>
<p>一个最大化的棋手知道：在下一步，最小化的棋手将试图达到最低分数。</p>
<p>假设最大化的棋手有三个可能的行动，第一个行动的值为 4。为此，如果当前棋手实施了该行动，棋手会生成最小化者的行动值，因为他知道最小化者会选择最低的行动。</p>
<p>然而，在完成对最小化者的所有可能行动的计算之前，棋手看到其中一个选项的值为 3。这意味着对于最小化者来说，没有理由继续探索其他可能的行动。尚未取值的行动的值并不重要，无论是 10 还是 - 10。</p>
<p>如果值是 10，最小化者就会选择最低的选项，也就是 3，这已经比预先确定的 4 更糟糕。因此，此时计算最小化者的额外可能行动与最大化者无关，因为最大化者已经有一个明确的更好的选择，即 4。</p>
</blockquote>
<ol start="3">
<li>深度有限的极小化极大（depth-limited minimax）</li>
</ol>
<p>井字棋一共有 255168 个可能，而国际象棋有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><msup><mn>0</mn><mn>290</mn></msup></mrow><annotation encoding="application/x-tex">10^{290}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span><span class="mord mtight">9</span><span class="mord mtight">0</span></span></span></span></span></span></span></span></span></span></span></span> 个可能。到目前为止，极小化极大算法要求生成从某一点到目标条件的所有假设。虽然计算所有的井字棋游戏假设对现代计算机来说并不困难，但如果在国际象棋里呢？</p>
<p>深度限制的极小化极大在停止前只考虑先定义的棋步数，而不去考虑临终状态。然而这并不允许为每个行动获取一个精确的数值，因为假想游戏的终点还未达到。</p>
<p>为了处理这个问题，深度有限的极小化极大依赖于一个评估函数，该函数估计了从给定状态开始的游戏的预期效用，或者换句话说，为状态赋值。</p>
<blockquote>
<p>例子：</p>
<p>在国际象棋中，一个效用函数将棋盘的当前配置作为输入，试图评估其预期效用（基于每个玩家拥有的棋子和它们在棋盘上的位置），然后返回一个正值或负值，代表棋盘对一个玩家与另一个玩家的有利程度。</p>
<p>这些值可以用来决定正确的行动。评估函数越好，依赖它的极小化极大算法就越好。</p>
</blockquote>
</li>
</ol>
<h2 id="作业degrees"><a class="markdownIt-Anchor" href="#作业degrees"></a> 作业 Degrees</h2>
<blockquote>
<p>根据 Six Degrees of Kevin Bacon 游戏，好莱坞电影界的任何人都可以在 6 个步骤内与 Kevin Bacon 联系起来，其中每个步骤都包括找到两个演员都出演的电影。</p>
<p>问题：通过选择一连串的电影，找到任何两个演员之间的最短路径。</p>
<blockquote>
<p>例子：Jennifer Lawrence 和 Tom Hanks 的最短路径为 2。</p>
<ol>
<li>Jennifer Lawrence 和 Kevin Bacon 都出演了《X-Men: First Class》</li>
<li>Kevin Bacon 和 Tom Hanks 都出演了《Apollo 13》</li>
</ol>
</blockquote>
</blockquote>
<h3 id="分发代码"><a class="markdownIt-Anchor" href="#分发代码"></a> 分发代码</h3>
<ol>
<li>
<p>large 目录下的 csv 数据文件</p>
</li>
<li>
<p>small 目录下的 csv 数据文件（用于测试）：<br>
在 small 目录下的 people.csv 中，能看到每个人都有一个独特的 id、他们的名字和生日；在 movies.csv 中，每个电影都有一个独特的 id、它们的标题和发布的年份；在 stars.csv 中，每一行都是一组人的 id 和电影的 id。</p>
<blockquote>
<p>例子：人的 id 为 102，电影的 id 为 104257。这代表了 Kevin Bacon 出演过《A Few Good Men》。</p>
</blockquote>
</li>
<li>
<p><a target="_blank" rel="noopener" href="http://degrees.py">degrees.py</a>。在最上方一些数据结构被定义（<code>names</code>、<code>people</code>、<code>movies</code>），这些数据结构将保存从 CSV 文件中的信息。</p>
<ul>
<li><code>names</code> 字典，将名字映射到一组对应的 id（可能有多个演员有相同的名字）</li>
<li><code>people</code> 字典，将人 id 映射到另外一个字典（存有名字、出生年份、主演的所有电影的集合）</li>
<li><code>movies</code> 字典，将电影 id 映射到另外一个字典（存有标题、发行年份、所有出演演员的 id）</li>
</ul>
<p>文件已经事先定义了一个函数 <code>load_data()</code>，它从 CSV 文件里加载数据，并存在上述这些数据结构中。</p>
<p>主函数 <code>main()</code> 首先将数据加载到内存中（加载数据的目录需要通过命令行参数指定）。之后函数会提示用户输入两个名字，另一个函数 <code>person_id_for_name()</code> 会检索这个名字并返回 id（如果有多个演员叫这个名字，就会提示用户找出正确的 id）。然后主函数会调用 <code>shortest_path()</code> 来计算这两个人之间的最短路径，并打印出这个路径。</p>
<p>然而，<code>shortest_path()</code> 要你来写。</p>
</li>
</ol>
<h3 id="目标"><a class="markdownIt-Anchor" href="#目标"></a> 目标</h3>
<p>完成 <code>shortest_path()</code> 的实现，使其返回源 id 到目标 id 的最短路径</p>
<ol>
<li>假设有一条从源 id 到目标 id 的路径，你的函数应该返回一个列表，每个元素是一个元组：<code>(movie_id, person_id)</code></li>
<li>如果 <code>shortest_path()</code> 返回了 <code>[(1, 2), (3, 4)]</code>，那就意味着源 id 和人 2 一起出演了电影 1，人 2 在电影 3 中和人 4 出演，而人 4 是目标</li>
<li>如果从源 id 到目标 id 之间有多条最小长度的路径，你的函数可以返回其中的任何一条</li>
<li>如果两个演员之间没有可能的路径，你的函数应该返回 <code>None</code></li>
<li>你可以调用 <code>neighbors_for_person()</code>，该函数接收一个人的 id 作为参数，并返回装有 <code>(movie_id, person_id)</code> 元组的集合（这些人都和提供的人出演过电影）</li>
</ol>
<h2 id="作业tic-tac-toe"><a class="markdownIt-Anchor" href="#作业tic-tac-toe"></a> 作业 Tic-Tac-Toe</h2>
<h3 id="分发代码-2"><a class="markdownIt-Anchor" href="#分发代码-2"></a> 分发代码</h3>
<p>项目中有两个主要文件：<a target="_blank" rel="noopener" href="http://runner.py">runner.py</a> 和 <a target="_blank" rel="noopener" href="http://tictactoe.py">tictactoe.py</a>，后者包含了所有玩游戏、做出最佳动作的逻辑，而前者包含了所有运行游戏的代码。</p>
<p><a target="_blank" rel="noopener" href="http://tictactoe.py">tictactoe.py</a> 定义了三个变量：<code>X</code>、<code>O</code>、<code>EMPTY</code>，代表了棋盘上可能出现的移动。</p>
<p>函数 <code>initial_state()</code> 返回棋盘的起始状态。将棋盘表示为三个列表以代表三行，其中每个内部列表都包含了我们刚定义的变量的值。</p>
<h3 id="目标-2"><a class="markdownIt-Anchor" href="#目标-2"></a> 目标</h3>
<p>完成 <code>player()</code>、<code>actions()</code>、<code>result()</code>、<code>winner()</code>、<code>terminal()</code>、<code>utility()</code>，和 <code>minimax()</code> 这些函数。</p>
<ol>
<li>
<p><code>player()</code> 接受棋盘状态作为输入，然后返回当前回合属于哪个棋手</p>
<ul>
<li>棋盘初始化时，棋手 X 先手下棋</li>
</ul>
</li>
<li>
<p><code>action()</code> 返回一个装有在当前棋盘上可以采取的所有行动的集合</p>
<ul>
<li>每个行动是一个元组 <code>(i, j)</code>，其中 <code>i</code> 对应行，<code>j</code> 对应一行中的单元格</li>
<li>可以采取的行动代表的是在棋盘上任何尚未有 X 或者 O 的单元格</li>
</ul>
</li>
<li>
<p><code>result()</code> 接受一个棋盘和一个行动作为输入，然后返回一个新的棋盘状态</p>
<ul>
<li>如果动作并不有效，程序应该引发一个异常</li>
</ul>
</li>
<li>
<p><code>winner()</code> 接受一个棋盘作为输入。如果已经有人胜出，返回赢家</p>
<ul>
<li>
<p>假设棋手 X 赢了，就返回 <code>X</code></p>
</li>
<li>
<p>胜利目标：在水平、垂直或对角线上连续走了三步</p>
</li>
<li>
<p>如果平手，则返回 <code>None</code></p>
</li>
</ul>
</li>
<li>
<p><code>terminal()</code> 接受一个棋盘作为输入，然后返回一个布尔值，表示游戏是否结束</p>
</li>
<li>
<p><code>utility()</code> 接受一个结束了的棋盘作为输入，并输出该棋盘的效用</p>
<ul>
<li>如果棋手 X 胜利，效用为 <code>1</code>；如果棋手 O 胜利，效用为 <code>-1</code>；如果平局，效用为 <code>0</code></li>
<li>只有在 <code>terminal(board)</code> 为 <code>True</code> 时才会调用该函数</li>
</ul>
</li>
<li>
<p><code>minimax()</code> 接受一个棋盘作为输入，并返回棋手在棋盘上的最佳行动</p>
<ul>
<li>返回的应该是最优行动 <code>(i, j)</code></li>
<li>如果多个行动是最优的，那么任意一个行动都可以被返回</li>
<li>如果棋盘是结束了的棋盘，返回 <code>None</code></li>
</ul>
</li>
</ol>
<hr>
<h1 id="1-knowledge"><a class="markdownIt-Anchor" href="#1-knowledge"></a> 1. Knowledge</h1>
<p>人类根据现有的知识进行推理并得出结论。人工智能也可以从知识里得出结论。</p>
<p>什么是」基于知识进行推理以得出结论「？</p>
<p>考虑以下这些句子：</p>
<ol>
<li>如果没有下雨的话，哈利今天就会去拜访海格了</li>
<li>哈利今天拜访了海格或邓布利多，但没有同时拜访</li>
<li>哈利今天拜访了邓布利多</li>
</ol>
<p>根据这三个句子，我们可以回答」今天下雨了吗？「这个问题，尽管没有一个单独的句子告诉我们关于今天是否下雨的信息。我们可以这样做：看句子 3，得知哈利拜访了邓布利多；看句子 2，得知哈利拜访了海格或邓布利多。因此我们可以得出结论：</p>
<ol start="4">
<li>哈利没有拜访海格</li>
</ol>
<p>现在再去看句子 1，我们明白，如果没有下雨，哈利就会去拜访海格。了解了句子 4 后，我们可以得出结论：</p>
<ol start="5">
<li>今天下雨了</li>
</ol>
<p>逻辑，我们使用了逻辑来得出结论。人工智能该如何使用逻辑在现有信息的基础上得出新的结论？</p>
<p>句子是人工智能存储知识并使用它来推断新信息的方式。</p>
<h2 id="命题逻辑"><a class="markdownIt-Anchor" href="#命题逻辑"></a> 命题逻辑</h2>
<p>命题逻辑以命题为基础，即可以是真的、也可以是假的、关于世界的陈述。例如上述的句子 1~5。</p>
<ol>
<li>
<p>命题符号</p>
<ul>
<li>最常见的是字母（<code>P</code>、<code>Q</code>、<code>R</code>），用于表示一个命题</li>
</ul>
</li>
<li>
<p>逻辑连接词</p>
</li>
</ol>
<ul>
<li>连接命题符号的逻辑符号，以便以更复杂的方式对世界进行推理</li>
</ul>
<ol>
<li>
<p><code>¬</code>，」不「符号，用于反转命题的真值。例如 <code>P</code> 是」正在下雨「，<code>¬P</code> 就是」没有下雨「</p>
</li>
<li>
<p><code>^</code>，」和「符号，用于连接两个不同的命题</p>
</li>
<li>
<p><code>∨</code>，「或」符号，只要其中一边是真，那就是真</p>
</li>
</ol>
<pre><code>1. 排他性“或”：如果`P^Q`为真，那`P∨Q`就是假；排他性语句只要求其中一个参数为真
2. 包容性“或”：只要`P`、`Q`、`P^Q`为真，那就是真

我们会更倾向于使用包容性“或”。

&gt; 更多的例子：
&gt;
&gt; - 包容性“或”：为了吃甜点，你必须清理你的房间或者修剪草坪
&gt; 	- 如果你清理了房间，还修剪了草坪，你仍然会吃到甜点
&gt; - 排他性“或”：甜点的话，你可以吃饼干或者吃冰淇淋
&gt; 	- 你不能同时吃到饼干和冰淇淋
&gt; 	- 排他性“或”通常被简称为XOR，符号是⊕
</code></pre>
<ol start="4">
<li>
<p><code>→</code>，「暗示」符号，表示「如果 <code>P</code> 那么 <code>Q</code>」的结构。例如 <code>P</code> 是「正在下雨」，<code>Q</code> 是「我在室内」，那么 <code>p→Q</code> 意味着「如果正在下雨，那么我在室内」。这个案例中，<code>P</code> 被称为前项（antecedent），<code>Q</code> 被称为后项（consequent）</p>
<ul>
<li>如果前项为真，后项为真，那么整个暗示就为真</li>
<li>如果前项为真，后向为假，那么整个暗示就为假</li>
<li>然而，当前项为假，后项为真时，暗示总是真的</li>
</ul>
</li>
<li>
<p><code>↔</code>，「双条件」符号，或「如果 &amp; 只有当」。<code>P↔Q</code> 相当于 <code>P→Q</code> 和 <code>Q→P</code>。引用上述的例子，<code>P↔Q</code> 就是「如果正在下雨，那么我在室内」和「如果我在室内，那么正在下雨」</p>
</li>
</ol>
<h3 id="模型"><a class="markdownIt-Anchor" href="#模型"></a> 模型</h3>
<p>模型是对每个命题的真值的分配，而命题是关于世界的陈述，可以是真也可以是假。然而，关于世界的知识就体现在这些命题的真值中。模型是提供关于世界的信息的真值分配。</p>
<p>例如，<code>P</code> 是「正在下雨」，<code>Q</code> 是「今天是周二」，一个模型可以是以下的真值赋值：<code>{P=True, Q=False}</code>。这个模型意味着正在下雨，但今天不是周二。在这种情况下还有更多可能的模型，例如 <code>{P=True, Q=True}</code>，也就是现在既下雨，也是周二。</p>
<p>事实上，可能的模型的数量是命题的数量的两倍。如果我们有两个命题，那就有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">2^2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span> 个可能的模型。</p>
<h3 id="知识库"><a class="markdownIt-Anchor" href="#知识库"></a> 知识库</h3>
<p>知识库是一组被基于知识的代理所知道的句子，也就是人工智能以命题逻辑句子的形式提供的关于世界的知识，可以用来对世界进行额外的推断。</p>
<h3 id="蕴涵"><a class="markdownIt-Anchor" href="#蕴涵"></a> 蕴涵（<code>⊨</code>）</h3>
<p>如果 <code>α⊨β</code>，那么在任何 <code>α</code> 为真的世界中，<code>β</code> 也是真的。</p>
<ul>
<li>例如 <code>α</code> 是「这是一月中的一个周二」，<code>β</code> 是「这是一个周二」，然后 <code>α⊨β</code>。那么我们能知道这是一个在一月内的周二，并且这是一个周二</li>
<li>蕴含和暗示不同。暗示是两个命题间的逻辑连接词，而蕴含是一种关系，意味着如果 <code>α</code> 中所有的信息都是真，那么 <code>β</code> 中所有的信息也都是真</li>
</ul>
<h2 id="推理"><a class="markdownIt-Anchor" href="#推理"></a> 推理</h2>
<p>推理是指从旧的句子中推导出新的句子的过程。</p>
<p>例如上述的哈利波特例子中，句子 4~5 是句子 1~3 中推断出来的。</p>
<p>有多种方法可以在现有知识的基础上推断出新的知识。首先，我们将考虑模型检查算法（Model Checking algorithm）。</p>
<ul>
<li>
<p>为了确定 <code>KB⊨α</code>（换言之，回答问题「我们能否根据我们的知识库得出 <code>α</code> 为真的结论」）：</p>
<ul>
<li>列举所有可能的模型</li>
<li>如果每个模型中 <code>KB</code> 为真，那么 <code>α</code> 也都是真的，因此 <code>KB⊨α</code></li>
</ul>
</li>
<li>
<p>再考虑这个例子：</p>
<ul>
<li>
<p><code>P</code> 是「今天是星期二」，<code>Q</code> 是「现在在下雨」，<code>R</code> 是「哈利要去跑步」</p>
</li>
<li>
<p><code>KB</code>：<code>(P^¬Q) → R</code>，用话说就是：<code>P</code> 和 <code>¬Q</code> 暗示了 <code>R</code>。<code>P</code> 是真，<code>Q</code> 是假，那么 <code>R</code> 是真还是假？<code>KB</code> 是否 <code>⊨R</code>？</p>
</li>
<li>
<p>先列举出所有可能的模型</p>
<table>
<thead>
<tr>
<th>命题</th>
<th>值</th>
</tr>
</thead>
<tbody>
<tr>
<td>P<br>Q<br>R</td>
<td>false<br>false<br>false</td>
</tr>
<tr>
<td>P<br>Q<br>R</td>
<td>false<br>false<br>true</td>
</tr>
<tr>
<td>P<br>Q<br>R</td>
<td>false<br>true<br>false</td>
</tr>
<tr>
<td>P<br>Q<br>R</td>
<td>false<br>true<br>true</td>
</tr>
<tr>
<td>P<br>Q<br>R</td>
<td>true<br>false<br>false</td>
</tr>
<tr>
<td>P<br>Q<br>R</td>
<td>true<br>false<br>true</td>
</tr>
<tr>
<td>P<br>Q<br>R</td>
<td>true<br>true<br>false</td>
</tr>
<tr>
<td>P<br>Q<br>R</td>
<td>true<br>true<br>true</td>
</tr>
</tbody>
</table>
</li>
<li>
<p>通过每一个模型，检查它在我们的知识库中是否为真</p>
</li>
<li>
<p>首先，我们知道 <code>P</code> 为真，因此所有 <code>P</code> 为假的模型里，<code>KB</code> 都为假。同样地，我们知道 <code>Q</code> 为假，因此所有 <code>Q</code> 为真的模型里，<code>KB</code> 都为假。最终我们只剩下两个模型，<code>P</code> 都是真且 <code>Q</code> 都是假。我们知道 <code>R</code> 是真，因此最后 <code>R</code> 为假的模型中，<code>KB</code> 自然也是假</p>
</li>
<li>
<p>再来看看我们的表，我们只有一个 <code>KB</code> 为真的模型。根据蕴含的含义，得出 <code>KB⊨R</code></p>
</li>
<li>
<p>这些知识和逻辑可以被这样写：</p>
  <figure class="highlight python"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">from</span> logic <span class="keyword">import</span> *</span><br><span class="line"></span><br><span class="line"><span class="comment"># 创建新的类，每个类都有一个名字或符号，代表命题</span></span><br><span class="line">rain = Symbol(<span class="string">"rain"</span>)  <span class="comment"># 在下雨</span></span><br><span class="line">hagrid = Symbol(<span class="string">"hagrid"</span>)  <span class="comment"># 哈利见海格</span></span><br><span class="line">dumbledore = Symbol(<span class="string">"dumbledore"</span>)  <span class="comment"># 哈利见邓布利多</span></span><br><span class="line"></span><br><span class="line"><span class="comment"># 将句子保存进知识库</span></span><br><span class="line"><span class="comment"># 先使用“和”逻辑，因为每个命题都代表了我们已知为真的知识</span></span><br><span class="line">knowledge = And( </span><br><span class="line">	Implication(Not(rain), hagrid),  <span class="comment"># ¬(在下雨)→(哈利见海格)</span></span><br><span class="line">    Or(hagrid, dumbledore),  <span class="comment"># (哈利见海格)∨(哈利见邓布利多)</span></span><br><span class="line">    Not(And(hagrid, dumbledore)),  <span class="comment"># ¬(哈利见海格^哈利见邓布利多)，但没有见两人</span></span><br><span class="line">    dumbledore  <span class="comment"># 哈利见邓布利多（事实）</span></span><br><span class="line">)</span><br></pre></td></tr></tbody></table></figure>
</li>
<li>
<p>要运行模型检查算法，我们需要这些信息：</p>
<ul>
<li>知识库，用于推理</li>
<li>一个查询，或我们感兴趣的命题是否被 KB 所包含</li>
<li>一个装有所有被使用的符号（或原子命题）的列表（也就是我们案例中的 <code>rain</code>、<code>hagrid</code>、<code>dumbledore</code>）</li>
<li>模型</li>
</ul>
  <figure class="highlight python"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">def</span> <span class="title function_">check_all</span>(<span class="params">knowledge, query, symbols, model</span>):</span><br><span class="line">    <span class="comment"># 如果模型有分配给每个符号</span></span><br><span class="line">    <span class="comment"># 逻辑：从一个符号列表开始。函数递归时，每次的调用都会从列表中删除一个符号，并从中生成模型。当符号列表为空时，我们知道我们已经完成了对符号的每一个可能的真值分配的模型生成</span></span><br><span class="line">    <span class="keyword">if</span> <span class="keyword">not</span> symbols:</span><br><span class="line">        <span class="comment"># 如果在模型中的KB为真，查询也就是真</span></span><br><span class="line">        <span class="keyword">if</span> knowledge.evaluate(model):</span><br><span class="line">            <span class="keyword">return</span> query.evaluate(model)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">True</span></span><br><span class="line">    </span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="comment"># 选择剩余的未使用符号的其中一个</span></span><br><span class="line">        remaining = symbols.copy()</span><br><span class="line">        p = remaining.pop()</span><br><span class="line">        </span><br><span class="line">        <span class="comment"># 创建一个符号为真的模型</span></span><br><span class="line">        model_true = model.copy()</span><br><span class="line">        model_true[p] = <span class="literal">True</span></span><br><span class="line">        </span><br><span class="line">        <span class="comment"># 创建一个符号为假的模型</span></span><br><span class="line">        model_false = model.copy()</span><br><span class="line">        model_false[p] = <span class="literal">False</span></span><br><span class="line">        </span><br><span class="line">        <span class="comment"># 确保两个模型中都有蕴含关系</span></span><br><span class="line">        <span class="keyword">return</span>(</span><br><span class="line">            check_all(knowledge, query, </span><br><span class="line">                      remaining, model_true) </span><br><span class="line">            <span class="keyword">and</span> </span><br><span class="line">            check_all(knowledge, query, </span><br><span class="line">                      remaining, model_false)</span><br><span class="line">        )</span><br></pre></td></tr></tbody></table></figure>
</li>
<li>
<p>我们只对 <code>KB</code> 为真的模型感兴趣。如果 <code>KB</code> 为假，那么这个模型就和我们的案例无关</p>
<blockquote>
<p>例子：</p>
<ul>
<li><code>P</code> 为「哈利扮演 seeker」、<code>Q</code> 为「奥利弗扮演 keeper」，<code>R</code> 为「格兰芬多获胜」</li>
<li><code>KB</code> 规定 <code>P Q (P ^ Q) → R</code>
<ul>
<li>也就是 <code>P</code> 为真，<code>Q</code> 为真，那么 <code>R</code> 也为真</li>
</ul>
</li>
<li>想象一个模型，哈利扮演的是 beater 而非 seeker，也就是 <code>P</code> 为假。这种情况下我们并不关心格兰芬多是否胜利（即 <code>R</code> 是否为真）。因为我们只对 <code>P</code> 和 <code>Q</code> 为真的模型感兴趣</li>
</ul>
</blockquote>
</li>
<li>
<p>此外，<code>check_all()</code> 的工作方式是递归的。也就是说它会选择一个符号，创建两个模型，其中一个符号为真，另一个符号为假，然后再次调用自己，现在有两个模型因这个符号的真值分配而不同。这个函数会一直这样做，直到所有的符号都在模型中被分配了真值、让列表中的符号为空。一旦列表为空，函数会在每个实例中检查模型中的 KB 是否为真。如果为真，函数就会检查查询是否为真，如前面所述</p>
</li>
</ul>
</li>
</ul>
<h2 id="知识工程"><a class="markdownIt-Anchor" href="#知识工程"></a> 知识工程</h2>
<p>知识工程是弄清如何在人工智能中表示命题和逻辑的过程。</p>
<p>来看看例子：游戏 Clue。</p>
<ul>
<li>在这个游戏中，一个人用一个工具在一个地方犯下了一起谋杀案</li>
<li>人、工具、地点都用卡片表示</li>
<li>每个类别的卡片被随机抽取并装入一个信封，由参与者来揭开谁是凶手</li>
<li>参与者通过揭开卡片并从这些线索中推断出信封里一定有什么</li>
</ul>
<p>我们将使用模型检查算法来揭开这个谜团。在我们的模型中，我们把我们知道的、与谋杀案有关的项目标记为真，其余的都为假。</p>
<p>假设我们的游戏是这样的：</p>
<ul>
<li>有三个人：芥末、梅子、猩红</li>
<li>有三个工具：刀、左轮手枪、扳手</li>
<li>有三个地点：舞厅、厨房、图书馆</li>
</ul>
<p>我们可以通过添加游戏规则开始创建我们的知识库：</p>
<ol>
<li>
<p>我们肯定的是：有一个人是凶手，使用的是一种工具，而且谋杀发生在一个地点。命题逻辑：</p>
<ul>
<li><code>(芥末∨梅子∨猩红)</code></li>
<li><code>(刀∨左轮手枪∨扳手)</code></li>
<li><code>(舞厅∨厨房∨图书馆)</code></li>
</ul>
</li>
<li>
<p>游戏开始时，每个玩家会看到一个人、一个工具、一个地点，并且得知这些与谋杀没有联系。玩家们不会共享从卡片中看到的信息。假设我们的玩家得到了芥末、厨房和左轮手枪的卡片。因此我们可以添加这些命题逻辑进我们的知识库：</p>
<ul>
<li><code>¬(芥末)</code></li>
<li><code>¬(厨房)</code></li>
<li><code>¬(左轮手枪)</code></li>
</ul>
</li>
<li>
<p>在游戏的其他情况下，人们可以进行猜测，提出人、工具、地点的一种组合。假设推测是「猩红用扳手在图书馆作案」。如果这个推测是错误的，那么可以推导出以下内容：</p>
<ul>
<li><code>(¬猩红∨¬图书馆∨¬扳手)</code></li>
</ul>
</li>
<li>
<p>现在有人给我们看到了梅子的卡片，我们可以添加这个到我们的知识库：</p>
<ul>
<li><code>¬(梅子)</code></li>
</ul>
</li>
<li>
<p>这时我们可以得出结论，凶手是猩红，因为我们有证据表明另外两个人不是</p>
</li>
<li>
<p>只要在增加一个知识，比如说，不是舞厅，就可以给我们更多的信息：</p>
<ul>
<li><code>¬(舞厅)</code></li>
</ul>
</li>
<li>
<p>现在利用之前的多个数据，我们可以推断出是猩红在图书馆内用刀杀了人。然而这个猜测是错的，因为我们没有证据表明凶器具体是什么。最终的结论是刀</p>
</li>
</ol>
<p>整个流程在 Python 中就是：</p>
<figure class="highlight python"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 添加线索至知识库</span></span><br><span class="line">knowledge = And(</span><br><span class="line">    <span class="comment"># 添加游戏起始条件</span></span><br><span class="line">    Or(mustard, plum, scarlet),</span><br><span class="line">    Or(ballroom, kitchen, library),</span><br><span class="line">    Or(knife, revolver, wrench),</span><br><span class="line">    </span><br><span class="line">    <span class="comment"># 添加我们所看到的第一组卡片</span></span><br><span class="line">    Not(mustard),</span><br><span class="line">    Not(kitchen),</span><br><span class="line">    Not(revolver),</span><br><span class="line">    </span><br><span class="line">    <span class="comment"># 添加他人举出的猜测</span></span><br><span class="line">    Or(Not(scarlet), Not(library), Not(wrench)),</span><br><span class="line">    </span><br><span class="line">    <span class="comment"># 添加我们之后得知的线索</span></span><br><span class="line">    Not(plum),</span><br><span class="line">    Not(ballroom)</span><br><span class="line">)</span><br></pre></td></tr></tbody></table></figure>
<p>我们还可以看看另外一个逻辑谜题：</p>
<ul>
<li>
<p>有四个不同的人：吉尔德洛依、波莫纳、密涅瓦、霍勒斯</p>
</li>
<li>
<p>他们被分配到四个不同的学院：格兰芬多、赫夫帕夫、拉文克劳、斯莱特林</p>
</li>
<li>
<p>每个学院正好有一个人</p>
</li>
</ul>
<p>首先，这个谜题的条件很难被命题逻辑来表示，因为每一个可能的分配都是一个命题。其次为了表示每个人都属于某个学院，就需要 <code>Or()</code> 来包含所有每个人可能的学院分配情况。接着，为了说明如果有一个人被分配到一个学院，他们就不会被分配到其他学院，我们还要给每个人写一大堆命题。</p>
<p>另一种可以用命题逻辑解决的谜题是 Mastermind。</p>
<ul>
<li>玩家 1 按照一定的顺序排列颜色，玩家 2 要猜出该顺序</li>
<li>每个回合里，玩家 2 做出猜测，玩家 1 给出一个数字，表示玩家 2 猜对了多少种颜色</li>
</ul>
<ol>
<li>假设玩家 2 猜测「红蓝绿黄」，玩家 1 给出数字 2</li>
<li>玩家 2 仅切换 2 个颜色的位置：「蓝红绿黄」，玩家 1 给出数字 0</li>
<li>借此得知，红蓝原先的位置是正确的，这时切换另外 2 个颜色的位置：「红蓝黄绿」，玩家 1 给出数字 4，代表游戏结束。</li>
</ol>
<ul>
<li>用命题逻辑来表示这一点，需要我们有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mtext>颜色的数量</mtext><msup><mo stretchy="false">)</mo><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">(\text {颜色的数量})^2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord text"><span class="mord cjk_fallback">颜色的数量</span></span><span class="mclose"><span class="mclose">)</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span> 个原子命题。因此在有四种颜色的情况下，我们将有红 0、红 1、红 2、红 3、蓝 0…… 这些命题代表着颜色和位置</li>
<li>用命题逻辑表示游戏规则，也就是每个位置只有一种颜色，而且没有颜色重复，并将其加入知识库</li>
<li>最后将我们拥有的所有线索添加到知识库中</li>
</ul>
<h2 id="推理规则"><a class="markdownIt-Anchor" href="#推理规则"></a> 推理规则</h2>
<p>模型检查不是一种有效的算法，因为它必须在给出答案之前考虑每一种可能的模型。</p>
<blockquote>
<p>如果是 <code>KB</code> 为真的模型，那么查询 <code>R</code> 也是真的</p>
</blockquote>
<p>推理规则允许我们在现有知识的基础上生成新的信息，而无需考虑每一个可能的模型。推理规则通常使用一个横条来表示，横条将上面的部分（前提）和下面的部分（结论）分开。前提是我们拥有的任何知识，而结论是基于前提可以产生的知识。</p>
<p><img src="/posts/d235/Modus_Ponens_Example.png" alt="Modus Ponens Example"></p>
<h3 id="肯定前件"><a class="markdownIt-Anchor" href="#肯定前件"></a> 肯定前件</h3>
<p>肯定前件（Modus Ponens）就是在我们知道一个暗示、其前项是真的，那么后项也是真的。</p>
<p><img src="/posts/d235/Modus_Ponens.png" alt="Modus Ponens"></p>
<h3 id="连词消除"><a class="markdownIt-Anchor" href="#连词消除"></a> 连词消除</h3>
<p>也被称为和消除（And Elimination）。</p>
<p>如果一个「和」的命题为真，那么其中任何一个原子命题也是真。</p>
<blockquote>
<p>例子：</p>
<ul>
<li>已知：哈利是罗恩和赫敏的朋友</li>
<li>结论：哈利是赫敏的朋友</li>
</ul>
</blockquote>
<p><img src="/posts/d235/And_Elimination.png" alt="And Elimination"></p>
<h3 id="双重否定"><a class="markdownIt-Anchor" href="#双重否定"></a> 双重否定</h3>
<p>一个命题如果被否定了两次，那它就是真。</p>
<blockquote>
<p>例子：哈利没有通过考试是不真实的。</p>
<ol>
<li><code>(哈利没有通过考试)是不真实的</code></li>
<li><code>¬(哈利没有通过考试)</code></li>
<li><code>¬(¬(哈利没有通过考试))</code></li>
<li>双重否定抵消了彼此，让该命题「哈利通过了考试」变为真</li>
</ol>
</blockquote>
<p><img src="/posts/d235/Double_Negation_Elimination.png" alt="Double Negation Elimination"></p>
<h3 id="暗示消除"><a class="markdownIt-Anchor" href="#暗示消除"></a> 暗示消除</h3>
<p>暗示相当于被否定的前项和后项之间的「或」关系。</p>
<blockquote>
<p>例子：以下等同于彼此</p>
<ul>
<li>如果下雨了，那么哈利在室内</li>
<li>（没有下雨） 或（哈利在室内）</li>
</ul>
</blockquote>
<p><img src="/posts/d235/Implication_Elimination.png" alt="Implication Elimination"></p>
<p>由于 <code>P→Q</code> 和 <code>P∨Q</code> 有相同的真值分配，因此在逻辑上是等价的。</p>
<p>另一种思考方式是如果满足两个可能的条件中的任何一个，暗示就是真的：</p>
<ol>
<li>如果前项为假，那么暗示为真
<ul>
<li><code>¬P∨Q</code>：如果 <code>P</code> 为假，那么这个命题总是真的</li>
</ul>
</li>
<li>如果前项为真，只有当后项为真时，暗示才为真
<ul>
<li>如果 <code>P</code> 和 <code>Q</code> 都是真，那么 <code>¬P∨Q</code> 就为真</li>
<li>如果 <code>P</code> 为真，<code>Q</code> 为假，那么 <code>¬P∨Q</code> 就为假</li>
</ul>
</li>
</ol>
<h3 id="双条件消除"><a class="markdownIt-Anchor" href="#双条件消除"></a> 双条件消除</h3>
<p>一个双条件命题等同于一个暗示命题和其翻转命题用「和」连接在一起。</p>
<blockquote>
<p>例子：以下等同于彼此。</p>
<ul>
<li>只有在哈利在室内的时候，外面才会下雨</li>
<li>（如果下雨了，那么哈利在室内） 和（如果哈利在室内，那么外面在下雨）</li>
</ul>
</blockquote>
<p><img src="/posts/d235/Biconditional_Elimination.png" alt="Biconditional_Elimination"></p>
<h3 id="德摩根定律"><a class="markdownIt-Anchor" href="#德摩根定律"></a> 德摩根定律</h3>
<p>有可能把一个「和」连接词变成一个「或」连接词。例如：「哈利和罗恩都通过了测试，这不是真的」，可以得出结论：「哈利通过考试不是真的」或者「罗恩通过考试不是真的」。也就是说，要使前面的「和」命题为真，「或」命题中的至少一个命题必须为真。</p>
<p><img src="/posts/d235/De_Morgans_1.png" alt="De Morgan's 1"></p>
<p>同样地，也可以得出相反的结论。例如命题「哈利或罗恩通过测试是不真实的」可以被改写为「哈利没有通过测试」和「罗恩没有通过测试」。</p>
<h3 id="分配律"><a class="markdownIt-Anchor" href="#分配律"></a> 分配律</h3>
<p>一个由两个元素组成的命题，如果使用「和」或「或」连接词来分组，那就可以被分配或分解成由「和」和「或」组成的更小的单元。</p>
<p><img src="/posts/d235/Distributive_1.png" alt="Distributive 1"></p>
<h3 id="知识和搜索问题"><a class="markdownIt-Anchor" href="#知识和搜索问题"></a> 知识和搜索问题</h3>
<p>推理可以被看作是一个具有以下属性的搜索问题：</p>
<ul>
<li>初始状态：起始初始库</li>
<li>行动：推理规则</li>
<li>过渡模型：推理中的新知识库</li>
<li>目标测试：检查我们要证明的语句是否在知识库内</li>
<li>路径成本函数：证明中的步骤数量</li>
</ul>
<p>这些都表示了搜索算法的多功能性，使我们能够在现有知识的基础上利用推理规则得出新的信息。</p>
<h2 id="归结原理"><a class="markdownIt-Anchor" href="#归结原理"></a> 归结原理</h2>
<p>归结原理（resolution）是一个强大的推理规则。如果「或」命题中的两个原子命题中的一个为假，那么另外一个就必须为真。</p>
<p><img src="/posts/d235/Resolution_1.png" alt="Resolution"></p>
<p>归结原理依赖于互补文字（complementary literals），即两个相同的原子命题，其中一个被否定，另一个没有被否定。</p>
<p><img src="/posts/d235/Resolution_2.png" alt="Resolution"></p>
<p>互补文字使我们能够通过解析推理产生新的句子。因此推理算法通过定位互补文字来生成新的知识。</p>
<p>一个从句是一个字词的二元链接（一个命题符号或者一个命题符号的否定）。分句由一个「或」逻辑连接词（<code>P∨Q∨R</code>）连接。另一方面，连词由「和」逻辑连接词相连的的命题组成（<code>P^Q^R</code>）。</p>
<p>分句允许我们把任何逻辑语句转换成合取范式（CNF），也就是分句的连接，例如：</p>
<ul>
<li><code>(A∨B∨C)^(D∨¬E)^(F∨G)</code></li>
</ul>
<p>将命题转换为合取范式的步骤：</p>
<ol>
<li>消除双条件；将 <code>α↔β</code> 变成 <code>(α→β)^(β→α)</code></li>
<li>消除暗示；将 <code>α→β</code> 变成 <code>¬α∨β</code></li>
<li>使用德摩根定律，将否定向内移动，直到只有文字被否定；将 <code>¬(α∨β)</code> 变为 <code>¬α∨¬β</code></li>
</ol>
<blockquote>
<p>更多的例子：<code>(P∨Q)→R</code></p>
<ol>
<li><code>¬(P∨Q)∨R</code>，消除暗示</li>
<li><code>(¬P∨¬Q)∨R</code>，德摩根定律</li>
<li><code>(¬P∨R)^(¬Q∨R)</code>，分配律</li>
</ol>
</blockquote>
<p>在这一点上，我们可以对合取范式运行推理算法。偶尔在解析推理的过程中我们会遇到这样的情况：一个子句包含两次相同的文字。我们会需要使用一个叫做分解（factoring）的过程，将重复的文字删除。</p>
<blockquote>
<p>例子：</p>
<p><code>(P∨Q∨S)^(¬P∨R∨S)</code> 允许我们通过解析推断 <code>(Q∨S∨R∨S)</code>。重复的 S 会被删除，得到 <code>(Q∨R∨S)</code>。</p>
</blockquote>
<p>消除一个文字和它的否定，也就是 <code>¬P</code> 和 <code>P</code>，可以得到空的分句。空句总是假，因为 <code>P</code> 和 <code>¬P</code> 不可能都是真：</p>
<ul>
<li>确定 KB 是否 <code>⊨α</code>：
<ul>
<li>检查：<code>(KB^¬α)</code> 是否是矛盾的？
<ul>
<li>如果是，则 <code>KB⊨α</code></li>
<li>如果否，则没有蕴含关系</li>
</ul>
</li>
</ul>
</li>
</ul>
<p>矛盾证明是计算机科学中经常使用的一种工具。如果我们的知识库为真，而它与 <code>¬α</code> 相矛盾。这意味着 <code>¬α</code> 为假。因此 <code>α</code> 绝对为真。</p>
<ul>
<li>确定 <code>KB</code> 是否 <code>⊨α</code>：
<ul>
<li>将 <code>(KB^¬α)</code> 转换为合取范式</li>
<li>继续检查，看我们能否用归结原理产生一个新的分句</li>
<li>如果产生了一个空句，代表我们得到了一个矛盾，从而证明 <code>KB⊨α</code></li>
<li>如果没有产生矛盾，也没有更多的子句可以被推断出来，也就没有蕴含关系</li>
</ul>
</li>
</ul>
<blockquote>
<p>例子：<code>(A∨B)^(¬B∨C)^(¬C)</code> 是否蕴含 A？</p>
<ol>
<li>用矛盾法证明。假设 A 为假，那就会得出 <code>(A∨B)^(¬B∨C)^(¬C)^(¬A)</code></li>
<li>既然我们知道 <code>C</code> 为假（因为 <code>¬C</code>），那么 <code>(¬B∨C)</code> 的唯一可能是 B 也是假的，这样 <code>¬B</code> 就为真（将 <code>¬B</code> 加入到我们的知识库）</li>
<li><code>(A∨B)</code> 的唯一可能是 <code>A</code> 为真（将 A 加入我们的知识库）</li>
<li>现在知识库中有两个互补的文字：<code>A</code> 和 <code>¬A</code>。我们得到了一个空的集合，根据定义，空的集合为假，所以我们得到了一个矛盾</li>
</ol>
</blockquote>
<h2 id="一阶逻辑"><a class="markdownIt-Anchor" href="#一阶逻辑"></a> 一阶逻辑</h2>
<p>一阶逻辑（First-Order Logic）是另一种类型的逻辑，它允许我们比命题逻辑更简洁地表达更复杂的想法。一阶逻辑使用两种类型的符号：常量符号和谓词符号。</p>
<ul>
<li>常量符号代表对象</li>
<li>谓词符号更像是关系或函数，接受一个参数并返回一个真或假的值</li>
</ul>
<p>回到逻辑谜题：在霍格沃茨有不同的人和房子的分配。常量符号是人或者学院，而谓词符号就是一些持有常量符号真或假的属性。</p>
<blockquote>
<p>例子：</p>
<ul>
<li>使用句子 <code>Person(Minerva)</code> 来表达 Minerva 是一个人</li>
<li>使用句子 <code>House(Gryffindor)</code> 来表达格兰芬多是一个学院</li>
</ul>
</blockquote>
<p>所有的逻辑连接词在一阶逻辑中的使用方式与命题逻辑的相同。</p>
<blockquote>
<p>例子：</p>
<ul>
<li><code>¬House(Minerva)</code> 表达了 Minerva 不是一个学院</li>
</ul>
</blockquote>
<p>一个谓词符号也可以接受两个或以上的参数，并表达它们之间的关系。</p>
<blockquote>
<p>例子：</p>
<ul>
<li><code>BelongsTo</code> 表达了两个参数之间的关系，即人和人所属的房子</li>
<li>Minerva 属于格兰芬多可以写成：<code>BelongsTo(Minerva, Gryffindor)</code></li>
</ul>
</blockquote>
<h3 id="全称量化"><a class="markdownIt-Anchor" href="#全称量化"></a> 全称量化</h3>
<p>量化是一种工具，可以在一阶逻辑中用来表示句子而不使用特定的常数符号。全称量化使用符号 <code>∀</code> 来表达」对于所有「（for all）。</p>
<blockquote>
<p>例子：<code>∀x.BelongsTo(x, Gryffindor) -&gt; ¬BelongsTo(x, Hufflepuff)</code>，表达了对于所有符号来说，如果这个符号属于格兰芬多，那么它就不属于赫夫帕夫。</p>
</blockquote>
<h3 id="存在量化"><a class="markdownIt-Anchor" href="#存在量化"></a> 存在量化</h3>
<p>存在量化是一个与全称量化平行的概念。然而，全称量化被用来创建对所有 <code>x</code> 都为真的句子，存在量化被用来创建对至少一个 <code>x</code> 为真的句子。存在量化使用符号 <code>∃</code> 来表示。</p>
<blockquote>
<p>例子：<code>∃x.House(x)^BelongsTo(Minerva, x)</code>，意味着至少有一个符号既是学院，Minerva 也属于它。</p>
<p>换句话说，这表达了 Minerva 属于一个学院的想法。</p>
</blockquote>
<p>存在量化和全称量化可以在同一个句子中使用。</p>
<blockquote>
<p>例子：<code>∀x.Person(x) -&gt; (∃x.House(y)^BelongsTo(x,y))</code> 表达的意思是如果 <code>x</code> 是一个人，那么至少有一个学院 <code>y</code> 是这个人的归属。</p>
<p>换句话说，这个句子意味着每个人都属于一个学院。</p>
</blockquote>
<h2 id="测验"><a class="markdownIt-Anchor" href="#测验"></a> 测验</h2>
<ol>
<li>
<p>考虑以下逻辑句子：</p>
<ol>
<li>如果赫敏在图书馆内，那么哈利就在图书馆内</li>
<li>赫敏在图书馆内</li>
<li>罗恩在图书馆并且罗恩不在图书馆内</li>
<li>哈利在图书馆内</li>
<li>哈利不在图书馆内或赫敏在图书馆内</li>
<li>罗恩在图书馆内或赫敏在图书馆内</li>
</ol>
<p>哪个逻辑蕴含为真：</p>
<ul>
<li>句子 6 蕴含了句子 3</li>
<li>句子 6 蕴含了句子 2</li>
<li>句子 2 蕴含了句子 5</li>
<li>句子 5 蕴含了句子 6</li>
<li>句子 1 蕴含了句子 4</li>
<li>句子 2 蕴含了句子 2</li>
</ul>
</li>
<li>
<p>表达式 <code>A⊕B</code> 表示句子 "A 或 B，但不是全部为真"。以下哪个在逻辑上等同于 <code>A⊕B</code>：</p>
<ul>
<li><code>(A ∨ B) ∧ ¬ (A ∧ B)</code></li>
<li><code>(A ∨ B) ∧ (A ∧ B)</code></li>
<li><code>(A ∧ B) ∨ ¬ (A ∨ B)</code></li>
<li><code>(A ∨ B) ∧ ¬ (A ∨ B)</code></li>
</ul>
<blockquote>
<p>答案：<code>(A ∨ B) ∧ ¬ (A ∧ B)</code></p>
<p>解析：(A 或者 B）和 不是（A 和 B)</p>
</blockquote>
</li>
<li>
<p><code>R</code> 是」现在下雨「，<code>C</code> 是」现在多云「，<code>S</code> 是」现在晴天「。哪个表达了」如果现在下雨，那么现在是多云而不是晴天「：</p>
<ul>
<li>
<p><code>(R → C) ∧ ¬S</code></p>
</li>
<li>
<p><code>R → C → ¬S</code></p>
</li>
<li>
<p><code>R ∧ C ∧ ¬S</code></p>
</li>
<li>
<p><code>R → (C ∧ ¬S)</code></p>
</li>
<li>
<p><code>(C ∨ ¬S) → R</code></p>
</li>
</ul>
<blockquote>
<p>答案：<code>R → (C ∧ ¬S)</code></p>
<p>解析：（现在下雨） 暗示（现在多云 和 不是（现在晴天）)</p>
</blockquote>
</li>
<li>
<p><code>Student(x)</code> 代表了」x 是一个学生「；<code>Course(x)</code> 代表了」x 是一个课程「；<code>Enrolled(x,y)</code> 代表了」x 入学了 y「。哪个一阶逻辑句子代表了」哈利和赫敏同时入学了的课程「：</p>
<ul>
<li>
<p><code>∃x. Enrolled(Harry, x) ∨ Enrolled(Hermione, x)</code></p>
</li>
<li>
<p><code>∀x. Enrolled(Harry, x) ∨ Enrolled(Hermione, x)</code></p>
</li>
<li>
<p><code>∀x. Course(x) ∧ Enrolled(Harry, x) ∧ Enrolled(Hermione, x)</code></p>
</li>
<li>
<p><code>∃x. Course(x) ∧ Enrolled(Harry, x) ∧ Enrolled(Hermione, x)</code></p>
</li>
<li>
<p><code>∀x. Enrolled(Harry, x) ∧ ∀y. Enrolled(Hermione, y)</code></p>
</li>
<li>
<p><code>∃x. Enrolled(Harry, x) ∧ ∃y. Enrolled(Hermione, y)</code></p>
</li>
</ul>
<blockquote>
<p>答案：<code>∃x. Course(x) ∧ Enrolled(Harry, x) ∧ Enrolled(Hermione, x)</code></p>
<p>解析：(x 是一个课程） 和（哈利入学了 x）和（赫敏入学了 x)；存在量化：至少有一个课程，并且哈利属于它，赫敏也属于它</p>
</blockquote>
</li>
</ol>
<h2 id="作业knights"><a class="markdownIt-Anchor" href="#作业knights"></a> 作业 Knights</h2>
<p>1978 年，逻辑学家 Raymond Smullyan 出版了《这本书叫什么名字？》。这是一本逻辑谜题书。在这本书中，有一类谜题被 Smullyan 称作为」骑士和无赖「（Knights and Knaves）。</p>
<p>在这个谜题中，以下信息被给出：</p>
<ul>
<li>每个角色要么是骑士，要么就是无赖</li>
<li>骑士总是说真话，而无赖总是撒谎</li>
</ul>
<p>这个迷题的目的是，给定一组由每个角色说出的句子，对于每个角色，确定该角色是骑士还是无赖。</p>
<p>例如单个角色 A，它说」我既是骑士也是无赖「。根据逻辑，我们可以推断这句话不可能为真。因此 A 一定是无赖。</p>
<h3 id="分发代码-3"><a class="markdownIt-Anchor" href="#分发代码-3"></a> 分发代码</h3>
<p>瞅瞅 logic.py 文件，它定义了一些用于不同类型的逻辑连接词的类。这些类可以互相组成，例如 <code>And(Not(A), Or(B, C))</code> 这样的表达式代表了一个逻辑句子，说明 <code>A</code> 不是真的，而 <code>B</code> 或 <code>C</code> 是真。</p>
<p>该文件还有一个函数 <code>model_check()</code>，它接收一个知识库和一个查询作为参数。知识库是一个单一的逻辑句子：如果多个逻辑句子是已知的，它们就可以被连接到一个 <code>And()</code> 中。<code>model_check()</code> 递归地考虑了所有可能的模型。如果知识库包含了查询，就返回 <code>True</code>，否则返回 <code>False</code>。</p>
<p><a target="_blank" rel="noopener" href="http://xn--puzzle-200ky68hgexroha.py">现在来看看 puzzle.py</a>。在顶部有六个命题符号被定义，例如 <code>AKnight</code> 表示」A 是一个骑士「，而 <code>AKnave</code> 表示」A 是一个无赖「。我们也同样为人物 B 和 C 定义了命题符号。</p>
<p>下面还有四个不同的知识库：<code>knowledge0</code>、<code>knowledge1</code>、<code>knowledge2</code>、<code>knowledge3</code>，它们将分别包含推导谜题所需的知识。</p>
<p>puzzle.py 的主函数在所有谜题上循环，并使用模型检查来计算，给定该谜题的知识并打印出模型检查算法能够得出的任何结论。</p>
<h3 id="目标-3"><a class="markdownIt-Anchor" href="#目标-3"></a> 目标</h3>
<p>将知识添加到知识库中，以解决下列谜题：</p>
<ol>
<li>A 说」我既是骑士也是无赖「</li>
<li>A 说」我们都是骑士「；B 没有说话</li>
<li>A 说「我们是同类人」；B 说「我们是不同类的人」</li>
<li>A 要么说了「我是一个骑士」，要么说了「我是一个无赖」，但是你不知道；B 说「A 说了他是一个无赖」；C 说「A 是一个骑士」</li>
</ol>
<h2 id="作业minesweeper"><a class="markdownIt-Anchor" href="#作业minesweeper"></a> 作业 minesweeper</h2>
<p>扫雷是一个益智游戏，由一个单元格组成，其中一些单元格中隐藏着地雷。点击含有地雷的单元格会引爆地雷，并导致用户输掉游戏。点击一个安全的单元格会显示一个数字，表明有多少个相邻的单元格含有炸弹。</p>
<h3 id="命题逻辑-2"><a class="markdownIt-Anchor" href="#命题逻辑-2"></a> 命题逻辑</h3>
<p>你在这个项目中的目标是建立一个能玩扫雷游戏的人工智能。我们可以用一种方法来表示人工智能对扫雷游戏的了解，那就是让每个单元格成为一个命题变量，如果该单元格含有地雷，则为真，否则就是假。</p>
<p>人工智能会知道每次点击安全的单元格时显示的数字。</p>
<p><img src="/posts/d235/Middle_Safe.png" alt="Middle cell with labeled neighbors"></p>
<p>用上图作为例子，我们知道八个相邻的单元格中会有一个是地雷。因此我们可以写一个像下面这样的逻辑表达式来表示相邻单元格中的一个是地雷：<code>Or(A,B,C,D,E,F,G,H)</code>。</p>
<p>但实际上我们知道的要比这个表达式所说的要多。上面这个逻辑句子表达的是这八个变量中至少有一个是真的，但我们可以做一个比这更有力的声明：我们知道这八个变量中只有一个是真的。那就是：</p>
<figure class="highlight python"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">Or(</span><br><span class="line">    And(A, Not(B), Not(C), Not(D), Not(E), Not(F), Not(G), Not(H)),</span><br><span class="line">    And(Not(A), B, Not(C), Not(D), Not(E), Not(F), Not(G), Not(H)),</span><br><span class="line">    And(Not(A), Not(B), C, Not(D), Not(E), Not(F), Not(G), Not(H)),</span><br><span class="line">    And(Not(A), Not(B), Not(C), D, Not(E), Not(F), Not(G), Not(H)),</span><br><span class="line">    And(Not(A), Not(B), Not(C), Not(D), E, Not(F), Not(G), Not(H)),</span><br><span class="line">    And(Not(A), Not(B), Not(C), Not(D), Not(E), F, Not(G), Not(H)),</span><br><span class="line">    And(Not(A), Not(B), Not(C), Not(D), Not(E), Not(F), G, Not(H)),</span><br><span class="line">    And(Not(A), Not(B), Not(C), Not(D), Not(E), Not(F), Not(G), H)</span><br><span class="line">)</span><br></pre></td></tr></tbody></table></figure>
<p>嗯…… 是不是太复杂了？这只是为了表达一个单元格中有 1。如果单元格中有 2 或者 3 或者其他的值，表达式可能会更长。</p>
<p>试图对这种类型的问题进行模型检查，也会很快变得难以解决：在一个 8x8 的网格上，也就是简单模式会用的尺寸，我们会有 64 个变量，因此有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mn>64</mn></msup></mrow><annotation encoding="application/x-tex">2^{64}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">6</span><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span></span></span> 个可能的模型需要检查。对于一台计算机来说，在任何合理的时间内计算的数量都太多了。对于这个问题，我们需要一个更好的知识来表示。</p>
<h3 id="知识表示"><a class="markdownIt-Anchor" href="#知识表示"></a> 知识表示</h3>
<p>又称知识重呈、知识表现、知识表征……</p>
<p>我们将像这样表示人工智能的每一句知识：<code>{A,B,C,D,E,F,G,H}=1</code>。</p>
<p>这个表达式中的每个逻辑句子都有两个部分：黑板上涉及该句子的一组单元格，以及一个数字计数，代表这个单元格中有多少是地雷的计数。上面的逻辑句子表示了「在这八个单元格中正好有一个是地雷」。</p>
<h3 id="分发代码-4"><a class="markdownIt-Anchor" href="#分发代码-4"></a> 分发代码</h3>
<p>这个项目有两个主要文件：<a target="_blank" rel="noopener" href="http://runner.xn--pyminesweeper-q59v.py">runner.py 和 minesweeper.py</a>。前者已被实现，后者包含了游戏本身和 AI 玩游戏的所有逻辑。</p>
<p>minesweeper.py 定义了三个类：<code>Minesweeper</code>、<code>Sentence</code>、<code>MinesweeperAI</code>。第一个处理游戏的玩法，第二个表示一个逻辑句子，第三个处理根据知识推断出要做的动作。</p>
<p><code>Minesweeper</code> 类已被实现。每个单元格是一对 <code>(i,j)</code>，其中 <code>i</code> 是行号（从 0 到 <code>高度-1</code>），<code>j</code> 是列号（从 0 到 <code>宽度-1</code>）。</p>
<p><code>Sentence</code> 类被用来表示背景中描述的逻辑句子的形式。每个句子中都有一组单元格，以及这些单元格中有多少个地雷的计数。该类还包含函数 <code>known_mines()</code> 和 <code>known_safes()</code> 用于确定句子中的任何单元格是否为已知的地雷或已知的安全区。它还包含了 <code>mark_mine()</code> 和 <code>mark_safe()</code> 用来更新句子，以应对关于一个单元格的新信息。</p>
<p>最后，<code>MinesweeperAI</code> 类将实现一个可以玩扫雷的 AI。这个 AI 类记录了一些数值：</p>
<ul>
<li><code>self.moves_made</code> 包含了一个装有所有已经点击过的单元格的集合，所以 AI 知道不要再去选择那些单元格</li>
<li><code>self.mines</code> 包含了一个装有所有已知是地雷的单元格的集合</li>
<li><code>self.safes</code> 包含了一个装有所有已知是安全的的单元格的集合</li>
<li><code>self.knowledge</code> 包含了一个装有所有人工智能已知为真的句子的列表</li>
</ul>
<p><code>mark_mine()</code> 将一个单元格添加到 <code>self.mines</code> 中。<code>mark_safe()</code> 同理。</p>
<hr>
<h1 id="2-uncertainty"><a class="markdownIt-Anchor" href="#2-uncertainty"></a> 2. Uncertainty</h1>
<p>在现实里，人工智能往往只拥有对世界的部分知识，剩余的空间则都是不确定性（uncertainty）。尽管如此，我们仍希望我们的人工智能在这些情况下做出最佳的决策。</p>
<ul>
<li>例如：在预测天气时，人工智能能拥有今天的天气信息，但无法百分之百准确地预测明天的天气</li>
</ul>
<p>不过我们还是可以在有限信息和不确定性地情况下创建出可以做出最佳决策的人工智能。</p>
<h2 id="概率"><a class="markdownIt-Anchor" href="#概率"></a> 概率</h2>
<p>不确定性可以被表示为一些事件及其发生的可能性或概率。</p>
<h3 id="可能的世界"><a class="markdownIt-Anchor" href="#可能的世界"></a> 可能的世界</h3>
<p>每种可能的情况都可以被看作是一个世界，用小写希腊字母 <code>ω</code> 来表示。</p>
<ul>
<li>例如：投掷骰子时可以产生六个可能的世界</li>
</ul>
<p>为了表示某个世界的概率，我们使用 <code>P(ω)</code>。</p>
<h3 id="概率的公理"><a class="markdownIt-Anchor" href="#概率的公理"></a> 概率的公理</h3>
<p>概率的公式为 <code>0 &lt; P(ω) &lt; 1</code>，每个表示概率的值必须在 0 和 1 之间。0 是不可能发生的事件，比如投掷骰子时得到了点数 7；1 是一定会发生的事件，比如投掷一个标准骰子得到一个小于 10 的点数。通常值越高，事件发生的可能性就越大。每个可能事件的概率加起来等于 1。</p>
<p><img src="/posts/d235/Lotp.png" alt="Summing Probabilities"></p>
<p>用标准骰子掷出一个数字 <code>R</code> 的概率可以表示为 <code>P(R)</code>。在我们的例子中，<code>P(R) = 1/6</code>，因为有六个可能的世界，每个都同样可能发生。现在考虑一下投掷两个骰子的事件，一下就有了 36 种可能的事件。</p>
<p><img src="/posts/d235/36_Events.png" alt="36 Events"></p>
<p>但是，如果我们试图预测两个骰子的和会发生什么？在这种情况下，我们只有 11 个可能的值。</p>
<p><img src="/posts/d235/Sum_Of_Two_Dice.png" alt="Sum of Two Dice"></p>
<p>要得到一个事件的概率，我们要将它发生的世界数除以所有可能的世界数。例如，投掷两个骰子时会有 36 个可能的世界。只有在其中一个世界里，当两个骰子都掷出 6 时，我们才能得到 12 的总和。因此 <code>P(12) = 1/36</code>。</p>
<ul>
<li>例子：<code>P(7)</code> 的概率是多少？7 出现在六个世界中，因此 <code>P(7) = 6/36 = 1/6</code></li>
</ul>
<h3 id="无条件概率"><a class="markdownIt-Anchor" href="#无条件概率"></a> 无条件概率</h3>
<p>无条件概率是在没有其他证据的情况下对一个命题的信度。我们迄今为止提出的所有问题都是无条件概率的问题，因为掷骰子的结果不依赖于先前的事件。</p>
<h2 id="条件概率"><a class="markdownIt-Anchor" href="#条件概率"></a> 条件概率</h2>
<p>条件概率是在已经揭示了一些证据的情况下对一个命题的信度。如前言所述，人工智能可以利用部分信息对未来做出有根据的猜测。为了使用这些信息，它们会影响事件在未来发生的概率，我们依赖于条件概率。</p>
<p>条件概率用 <code>P(a | b)</code> 来表示，意思是「在我们知道事件 b 已经发生的情况下，事件 a 发生的概率」。</p>
<ul>
<li>例如：如果昨天下雨了，今天下雨的概率是多少？ -&gt; <code>P(今天下雨 | 昨天下雨)</code></li>
</ul>
<p><img src="/posts/d235/Conditional.png" alt="Conditional Probability Formula"></p>
<p>换句话说，给定 b 为真的 a 的概率等同于 a 和 b 都为真的概率除以 b 的概率。</p>
<p>一种直观的推理方法是这样的：「我们对 a 和 b 都为真的事件感兴趣（分子），但只来自我们知道 b 为真的世界（分母）」</p>
<p><img src="/posts/d235/Conditional_Equivalent.png" alt="Equivalent Formulas"></p>
<p>计算一下 <code>P(总和为12 | 在骰子上掷出6)</code>。首先我们要把我们的世界限制在第一个骰子的点数为 6 的世界。其次我们要得出在我们限制了问题的世界中，事件 a（总和为 12）发生了多少次（除以 <code>P(b)</code>，即第一个骰子掷出 6 的概率）。</p>
<p><img src="/posts/d235/Sum_Conditional_2.png" alt="Conditioned Probability"></p>
<h2 id="随机变量"><a class="markdownIt-Anchor" href="#随机变量"></a> 随机变量</h2>
<p>随机变量是概率论中具有可能取值域的变量。</p>
<ul>
<li>例如：为了表示掷骰子时的可能结果，我们可以定义一个随机变量 <code>Roll</code>，它可以取值 <code>{0, 1, 2, 3, 4, 5, 6}</code>；为了表示航班的状态，我们可以定义一个变量 <code>Flight</code>，它可以取值 <code>{准时, 延误, 取消}</code></li>
<li>通常我们会对每个值发生的概率感兴趣，这一点可以使用概率分布来表示：
<ul>
<li><code>P(Flight = 准时) = 0.6</code></li>
<li><code>P(Flight = 延误) = 0.3</code></li>
<li><code>P(Flight = 取消) = 0.1</code></li>
</ul>
</li>
<li>概率分布可以更简洁地表示为向量：
<ul>
<li><code>P(Flight) = &lt;0.6, 0.3, 0.1&gt;</code></li>
</ul>
</li>
<li>为了使这种表示法可解释，值必须有一个固定的顺序（在我们的例子里，就是准时、延误、取消）</li>
</ul>
<h3 id="独立性"><a class="markdownIt-Anchor" href="#独立性"></a> 独立性</h3>
<p>独立性指的是一个事件的发生不影响另一个事件的概率。</p>
<ul>
<li>例如：当投掷两个骰子时，每个骰子的结果都与另一个骰子独立。这与依赖事件相反，比如早上的云和下午的雨（如果早上多云，那么下午下雨的可能性就更大）</li>
</ul>
<p>独立性可以用数学定义：当且仅当 a 和 b 的概率等于 a 的概率乘以 b 的概率时，事件 a 和 b 是独立的：<code>P(a ∧ b) = P(a)P(b)</code>。</p>
<h2 id="贝叶斯定理"><a class="markdownIt-Anchor" href="#贝叶斯定理"></a> 贝叶斯定理</h2>
<p>贝叶斯定理通常用于概率论中计算条件概率。给定 a 的 b 的概率等于给定 b 的 a 的概率乘以 b 的概率，除以 a 的概率。</p>
<p><img src="/posts/d235/Bayes_Rule.png" alt="Bayes' Rule"></p>
<ul>
<li>例如：计算如果早上有云，下午下雨的概率（也就是 <code>P(雨 | 云)</code>）
<ul>
<li>80% 的下午下雨始于早晨的多云，即 <code>P(云 | 雨)</code></li>
<li>40% 的日子是早上多云，即 <code>P(云)</code></li>
<li>10% 的日子是下午下雨，即 <code>P(雨)</code></li>
</ul>
</li>
<li>应用贝叶斯定理，<code>(0.1)(0.8)/(0.4) = 0.2</code>。也就是说，如果早上多云，那么下午下雨的概率为 20%</li>
</ul>
<p>知道了 <code>P(a | b)</code> 后还可以让我们计算出 <code>P(b | a)</code>。知道一个可见效果给定一个未知原因的条件概率（<code>P(可见效果 | 未知原因)</code>）可以让我们计算出未知原因给定可见效果的概率（<code>P(未知原因 | 可见效果)</code>）。</p>
<ul>
<li>例如：我们可以通过医学试验来了解 <code>P(医学检查结果 | 疾病)</code>，在那里我们测试患有疾病的人并看看测试多久能检测到。知道这一点，我们可以计算出 <code>P(疾病 | 医学检查结果)</code>，即宝贵的诊断信息</li>
</ul>
<h2 id="联合概率"><a class="markdownIt-Anchor" href="#联合概率"></a> 联合概率</h2>
<p>联合概率是多个事件都发生的可能性。考虑一下关于早上多云和下午下雨的概率的例子：</p>
<ul>
<li><code>C = cloud</code>，0.4</li>
<li><code>C = ¬cloud</code>，0.6</li>
<li><code>R = rain</code>，0.1</li>
<li><code>R = ¬rain</code>，0.9</li>
</ul>
<p>我们无法说早上多云是否与下午下雨的可能性有关。为了能够这样做，我们需要看两个变量的所有可能结果的联合概率：</p>
<table>
<thead>
<tr>
<th></th>
<th><code>C = cloud</code></th>
<th><code>C = ¬cloud</code></th>
</tr>
</thead>
<tbody>
<tr>
<td><code>R = rain</code></td>
<td>0.08</td>
<td>0.02</td>
</tr>
<tr>
<td><code>R = ¬rain</code></td>
<td>0.32</td>
<td>0.58</td>
</tr>
</tbody>
</table>
<p>使用联合概率，我们可以推导出条件概率。</p>
<ul>
<li>例如：我们对下午下雨时早上多云的概率分布感兴趣。<code>P(C | 雨) = P(C, 雨)/P(雨)</code>（在概率中，逗号和 <code>∧</code> 可以互换使用）
<ul>
<li>在最后一个方程中，可以将 <code>P(雨)</code> 视为乘以 <code>P(C, 雨)</code> 的某个常数</li>
<li>因此我们可以重写 <code>P(C, 雨)/P(雨) = αP(C, 雨)</code> 或 <code>α&lt;0.08, 0.02&gt;</code></li>
<li>提取 <code>α</code> 后，我们得到了 <code>C</code> 在下午下雨时可能值的概率比例</li>
<li>也就是说，如果下午下雨，那么早上多云和早上没有云的概率比例是 <code>0.08 : 0.02</code>
<ul>
<li>注意 0.08 和 0.02 并不加起来等于 1；然而，由于这是随机变量 C 的概率分布，我们知道它们应该加起来等于 1</li>
<li>因此，我们需要通过计算 α 使 <code>α0.08 + α0.02 = 1</code> 来归一化这些值。最后，我们可以说 <code>P(C | 雨) = &lt;0.8, 0.2&gt;</code></li>
</ul>
</li>
</ul>
</li>
</ul>
<h2 id="概率规则"><a class="markdownIt-Anchor" href="#概率规则"></a> 概率规则</h2>
<ul>
<li>
<p>否定：<code>P(¬a) = 1 - P(a)</code></p>
<ul>
<li>源于所有可能的世界的概率总和为 1，而补充文字 <code>a</code> 和 <code>¬a</code> 包括了所有的可能的世界</li>
</ul>
</li>
<li>
<p>容斥：<code>P(a ∨ b) = P(a) + P(b) - P(a ∧ b)</code></p>
<ul>
<li><code>a</code> 或 <code>b</code> 为真的世界等于所有 <code>a</code> 为真的世界加上 <code>b</code> 为真的世界</li>
<li>然而在这种情况下，有些世界会被多次计算（即 <code>a</code> 和 <code>b</code> 都为真的世界）。为了消除这种重叠，我们减去一次 <code>a</code> 和 <code>b</code> 都为真的世界
<ul>
<li>例如：我有 80% 的时间吃冰淇淋、70% 的时间吃饼干。如果我们在计算今天吃冰淇淋或饼干 <code>P(冰淇淋 ∨ 饼干)</code> 时不减去 <code>P(冰淇淋 ∧ 饼干)</code>，我们就会错误地得到 <code>0.7 + 0.8 = 1.5</code>，这与概率在 0 和 1 之间的公理相互矛盾</li>
</ul>
</li>
</ul>
</li>
<li>
<p>边缘化：<code>P(*a*) = P(*a, b*) + P(*a, ¬b*)</code></p>
<ul>
<li>
<p><code>b</code> 和 <code>¬b</code> 是不相交的概率，或者说，<code>b</code> 和 <code>¬b</code> 同时发生的概率是 0。我们也知道 <code>b</code> 和 <code>¬b</code> 加起来是 1。因此当 <code>a</code> 发生时，<code>b</code> 可以发生也可以不发生。当我们取 <code>a</code> 和 <code>b</code> 时发生的概率加上 <code>a</code> 和 <code>¬b</code> 同时发生的概率时，我们最终得到了 <code>a</code> 的概率</p>
</li>
<li>
<p><img src="/posts/d235/Marginalization.png" alt="Marginalization"></p>
<p>这个方程的左边意味着」随机变量 <code>X</code> 取值为 <code>xᵢ</code> 的概率「</p>
<ul>
<li>例如：对于我们前面提到的变量 <code>C</code>，两个可能的值分别是早上多云和早上没云</li>
</ul>
<p>方程的右边则是」<code>xᵢ</code> 和随机变量 <code>Y</code> 的每个值的所有联合概率之和「</p>
<ul>
<li>例如：<code>P(C = 多云) = P(C = 多云, R = 下雨) + P(C = 多云, R = ¬下雨) = 0.08 + 0.32 = 0.4</code></li>
</ul>
</li>
</ul>
</li>
<li>
<p>条件化：<code>P(a) = P(a | b)P(b) + P(a | ¬b)P(¬b)</code></p>
<ul>
<li>
<p>与边缘化相似，事件 <code>a</code> 发生的概率等于给定 <code>b</code> 的 <code>a</code> 的概率乘以 <code>b</code> 的概率，加上给定 <code>¬b</code> 的 <code>a</code> 的概率乘以 <code>¬b</code> 的概率</p>
</li>
<li>
<p><img src="/posts/d235/Conditioning.png" alt="Conditioning"></p>
<p>随机变量 <code>X</code> 以概率等于 <code>xᵢ</code> 给定随机变量 <code>Y</code> 的每个值的概率之和乘以变量 <code>Y</code> 取该值的概率。记住 <code>P(a | b) = P(a, b)/P(b)</code>，如果我们将这个表达式乘以 <code>P(b)</code>，我们就会得到 <code>P(a, b)</code>，之后的步骤便和边缘化一样</p>
</li>
</ul>
</li>
</ul>
<h2 id="贝叶斯网络"><a class="markdownIt-Anchor" href="#贝叶斯网络"></a> 贝叶斯网络</h2>
<p>贝叶斯网络是一种表示随机变量之间依赖关系的数据结构，其特性如下：</p>
<ul>
<li>是有向图，图上的每个节点都代表一个随机变量</li>
<li>从 X 到 Y 的箭头表示 X 是 Y 的父节点，即 Y 的概率分布取决于 X 的值</li>
<li>每个节点 X 都有概率分布 <code>P(X | Parents(X))</code></li>
</ul>
<p>考虑这个例子，它涉及影响了我们是否按时赴约的变量：</p>
<p><img src="/posts/d235/Bayesian_Network.png" alt="Bayesian Network"></p>
<ul>
<li>
<p><code>Rain</code> 是这个网络中的根节点。这意味着它的概率分布不依赖于任何先前的事件。在我们的例子中，<code>Rain</code> 是一个随机变量，可以取值 <code>{none, light, heavy}</code>，具有以下概率分布：</p>
<table>
<thead>
<tr>
<th>值</th>
<th>概率</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>none</code></td>
<td>0.7</td>
</tr>
<tr>
<td><code>light</code></td>
<td>0.2</td>
</tr>
<tr>
<td><code>heavy</code></td>
<td>0.1</td>
</tr>
</tbody>
</table>
</li>
<li>
<p>在我们的例子中，<code>Maintenance</code> 编码是否有火车轨道维护，取值 <code>{yes, no}</code>。<code>Rain</code> 是 <code>Maintenance</code> 的父节点，这意味着 <code>Maintenance</code> 的概率分布受 <code>Rain</code> 的影响</p>
<table>
<thead>
<tr>
<th></th>
<th><code>none</code></th>
<th><code>light</code></th>
<th><code>heavy</code></th>
</tr>
</thead>
<tbody>
<tr>
<td><code>yes</code></td>
<td>0.4</td>
<td>0.2</td>
<td>0.1</td>
</tr>
<tr>
<td><code>no</code></td>
<td>0.6</td>
<td>0.8</td>
<td>0.9</td>
</tr>
</tbody>
</table>
</li>
<li>
<p><code>Train</code> 变量编码火车是否准时或延误，取值 <code>{on time, delayed}</code>。注意，<code>Maintenance</code> 和 <code>Rain</code> 都有箭头指向 <code>Train</code>，这意味着它们都是 <code>Train</code> 的父节点，它们的值会影响 <code>Train</code> 的概率分布</p>
<table>
<thead>
<tr>
<th></th>
<th><code>none</code> + <code>yes</code></th>
<th><code>none</code> + <code>no</code></th>
<th><code>light</code> + <code>yes</code></th>
<th><code>light</code> + <code>no</code></th>
<th><code>heavy</code> + <code>yes</code></th>
<th><code>heavy</code> + <code>no</code></th>
</tr>
</thead>
<tbody>
<tr>
<td><code>on time</code></td>
<td>0.8</td>
<td>0.9</td>
<td>0.6</td>
<td>0.7</td>
<td>0.4</td>
<td>0.5</td>
</tr>
<tr>
<td><code>delayed</code></td>
<td>0.2</td>
<td>0.1</td>
<td>0.4</td>
<td>0.3</td>
<td>0.6</td>
<td>0.5</td>
</tr>
</tbody>
</table>
</li>
<li>
<p><code>Appointment</code> 是一个随机变量，代表我们是否出席了预约，取值 <code>{attend, miss}</code>。它的唯一父节点是 <code>Train</code></p>
<ul>
<li>
<p>根据贝叶斯网络，父节点只包括直接关系。<code>Maintenance</code> 确实会影响 <code>Train</code> 是否准时，而 <code>Train</code> 是否准时会影响到我们是否出席了预约。然而，最终直接影响我们出席预约的机会的是火车是否准时到达</p>
<ul>
<li>例如：如果火车准时到达，那么即使下大雨并且轨道在维修，也不会影响我们是否赶上预约</li>
</ul>
<table>
<thead>
<tr>
<th></th>
<th><code>on time</code></th>
<th><code>delayed</code></th>
</tr>
</thead>
<tbody>
<tr>
<td><code>attend</code></td>
<td>0.9</td>
<td>0.6</td>
</tr>
<tr>
<td><code>miss</code></td>
<td>0.1</td>
<td>0.4</td>
</tr>
</tbody>
</table>
<ul>
<li>例如：如果我们想要找到在没有维修、没有下雨的一天，火车晚点时错过预约的概率，也就是 <code>P(light, no, delayed, miss)</code>，我们将计算以下内容：
<ul>
<li><code>P(light)P(no | light)P(delayed | light, no)P(miss | delayed)</code></li>
<li>每个单独概率的值都可以在上面的概率分布中找到，然后将这些值相乘就能得到 <code>P(no, light, delayed, miss)</code></li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="推理-2"><a class="markdownIt-Anchor" href="#推理-2"></a> 推理</h3>
<p>早些时候我们通过蕴涵来推理，意味着我们可以根据我们已有的信息明确地得出新信息，也可以根据概率推断新信息。虽然这无法让我们确定新信息，但可以让我们找出某些值地概率分布。</p>
<p>推理具有多个属性：</p>
<ul>
<li>
<p>查询变量 X：我们想要计算概率分布的变量</p>
</li>
<li>
<p>证据变量 E：一个或多个一观察到的事件 <code>e</code> 的变量</p>
<ul>
<li>例如：我们可能观察到有轻微的雨。这个观察帮助我们计算火车延迟的概率</li>
</ul>
</li>
<li>
<p>隐藏变量 Y：不是查询变量，也没有被观察过的变量</p>
<ul>
<li>例如：在火车站台上，我们可以观察到是否在下雨，但是无法得知路的下方是否有维修工作。因此在这种情况下，维修工作是一个隐藏变量</li>
</ul>
</li>
<li>
<p>目标：计算 <code>P(X | e)</code></p>
<ul>
<li>例如：给予我们知道有轻微的雨的证据变量 E，计算火车变量（查询变量）的概率分布</li>
</ul>
</li>
</ul>
<p>举个例子，我们想要计算在有轻微的雨和没有轨道维修的证据下、预约变量的概率分布。也就是说，我们知道有轻微的雨并且没有轨道维修，我们想要确定我们参加预约和错过预约的概率分别是多少，也就是 <code>P(预约 | 有雨，无维修)</code>。根据联合概率部分，我们知道我们可以将预约随机变量的可能值表示为一个比例，将 <code>P(预约 | 有雨，无维修)</code> 重写为 <code>αP(预约，有雨，无维修)</code>。如果预约的父节点只有火车变量，而没有雨或者维修，我们该如何计算预约的概率分布？</p>
<p>在这里，我们将使用边缘化。<code>P(预约，有雨，无维修)</code> 的值等同于 <code>α[P(预约，有雨，无维修，延误) + P(预约，有雨，无维修，准时)]</code>。</p>
<h3 id="枚举推理"><a class="markdownIt-Anchor" href="#枚举推理"></a> 枚举推理</h3>
<p>枚举推理是一种根据观察到的证据 <code>e</code> 和一些隐藏变量 <code>Y</code> 来找到变量 <code>X</code> 的概率分布的过程。</p>
<p><img src="/posts/d235/Inference_By_Enumeration.png" alt="Inference by Enumeration"></p>
<p>在这个方程中，<code>X</code> 代表查询变量，<code>e</code> 代表观察到的证据，<code>y</code> 代表所有隐藏变量的值，<code>α</code> 对结果进行归一化，使得我们得到的概率总和为 1。</p>
<p>用文字解释这个方程，它表示给定 <code>e</code> 的情况下 <code>X</code> 的概率分布等于 <code>X</code> 和 <code>e</code> 的归一化概率分布。为了得到这个分布，我们对 <code>X</code>、<code>e</code> 和 <code>y</code> 的归一化概率求和，其中 <code>y</code> 每次取隐藏变量 <code>Y</code> 的不同值。</p>
<p>Python 中存在多个库以简化概率推理的过程。我们将使用 pomegranate 库来看看如何将上述数据表示为代码：</p>
<ol>
<li>
<p>创建节点并为每个节点提供概率分布</p>
<figure class="highlight python"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">from</span> pomegranate <span class="keyword">import</span> *</span><br><span class="line"></span><br><span class="line"><span class="comment"># 雨节点没有父节点</span></span><br><span class="line">rain = Node(DiscreteDistribution({</span><br><span class="line">    <span class="string">"none"</span>: <span class="number">0.7</span>,</span><br><span class="line">    <span class="string">"light"</span>: <span class="number">0.2</span>,</span><br><span class="line">    <span class="string">"heavy"</span>: <span class="number">0.1</span></span><br><span class="line">}), name=<span class="string">"rain"</span>)</span><br><span class="line"></span><br><span class="line"><span class="comment"># 轨道维修节点是基于雨的条件概率</span></span><br><span class="line">maintenance = Node(ConditionalProbabilityTable([</span><br><span class="line">    [<span class="string">"none"</span>, <span class="string">"yes"</span>, <span class="number">0.4</span>],</span><br><span class="line">    [<span class="string">"none"</span>, <span class="string">"no"</span>, <span class="number">0.6</span>],</span><br><span class="line">    [<span class="string">"light"</span>, <span class="string">"yes"</span>, <span class="number">0.2</span>],</span><br><span class="line">    [<span class="string">"light"</span>, <span class="string">"no"</span>, <span class="number">0.8</span>],</span><br><span class="line">    [<span class="string">"heavy"</span>, <span class="string">"yes"</span>, <span class="number">0.1</span>],</span><br><span class="line">    [<span class="string">"heavy"</span>, <span class="string">"no"</span>, <span class="number">0.9</span>]</span><br><span class="line">], [rain.distribution]), name=<span class="string">"maintenance"</span>)</span><br><span class="line"></span><br><span class="line"><span class="comment"># 火车节点是基于雨和维修的条件概率</span></span><br><span class="line">train = Node(ConditionalProbabilityTable([</span><br><span class="line">    [<span class="string">"none"</span>, <span class="string">"yes"</span>, <span class="string">"on time"</span>, <span class="number">0.8</span>],</span><br><span class="line">    [<span class="string">"none"</span>, <span class="string">"yes"</span>, <span class="string">"delayed"</span>, <span class="number">0.2</span>],</span><br><span class="line">    [<span class="string">"none"</span>, <span class="string">"no"</span>, <span class="string">"on time"</span>, <span class="number">0.9</span>],</span><br><span class="line">    [<span class="string">"none"</span>, <span class="string">"no"</span>, <span class="string">"delayed"</span>, <span class="number">0.1</span>],</span><br><span class="line">    [<span class="string">"light"</span>, <span class="string">"yes"</span>, <span class="string">"on time"</span>, <span class="number">0.6</span>],</span><br><span class="line">    [<span class="string">"light"</span>, <span class="string">"yes"</span>, <span class="string">"delayed"</span>, <span class="number">0.4</span>],</span><br><span class="line">    [<span class="string">"light"</span>, <span class="string">"no"</span>, <span class="string">"on time"</span>, <span class="number">0.7</span>],</span><br><span class="line">    [<span class="string">"light"</span>, <span class="string">"no"</span>, <span class="string">"delayed"</span>, <span class="number">0.3</span>],</span><br><span class="line">    [<span class="string">"heavy"</span>, <span class="string">"yes"</span>, <span class="string">"on time"</span>, <span class="number">0.4</span>],</span><br><span class="line">    [<span class="string">"heavy"</span>, <span class="string">"yes"</span>, <span class="string">"delayed"</span>, <span class="number">0.6</span>],</span><br><span class="line">    [<span class="string">"heavy"</span>, <span class="string">"no"</span>, <span class="string">"on time"</span>, <span class="number">0.5</span>],</span><br><span class="line">    [<span class="string">"heavy"</span>, <span class="string">"no"</span>, <span class="string">"delayed"</span>, <span class="number">0.5</span>],</span><br><span class="line">], [rain.distribution, maintenance.distribution]), name=<span class="string">"train"</span>)</span><br><span class="line"></span><br><span class="line"><span class="comment"># 预约节点是基于火车的条件概率</span></span><br><span class="line">appointment = Node(ConditionalProbabilityTable([</span><br><span class="line">    [<span class="string">"on time"</span>, <span class="string">"attend"</span>, <span class="number">0.9</span>],</span><br><span class="line">    [<span class="string">"on time"</span>, <span class="string">"miss"</span>, <span class="number">0.1</span>],</span><br><span class="line">    [<span class="string">"delayed"</span>, <span class="string">"attend"</span>, <span class="number">0.6</span>],</span><br><span class="line">    [<span class="string">"delayed"</span>, <span class="string">"miss"</span>, <span class="number">0.4</span>]</span><br><span class="line">], [train.distribution]), name=<span class="string">"appointment"</span>)</span><br></pre></td></tr></tbody></table></figure>
</li>
<li>
<p>通过添加所有节点来创建模型，然后通过在它们之间添加边来描述哪个节点是哪个其他节点的父节点（贝叶斯网络）</p>
<figure class="highlight python"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 创建一个贝叶斯网络并添加状态</span></span><br><span class="line">model = BayesianNetwork()</span><br><span class="line">model.add_states(rain, maintenance, train, appointment)</span><br><span class="line"></span><br><span class="line"><span class="comment"># 给节点之间添加用来连接的边</span></span><br><span class="line">model.add_edge(rain, maintenance)</span><br><span class="line">model.add_edge(rain, train)</span><br><span class="line">model.add_edge(maintenance, train)</span><br><span class="line">model.add_edge(train, appointment)</span><br><span class="line"></span><br><span class="line"><span class="comment"># 最终确定模型</span></span><br><span class="line">model.bake()</span><br></pre></td></tr></tbody></table></figure>
</li>
<li>
<p>为了询问某个事件的概率有多大，我们使用我们感兴趣的值来运行模型。在这个例子中，我们想要问的是没有雨、没有轨道维修、火车准时到达并且我们准点参加会议的概率是多少</p>
<figure class="highlight python"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 基于提供的观察，计算概率</span></span><br><span class="line">probability = model.probability([[<span class="string">"none"</span>, <span class="string">"no"</span>, <span class="string">"on time"</span>, <span class="string">"attend"</span>]])</span><br><span class="line"></span><br><span class="line"><span class="built_in">print</span>(probability)</span><br></pre></td></tr></tbody></table></figure>
</li>
<li>
<p>否则我们可以使用该程序在给定一些观察到的证据时提供所有变量的概率分布。在下面的情况中，我们知道火车延误了。根据这个信息，我们计算并打印变量 <code>Rain</code>、<code>Maintenance</code> 和 <code>Appointment</code> 的概率分布</p>
<figure class="highlight python"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 基于火车延误的证据进行预测计算</span></span><br><span class="line">predictions = model.predict_proba({</span><br><span class="line">    <span class="string">"train"</span>: <span class="string">"delayed"</span></span><br><span class="line">})</span><br><span class="line"></span><br><span class="line"><span class="comment"># 打印每个节点的预测结果</span></span><br><span class="line"><span class="keyword">for</span> node, prediction <span class="keyword">in</span> <span class="built_in">zip</span>(model.states, predictions):</span><br><span class="line">    <span class="keyword">if</span> <span class="built_in">isinstance</span>(prediction, <span class="built_in">str</span>):</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">f"<span class="subst">{node.name}</span>: <span class="subst">{prediction}</span>"</span>)</span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">f"<span class="subst">{node.name}</span>"</span>)</span><br><span class="line">        <span class="keyword">for</span> value, probability <span class="keyword">in</span> prediction.parameters[<span class="number">0</span>].items():</span><br><span class="line">            <span class="built_in">print</span>(<span class="string">f"    <span class="subst">{value}</span>: <span class="subst">{probability:<span class="number">.4</span>f}</span>"</span>)</span><br></pre></td></tr></tbody></table></figure>
</li>
</ol>
<p>上述代码使用了枚举推理。然而这种计算概率的方式是低效的，特别是当模型中有许多变量时。另一种方法是放弃精确推理，转而采用近似推理。通过这样做，我们在生成的概率中失去了一些精度，但通常这种不精确性是可以忽略的。相反我们获得了一种可扩展的计算概率的方法。</p>
</body></html></div></article></div></main><footer><div class="paginator"><a class="prev" href="9e+71.html">上一篇</a><a class="next" href="2abc.html">下一篇</a></div><!-- Webmention 显示区域--><div class="webmention-section webmention-empty" data-page-url="posts/d235.html" data-full-url="https://cytrogen.icu/posts/d235.html" data-mode="static">
              <h3 class="webmention-title">Webmentions (<span class="webmention-count">0</span>)</h3>
              <div class="webmention-list"></div>
              <span>暂无 Webmentions</span>
            </div><div class="copyright"><p class="footer-links"><a href="../friends/index.html">友链</a><span class="footer-separator"> ·</span><a href="../links/index.html">邻邦</a><span class="footer-separator"> ·</span><a href="../contact/index.html">联络</a><span class="footer-separator"> ·</span><a href="../colophon/index.html">营造记</a><span class="footer-separator"> ·</span><a href="../atom.xml">RSS订阅</a></p><p>© 2025 - 2026 <a href="https://cytrogen.icu">Cytrogen</a>, powered by <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/cytrogen/hexo-theme-ares" target="_blank">hexo-theme-ares</a>.</p><p><a href="https://blogscn.fun" target="_blank" rel="noopener">BLOGS·CN</a></p></div></footer></div></div><a class="back-to-top" href="#top" aria-label="返回顶部"><svg width="20" height="20" viewBox="0 0 20 20" fill="currentColor" aria-hidden="true"><path d="M3.293 9.707a1 1 0 010-1.414L9.586 2a2 2 0 012.828 0l6.293 6.293a1 1 0 01-1.414 1.414L11 3.414V17a1 1 0 11-2 0V3.414L2.707 9.707a1 1 0 01-1.414 0z"></path></svg></a><script>document.addEventListener('DOMContentLoaded', function() {
  const codeBlocks = document.querySelectorAll('figure.highlight');
  
  codeBlocks.forEach(block => {
    let caption = block.querySelector('figcaption');
    if (!caption) {
      caption = document.createElement('figcaption');
      block.insertBefore(caption, block.firstChild);
    }

    const info = document.createElement('div');
    info.className = 'info';
    
    const filename = caption.querySelector('span');
    if (filename) {
      filename.className = 'filename';
      info.appendChild(filename);
    }
    
    const lang = block.className.split(' ')[1];
    if (lang) {
      const langSpan = document.createElement('span');
      langSpan.className = 'lang-name';
      langSpan.textContent = lang;
      info.appendChild(langSpan);
    }

    const sourceLink = caption.querySelector('a');
    if (sourceLink) {
      sourceLink.className = 'source-link';
      info.appendChild(sourceLink);
    }

    const actions = document.createElement('div');
    actions.className = 'actions';

    const codeHeight = block.scrollHeight;
    const threshold = 300;

    if (codeHeight > threshold) {
      block.classList.add('folded');
      
      const toggleBtn = document.createElement('button');
      toggleBtn.textContent = '展开';
      toggleBtn.addEventListener('click', () => {
        block.classList.toggle('folded');
        toggleBtn.textContent = block.classList.contains('folded') ? '展开' : '折叠';
      });
      actions.appendChild(toggleBtn);
    }

    const copyBtn = document.createElement('button');
    copyBtn.textContent = '复制';
    copyBtn.addEventListener('click', async () => {
      const codeLines = block.querySelectorAll('.code .line');
      const code = Array.from(codeLines)
        .map(line => line.textContent)
        .join('\n')
        .replace(/\n\n/g, '\n');
      
      try {
        await navigator.clipboard.writeText(code);
        copyBtn.textContent = '已复制';
        copyBtn.classList.add('copied');
        
        setTimeout(() => {
          copyBtn.textContent = '复制';
          copyBtn.classList.remove('copied');
        }, 3000);
      } catch (err) {
        console.error('复制失败:', err);
        copyBtn.textContent = '复制失败';
        
        setTimeout(() => {
          copyBtn.textContent = '复制';
        }, 3000);
      }
    });
    actions.appendChild(copyBtn);

    caption.innerHTML = '';
    caption.appendChild(info);
    caption.appendChild(actions);

    const markedLines = block.getAttribute('data-marked-lines');
    if (markedLines) {
      const lines = markedLines.split(',');
      lines.forEach(range => {
        if (range.includes('-')) {
          const [start, end] = range.split('-').map(Number);
          for (let i = start; i <= end; i++) {
            const line = block.querySelector(`.line-${i}`);
            if (line) line.classList.add('marked');
          }
        } else {
          const line = block.querySelector(`.line-${range}`);
          if (line) line.classList.add('marked');
        }
      });
    }
  });
});</script><script async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js" id="MathJax-script"></script><script>(function() {
  document.addEventListener('DOMContentLoaded', function() {
    const themeToggle = document.querySelector('.theme-toggle');
    
    if (!themeToggle) return;
    
    const getCurrentTheme = () => {
      return document.documentElement.getAttribute('data-theme') || 'light';
    };
    
    const updateUI = (theme) => {
      const isDark = theme === 'dark';
      themeToggle.setAttribute('aria-pressed', isDark.toString());
    };
    
    const setTheme = (theme) => {
      document.documentElement.setAttribute('data-theme', theme);
      document.documentElement.style.colorScheme = theme;
      
      const pageWrapper = document.getElementById('page-wrapper');
      if (pageWrapper) {
        pageWrapper.setAttribute('data-theme', theme);
      }
      
      // Find and remove the temporary anti-flicker style tag if it exists.
      // This ensures the main stylesheet takes full control after the initial load.
      const antiFlickerStyle = document.getElementById('anti-flicker-style');
      if (antiFlickerStyle) {
        antiFlickerStyle.remove();
      }
      
      localStorage.setItem('theme', theme);
      updateUI(theme);
    };
    
    const toggleTheme = () => {
      const current = getCurrentTheme();
      const newTheme = current === 'light' ? 'dark' : 'light';
      setTheme(newTheme);
    };
    
    updateUI(getCurrentTheme());
    
    themeToggle.addEventListener('click', toggleTheme);
    
    if (window.matchMedia) {
      const mediaQuery = window.matchMedia('(prefers-color-scheme: dark)');
      mediaQuery.addEventListener('change', function(e) {
        if (!localStorage.getItem('theme')) {
          const theme = e.matches ? 'dark' : 'light';
          setTheme(theme);
        }
      });
    }
  });
})();
</script><script src="../js/details-toggle.js" defer></script><script>(function() {
  document.addEventListener('DOMContentLoaded', function() {
    const backToTopBtn = document.querySelector('.back-to-top');
    
    if (!backToTopBtn) return;
    
    const toggleButtonVisibility = () => {
      const scrollTop = window.pageYOffset || document.documentElement.scrollTop;
      const shouldShow = scrollTop > 200;
      
      if (shouldShow) {
        backToTopBtn.classList.add('is-visible');
      } else {
        backToTopBtn.classList.remove('is-visible');
      }
    };
    
    let ticking = false;
    const handleScroll = () => {
      if (!ticking) {
        requestAnimationFrame(() => {
          toggleButtonVisibility();
          ticking = false;
        });
        ticking = true;
      }
    };
    
    const scrollToTop = (event) => {
      event.preventDefault();
      window.scrollTo({
        top: 0,
        behavior: 'smooth'
      });
    };
    
    window.addEventListener('scroll', handleScroll);
    backToTopBtn.addEventListener('click', scrollToTop);
    
    toggleButtonVisibility();
  });
})();</script></body></html>