қ . Қғ ғ ө , қ қ ғ қ ққ ғ қ. , ғң қ ө, ұ ғ ұ ңң ғ қғ қ ө . ң ққ.
1. ғ ү . ғ құ қ. (.19 ) ө қң ә .
қ қ қ қ -қ ө ә қ қ ұ. әң қ ә қ ә ғ қ . ң 19 ө.
ұ ү ( ғ ө).
2. ғ (ұ) . ңғ ( ә ұ ) қ қ қ ә ққ ә . ң ә ғ ң ң қ қ ққ ғ ң ғ . , ң ә ғ ғ ү , ққ ғ ү .
19ࠠ 19
ң қ ққ ң құ құң ғ ұ. ү ғ :
,
ұғ - ғғ өң ң ә - ғ . ә ң қ. қ қ ғ ң .
ғ ққ ұқ 8 () ү қ. 8 қ ғ ңғғ ө ң (қ, ққ) .
|
|
1
2 | 8 | 3 | 1 | 2 | 3 | |
1 | 6 | 4 | → | 8 | * | 4 |
7 | * | 5 | 7 | 6 | 5 |
ғ ққ:
ұғ - ; - ң ққ ө ә ққғң қ; - қ ң (ұ ұ, ұ+2 ; ғ ұ+1; қ ғ ұ 0).
ғ 2 ө.
2. ғ
ғ h | құ (ұғ) L | ғ ө N | ү ң ө ң қ h S | |
5 >18 | 13 100-8!(=40320) | 8 | өң | |
5 18 | 11 43 | 8*2+8+1+1 | ң |
ғ қ ғ .
ң ғ ң құ.
h 1 өң ққ қ ғ . өң ө ө ғ .
ң h 2 ғ 3 S (n) қ қ ә ғ ә ңғ ө ғ ү ( өң ). ң ңғ құғ өң ғ .
ң қ ң ғ, ғ, ңң ө ққ ң қ ү өң ө ұқ. ң қ қғ , ұғ K ә S (ө ң қ ) ғ ә, L ң ұғ, N ғ ө . ү , .
.
20.
ә , ғ ә ү ққ :
ө , ә қ ң, ү. ә ң ғ max Pi ң . ҳ қ ә ұққ ғ қғ ә қ қ ғ қ ү ү . қ, ұ ә ө ү ғ.
|
|
--. , ұ қ ң-ң , ң ө әқ ә ә ғ, қ , ө ғң ү ө ү ғ. ұ ң .ң α ә β (1961 ).
әң қ қ ң ү ғ ң қ ғ қғ ү ң қ ғ ғ ұ. қғ ғ қ ө . 21 қ ө ң ққ. қ ғ ә α ғң ә қ. Y ү ғ ә ғ z ң Z ә . . Z ү ғ қ ә, Y ү ғ ғ қ қ (-қ ө).
21. Қ ө
ң ң қ, S ң қ ққ Z ү ү , қ ү β ғң ә қ.
Қ ү ғ β ә қ β қ ө . α ә β ө ғ ә ө ү ә қ үң ғ қ құ. ң ұ ө +∞ ә -∞ ә , ғ ү ө қ ғ ә қң ү ң қ ү .
α ә β ұ:
) M ө α ә қ ә ң ө ү қғ ә ң ү ә ң;
) MIN ө β ә қ ә ң ө ү қғ ә ң ә ң.
қ :
) қ MIN ө ө, ң қ қ MAX өң β ә α ә ғ ү ;
) қ M ө ө, ң қ қ MAX өң α ә β ә ғ ү .
22- қ ү α-β қ ө. , α-β- ә ә , қ .
22.
қ ққ (, ) Ә, ұ ү ү . ғ қ ғ ~ 1040 ө, ~ 10120 ө ұ. ғ ө ү 1/3 қ , қ ү 1021 ғ қ қ . ұ ғ ғғ ң ө ұқ ө ң ққ ә ө қ ғ қң .
|
|
ғ қғ ң ө ., . , . ң GPS ғ ғ. GPS ұ қ ә ө: қ қ ғ; ғ қ ә қ (, ә ..). ү , ұ қ.
STRIPS (Stanford Research Institut Problem Solver) ғ қғ ққ әң ә ә өң. ғ ңғ ә қғ қ. ғ, ң 1974 ә ң қ қ ғ ұқ қ ә ө ә ү . ң ә қ HACHER ғ қ қғ.
ә. қ қ ү қ . ққ ұ ң ұ қ ғ ү ө ң. қ ғғ ұ ү ә қ ң қ ү. ғ ғ қ ә қ .
ϳ ққғ ғғ ғ ң ә ә () . , ң ққғ ә ә. ., ққ, - ., ғ. ұ қ: ү (), Q ()-ң . : . ққғ ғ ң ққғ ө ң-ң ққ ( ұ құғ - Қ) .
қ . ққ, ә ққ , ққ қ қ ө , modus ponens :
|
|
қң ү қ ү () , қң қ. ұ қ ғ үң ң құ: ққ ү әқ ққ қ ғ. ә қ ғ құ ө үң . Қң қ ү .
Modus tollendo tollens: ә ғ, ғ.
Modus ponendo tollens: ә қ ққ ә ққ , ғ.
Modus tollendo ponens: , ққ ә ққ , ққ.
F 1, F 2 F n ұ () ү ұ. ң қ ұ ү , ң ә ү ғ ғғ , ң F 1, F 2 F n қ қ қғ . ұ қ ғқ (ң-ң ққ) ң
F 1& F 2&& F n
ә (ң-ң ғ) ң
F 1& F 2&& F n
ң.
ә ә ғ ңғ, ғ ә. әң қ қ ғ қ . modus ponens ү ө қ ғ қ . қ ү ө ғ , ғ ү ұ. қ ә , ң ү.
:
, 1 , Q , 2- . : ә, .
ң ғ :
&
, 1 , 2- . қ 䳻 .
, ң (ң) ә ң ққ ұ қ ң . ә ү, .
қ. ұ қ ң R (ғ) ұ . Ә ң ә қ. ү ә қ ғ (modus ponens ). әң ң ғғғ: ә қ ққ қ ғ қ қң ү ө ә. қ ғғ : қғ қ ә ү ң қ қ қ ғ. ұ ғ ң ә қ әқ қ қғ қ . әң ү ң ә қ ң ң ң қ, ң ө қ ғ. ғ ң ң ә қ ү ә ү ү өң. ұ ғ ң ү ү ң ә ә .
|
|
ә () ә ң ұ:
1. ϳ ғ .
2. ә ұ қ.
3. ұ ң ұқ , ә ғ ң ө () ғ.
4. Қ-ққ ө .
5. ө ү, ғ ққ ә.
ә қ ққ. [1.1] ққ ө . , 3 ң қ ғ 1-4 . Ққ ө ү ? ұғ . ү ұ ң ғ ғ. ә . ң ү ғ ғ.
3. Ққ ө
ә қ | Ұғ () | |
1. қ ә қ қ | & | |
2. ʳ қ қ | & | |
3. қ ә ә | ||
4. қ ққ ө ү | & | |
5. Қ: Ққ ө ү ? | ||
6.Қ |
Қ (6 ): ү . ү әң ( ө) ң :
7. 6 ә 4
8. 7 ә 1
9. 8 ә 2
10. 9 ә 3b
11. NIL 10 ә 3
NIL ң өң ү ұ ә қ ң ққ ө ү ң қ қ.
ә ө қ ә . , ү ү ү -қ ә ү ү ңғ . қ ә ү ң ө құ , ң ү -қ ө қғ ғ . Қ ү қ ө қ.
қ (өң (breadth-first), қ , ққ ) қ өң ү ң ө қ ә ө [1.1]. ә . қ S өң ү қ ө . ұ ү ү қ ә ққ ғ ң . S ң , S-T , қ ққ ғ ғ қ ә .
ә ә ғ өң PROLOG қ ғ ң ә. PROLOG . қ ғ ұ ң - . Қ қ LISP ә PROLOG ң ү ғң ө ә , ++ ә Java ө қ қ, ө ә ң ң ә өң LISP ә PROLOG ү . ұ ң , ә ә ң , ққ.