home *** CD-ROM | disk | FTP | other *** search
open in: 
MacOS 8.1
|
Win98
|
DOS
browse contents |
view JSON data
|
view as text
This file was processed as: LaTeX Document
(document/latex).
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| dexvert
| LaTeX Document (document/latex)
| magic
| Supported |
| 90%
| dexvert
| Hypertext Markup Language File (text/html)
| magic
| Supported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| HTML document text
| default (weak)
| |
| 99%
| file
| LaTeX document text
| default
| |
| 98%
| file
| exported SGML document text
| default
| |
| 97%
| file
| exported SGML document, ASCII text
| default
| |
| 80%
| TrID
| HyperText Markup Language with DOCTYPE
| default
| |
| 19%
| TrID
| HyperText Markup Language
| default
| |
| 100%
| checkBytes
| Printable ASCII
| default
| |
| 100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
| 100%
| siegfried
| fmt/281 LaTeX (Subdocument)
| default
| |
| 100%
| gt2
| HTML (Hyper Text Markup Language) Datei
| default
| |
| 100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
| |
| 100%
| xdgMime
| text/html
| default
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 3c 21 44 4f 43 54 59 50 | 45 20 48 54 4d 4c 20 50 |<!DOCTYP|E HTML P|
|00000010| 55 42 4c 49 43 20 22 2d | 2f 2f 57 33 43 2f 2f 44 |UBLIC "-|//W3C//D|
|00000020| 54 44 20 48 54 4d 4c 20 | 33 2e 32 20 46 69 6e 61 |TD HTML |3.2 Fina|
|00000030| 6c 2f 2f 65 6e 22 3e 0a | 0a 3c 21 2d 2d 43 6f 6e |l//en">.|.<!--Con|
|00000040| 76 65 72 74 65 64 20 77 | 69 74 68 20 4c 61 54 65 |verted w|ith LaTe|
|00000050| 58 32 48 54 4d 4c 20 32 | 30 32 32 20 28 52 65 6c |X2HTML 2|022 (Rel|
|00000060| 65 61 73 65 64 20 4a 61 | 6e 75 61 72 79 20 31 2c |eased Ja|nuary 1,|
|00000070| 20 32 30 32 32 29 20 2d | 2d 3e 0a 3c 48 54 4d 4c | 2022) -|->.<HTML|
|00000080| 20 6c 61 6e 67 3d 22 65 | 6e 22 3e 0a 3c 48 45 41 | lang="e|n">.<HEA|
|00000090| 44 3e 0a 3c 54 49 54 4c | 45 3e 43 6f 6e 74 65 6e |D>.<TITL|E>Conten|
|000000a0| 74 73 20 6f 66 20 53 74 | 61 74 65 20 73 70 61 63 |ts of St|ate spac|
|000000b0| 65 20 72 65 70 72 65 73 | 65 6e 74 61 74 69 6f 6e |e repres|entation|
|000000c0| 20 61 6e 64 20 70 72 6f | 62 6c 65 6d 20 72 65 64 | and pro|blem red|
|000000d0| 75 63 74 69 6f 6e 3c 2f | 54 49 54 4c 45 3e 0a 0a |uction</|TITLE>..|
|000000e0| 3c 4d 45 54 41 20 48 54 | 54 50 2d 45 51 55 49 56 |<META HT|TP-EQUIV|
|000000f0| 3d 22 43 6f 6e 74 65 6e | 74 2d 54 79 70 65 22 20 |="Conten|t-Type" |
|00000100| 43 4f 4e 54 45 4e 54 3d | 22 74 65 78 74 2f 68 74 |CONTENT=|"text/ht|
|00000110| 6d 6c 3b 20 63 68 61 72 | 73 65 74 3d 75 74 66 2d |ml; char|set=utf-|
|00000120| 38 22 3e 0a 3c 4d 45 54 | 41 20 4e 41 4d 45 3d 22 |8">.<MET|A NAME="|
|00000130| 76 69 65 77 70 6f 72 74 | 22 20 43 4f 4e 54 45 4e |viewport|" CONTEN|
|00000140| 54 3d 22 77 69 64 74 68 | 3d 64 65 76 69 63 65 2d |T="width|=device-|
|00000150| 77 69 64 74 68 2c 20 69 | 6e 69 74 69 61 6c 2d 73 |width, i|nitial-s|
|00000160| 63 61 6c 65 3d 31 2e 30 | 22 3e 0a 3c 4d 45 54 41 |cale=1.0|">.<META|
|00000170| 20 4e 41 4d 45 3d 22 47 | 65 6e 65 72 61 74 6f 72 | NAME="G|enerator|
|00000180| 22 20 43 4f 4e 54 45 4e | 54 3d 22 4c 61 54 65 58 |" CONTEN|T="LaTeX|
|00000190| 32 48 54 4d 4c 20 76 32 | 30 32 32 22 3e 0a 0a 3c |2HTML v2|022">..<|
|000001a0| 4c 49 4e 4b 20 52 45 4c | 3d 22 53 54 59 4c 45 53 |LINK REL|="STYLES|
|000001b0| 48 45 45 54 22 20 48 52 | 45 46 3d 22 53 45 41 52 |HEET" HR|EF="SEAR|
|000001c0| 43 48 2e 63 73 73 22 3e | 0a 0a 3c 4c 49 4e 4b 20 |CH.css">|..<LINK |
|000001d0| 52 45 4c 3d 22 6e 65 78 | 74 22 20 48 52 45 46 3d |REL="nex|t" HREF=|
|000001e0| 22 6e 6f 64 65 34 5f 6d | 6e 2e 68 74 6d 6c 22 3e |"node4_m|n.html">|
|000001f0| 0a 3c 4c 49 4e 4b 20 52 | 45 4c 3d 22 70 72 65 76 |.<LINK R|EL="prev|
|00000200| 69 6f 75 73 22 20 48 52 | 45 46 3d 22 6e 6f 64 65 |ious" HR|EF="node|
|00000210| 32 5f 6d 6e 2e 68 74 6d | 6c 22 3e 0a 3c 4c 49 4e |2_mn.htm|l">.<LIN|
|00000220| 4b 20 52 45 4c 3d 22 75 | 70 22 20 48 52 45 46 3d |K REL="u|p" HREF=|
|00000230| 22 6e 6f 64 65 32 5f 6d | 6e 2e 68 74 6d 6c 22 3e |"node2_m|n.html">|
|00000240| 0a 3c 4c 49 4e 4b 20 52 | 45 4c 3d 22 6e 65 78 74 |.<LINK R|EL="next|
|00000250| 22 20 48 52 45 46 3d 22 | 6e 6f 64 65 34 5f 6d 6e |" HREF="|node4_mn|
|00000260| 2e 68 74 6d 6c 22 3e 0a | 3c 2f 48 45 41 44 3e 0a |.html">.|</HEAD>.|
|00000270| 20 0a 3c 42 4f 44 59 20 | 62 67 63 6f 6c 6f 72 3d | .<BODY |bgcolor=|
|00000280| 22 23 66 66 66 66 66 66 | 22 20 74 65 78 74 3d 22 |"#ffffff|" text="|
|00000290| 23 30 30 30 30 30 30 22 | 20 6c 69 6e 6b 3d 22 23 |#000000"| link="#|
|000002a0| 39 39 34 34 45 45 22 20 | 76 6c 69 6e 6b 3d 22 23 |9944EE" |vlink="#|
|000002b0| 30 30 30 30 66 66 22 20 | 61 6c 69 6e 6b 3d 22 23 |0000ff" |alink="#|
|000002c0| 30 30 66 66 30 30 22 3e | 0a 0a 3c 48 32 3e 3c 41 |00ff00">|..<H2><A|
|000002d0| 20 49 44 3d 22 53 45 43 | 54 49 4f 4e 30 30 30 32 | ID="SEC|TION0002|
|000002e0| 31 30 30 30 30 30 30 30 | 30 30 30 30 30 30 30 30 |10000000|00000000|
|000002f0| 22 3e 0a 53 74 61 74 65 | 20 73 70 61 63 65 20 72 |">.State| space r|
|00000300| 65 70 72 65 73 65 6e 74 | 61 74 69 6f 6e 20 61 6e |epresent|ation an|
|00000310| 64 20 70 72 6f 62 6c 65 | 6d 20 72 65 64 75 63 74 |d proble|m reduct|
|00000320| 69 6f 6e 3c 2f 41 3e 0a | 3c 2f 48 32 3e 0a 0a 3c |ion</A>.|</H2>..<|
|00000330| 50 3e 0a 49 6e 20 74 68 | 69 73 20 73 65 63 74 69 |P>.In th|is secti|
|00000340| 6f 6e 2c 20 77 65 20 77 | 69 6c 6c 20 64 65 73 63 |on, we w|ill desc|
|00000350| 72 69 62 65 20 74 77 6f | 20 6d 65 74 68 6f 64 73 |ribe two| methods|
|00000360| 20 63 6f 6d 6d 6f 6e 6c | 79 20 75 73 65 64 20 69 | commonl|y used i|
|00000370| 6e 20 70 72 6f 62 6c 65 | 6d 0a 72 65 70 72 65 73 |n proble|m.repres|
|00000380| 65 6e 74 61 74 69 6f 6e | 2e 20 41 73 20 61 20 73 |entation|. As a s|
|00000390| 61 6d 70 6c 65 20 70 72 | 6f 62 6c 65 6d 20 74 68 |ample pr|oblem th|
|000003a0| 65 20 38 2d 70 75 7a 7a | 6c 65 20 77 69 6c 6c 20 |e 8-puzz|le will |
|000003b0| 62 65 20 75 73 65 64 2e | 20 54 68 65 20 38 2d 70 |be used.| The 8-p|
|000003c0| 75 7a 7a 6c 65 0a 63 6f | 6e 73 69 73 74 73 20 6f |uzzle.co|nsists o|
|000003d0| 66 20 38 20 6e 75 6d 62 | 65 72 65 64 2c 20 6d 6f |f 8 numb|ered, mo|
|000003e0| 76 61 62 6c 65 20 74 69 | 6c 65 73 20 73 65 74 20 |vable ti|les set |
|000003f0| 69 6e 20 61 20 33 20 58 | 20 33 20 66 72 61 6d 65 |in a 3 X| 3 frame|
|00000400| 2e 20 4f 6e 65 20 6f 66 | 20 74 68 65 20 63 65 6c |. One of| the cel|
|00000410| 6c 73 20 6f 66 0a 74 68 | 65 20 66 72 61 6d 65 20 |ls of.th|e frame |
|00000420| 69 73 20 61 6c 77 61 79 | 73 20 65 6d 70 74 79 2c |is alway|s empty,|
|00000430| 20 77 68 69 63 68 20 6d | 61 6b 65 73 20 69 74 20 | which m|akes it |
|00000440| 70 6f 73 73 69 62 6c 65 | 20 74 6f 20 6d 6f 76 65 |possible| to move|
|00000450| 20 74 68 65 20 74 69 6c | 65 73 2e 0a 0a 3c 50 3e | the til|es...<P>|
|00000460| 0a 41 20 73 61 6d 70 6c | 65 20 38 2d 70 75 7a 7a |.A sampl|e 8-puzz|
|00000470| 6c 65 20 69 73 20 67 69 | 76 65 6e 20 69 6e 20 66 |le is gi|ven in f|
|00000480| 69 67 2e 26 6e 62 73 70 | 3b 3c 41 20 48 52 45 46 |ig. |;<A HREF|
|00000490| 3d 22 6e 6f 64 65 33 5f | 63 74 2e 68 74 6d 6c 23 |="node3_|ct.html#|
|000004a0| 66 69 67 73 74 61 74 65 | 22 3e 3c 49 4d 47 20 20 |figstate|"><IMG |
|000004b0| 41 4c 54 3d 22 5b 2a 5d | 22 20 53 52 43 3d 22 63 |ALT="[*]|" SRC="c|
|000004c0| 72 6f 73 73 72 65 66 2e | 70 6e 67 22 3e 3c 2f 41 |rossref.|png"></A|
|000004d0| 3e 2e 20 43 6f 6e 73 69 | 64 65 72 20 74 68 65 20 |>. Consi|der the |
|000004e0| 70 72 6f 62 6c 65 6d 20 | 6f 66 0a 74 72 61 6e 73 |problem |of.trans|
|000004f0| 66 6f 72 6d 69 6e 67 20 | 74 68 65 20 66 69 72 73 |forming |the firs|
|00000500| 74 20 63 6f 6e 66 69 67 | 75 72 61 74 69 6f 6e 20 |t config|uration |
|00000510| 69 6e 74 6f 20 74 68 65 | 20 73 65 63 6f 6e 64 20 |into the| second |
|00000520| 6f 6e 65 2c 20 6f 75 72 | 20 67 6f 61 6c 2e 0a 0a |one, our| goal...|
|00000530| 3c 50 3e 0a 0a 3c 44 49 | 56 20 63 6c 61 73 73 3d |<P>..<DI|V class=|
|00000540| 22 43 45 4e 54 45 52 22 | 3e 3c 41 20 49 44 3d 22 |"CENTER"|><A ID="|
|00000550| 66 69 67 73 74 61 74 65 | 22 3e 3c 2f 41 3e 3c 41 |figstate|"></A><A|
|00000560| 20 49 44 3d 22 31 39 22 | 3e 3c 2f 41 3e 0a 3c 54 | ID="19"|></A>.<T|
|00000570| 41 42 4c 45 3e 0a 3c 43 | 41 50 54 49 4f 4e 20 63 |ABLE>.<C|APTION c|
|00000580| 6c 61 73 73 3d 22 42 4f | 54 54 4f 4d 22 3e 3c 53 |lass="BO|TTOM"><S|
|00000590| 54 52 4f 4e 47 3e 46 69 | 67 75 72 65 3a 3c 2f 53 |TRONG>Fi|gure:</S|
|000005a0| 54 52 4f 4e 47 3e 0a 54 | 68 65 20 38 2d 70 75 7a |TRONG>.T|he 8-puz|
|000005b0| 7a 6c 65 2e 3c 2f 43 41 | 50 54 49 4f 4e 3e 0a 3c |zle.</CA|PTION>.<|
|000005c0| 54 52 3e 3c 54 44 3e 3c | 49 4d 47 0a 20 53 54 59 |TR><TD><|IMG. STY|
|000005d0| 4c 45 3d 22 68 65 69 67 | 68 74 3a 20 32 38 36 2e |LE="heig|ht: 286.|
|000005e0| 37 36 65 78 3b 20 22 20 | 53 52 43 3d 22 69 6d 67 |76ex; " |SRC="img|
|000005f0| 31 2e 70 6e 67 22 0a 20 | 41 4c 54 3d 22 5c 62 65 |1.png". |ALT="\be|
|00000600| 67 69 6e 7b 66 69 67 75 | 72 65 7d 5c 63 65 6e 74 |gin{figu|re}\cent|
|00000610| 65 72 69 6e 67 0a 5c 62 | 65 67 69 6e 7b 74 61 62 |ering.\b|egin{tab|
|00000620| 75 6c 61 72 7d 7b 72 72 | 72 63 72 72 72 7d 0a 32 |ular}{rr|rcrrr}.2|
|00000630| 20 26 61 6d 70 3b 20 31 | 20 26 61 6d 70 3b 20 36 | & 1| & 6|
|00000640| 20 5c 68 73 70 61 63 65 | 7b 32 63 6d 7d 20 26 61 | \hspace|{2cm} &a|
|00000650| 6d 70 3b 20 31 20 26 61 | 6d 70 3b 2e 2e 2e 0a 2e |mp; 1 &a|mp;.....|
|00000660| 2e 2e 20 26 61 6d 70 3b | 20 30 20 26 61 6d 70 3b |.. &| 0 &|
|00000670| 20 34 20 5c 5c 0a 37 20 | 26 61 6d 70 3b 20 35 20 | 4 \\.7 |& 5 |
|00000680| 26 61 6d 70 3b 20 33 20 | 5c 68 73 70 61 63 65 7b |& 3 |\hspace{|
|00000690| 32 63 6d 7d 20 26 61 6d | 70 3b 20 37 20 26 61 6d |2cm} &am|p; 7 &am|
|000006a0| 70 3b 20 36 20 26 61 6d | 70 3b 20 35 20 5c 5c 0a |p; 6 &am|p; 5 \\.|
|000006b0| 5c 65 6e 64 7b 74 61 62 | 75 6c 61 72 7d 20 5c 65 |\end{tab|ular} \e|
|000006c0| 6e 64 7b 66 69 67 75 72 | 65 7d 22 3e 3c 2f 54 44 |nd{figur|e}"></TD|
|000006d0| 3e 3c 2f 54 52 3e 0a 3c | 2f 54 41 42 4c 45 3e 0a |></TR>.<|/TABLE>.|
|000006e0| 3c 2f 44 49 56 3e 0a 0a | 3c 50 3e 0a 54 6f 20 73 |</DIV>..|<P>.To s|
|000006f0| 6f 6c 76 65 20 74 68 69 | 73 20 70 75 7a 7a 6c 65 |olve thi|s puzzle|
|00000700| 20 77 65 20 74 72 79 20 | 6f 75 74 20 76 61 72 69 | we try |out vari|
|00000710| 6f 75 73 20 6d 6f 76 65 | 73 20 70 72 6f 64 75 63 |ous move|s produc|
|00000720| 69 6e 67 20 6e 65 77 20 | 63 6f 6e 66 69 67 75 72 |ing new |configur|
|00000730| 61 74 69 6f 6e 73 0a 75 | 6e 74 69 6c 20 77 65 20 |ations.u|ntil we |
|00000740| 70 72 6f 64 75 63 65 20 | 74 68 65 20 67 6f 61 6c |produce |the goal|
|00000750| 20 63 6f 6e 66 69 67 75 | 72 61 74 69 6f 6e 2e 20 | configu|ration. |
|00000760| 54 6f 20 67 69 76 65 20 | 61 20 6d 6f 72 65 20 66 |To give |a more f|
|00000770| 6f 72 6d 61 6c 0a 64 65 | 66 69 6e 69 74 69 6f 6e |ormal.de|finition|
|00000780| 20 6f 66 20 74 68 69 73 | 20 70 72 6f 62 6c 65 6d | of this| problem|
|00000790| 20 77 65 20 73 61 79 20 | 74 68 61 74 20 77 65 20 | we say |that we |
|000007a0| 61 72 65 20 74 72 79 69 | 6e 67 20 74 6f 20 72 65 |are tryi|ng to re|
|000007b0| 61 63 68 20 61 20 63 65 | 72 74 61 69 6e 20 3c 45 |ach a ce|rtain <E|
|000007c0| 4d 3e 67 6f 61 6c 26 6e | 62 73 70 3b 3c 2f 45 4d |M>goal&n|bsp;</EM|
|000007d0| 3e 20 63 6f 6e 66 69 67 | 75 72 61 74 69 6f 6e 20 |> config|uration |
|000007e0| 73 74 61 72 74 69 6e 67 | 20 77 69 74 68 20 61 6e |starting| with an|
|000007f0| 20 3c 45 4d 3e 69 6e 69 | 74 69 61 6c 3c 2f 45 4d | <EM>ini|tial</EM|
|00000800| 3e 20 63 6f 6e 66 69 67 | 75 72 61 74 69 6f 6e 20 |> config|uration |
|00000810| 62 79 20 75 73 69 6e 67 | 0a 73 6f 6d 65 20 73 65 |by using|.some se|
|00000820| 74 20 6f 66 20 3c 45 4d | 3e 6f 70 65 72 61 74 6f |t of <EM|>operato|
|00000830| 72 73 26 6e 62 73 70 3b | 3c 2f 45 4d 3e 2e 20 41 |rs |</EM>. A|
|00000840| 6e 20 6f 70 65 72 61 74 | 6f 72 20 74 72 61 6e 73 |n operat|or trans|
|00000850| 66 6f 72 6d 73 20 6f 6e | 65 20 63 6f 6e 66 69 67 |forms on|e config|
|00000860| 75 72 61 74 69 6f 6e 20 | 69 6e 74 6f 0a 61 6e 6f |uration |into.ano|
|00000870| 74 68 65 72 2c 20 69 6e | 20 74 68 65 20 63 61 73 |ther, in| the cas|
|00000880| 65 20 6f 66 20 74 68 65 | 20 38 2d 70 75 7a 7a 6c |e of the| 8-puzzl|
|00000890| 65 20 69 74 20 69 73 20 | 6d 6f 73 74 20 6e 61 74 |e it is |most nat|
|000008a0| 75 72 61 6c 20 74 6f 20 | 74 68 69 6e 6b 20 6f 66 |ural to |think of|
|000008b0| 20 34 20 73 75 63 68 0a | 6f 70 65 72 61 74 6f 72 | 4 such.|operator|
|000008c0| 73 2c 20 65 61 63 68 20 | 63 6f 72 72 65 73 70 6f |s, each |correspo|
|000008d0| 6e 64 69 6e 67 20 74 6f | 20 6d 6f 76 69 6e 67 20 |nding to| moving |
|000008e0| 74 68 65 20 65 6d 70 74 | 79 20 74 69 6c 65 3a 20 |the empt|y tile: |
|000008f0| 6d 6f 76 65 20 65 6d 70 | 74 79 20 74 69 6c 65 20 |move emp|ty tile |
|00000900| 6c 65 66 74 2c 0a 6d 6f | 76 65 20 65 6d 70 74 79 |left,.mo|ve empty|
|00000910| 20 74 69 6c 65 20 72 69 | 67 68 74 2c 20 6d 6f 76 | tile ri|ght, mov|
|00000920| 65 20 65 6d 70 74 79 20 | 74 69 6c 65 20 75 70 2c |e empty |tile up,|
|00000930| 20 6d 6f 76 65 20 65 6d | 70 74 79 20 74 69 6c 65 | move em|pty tile|
|00000940| 20 64 6f 77 6e 2e 0a 0a | 3c 50 3e 0a 57 68 61 74 | down...|<P>.What|
|00000950| 20 77 65 20 6a 75 73 74 | 20 68 61 76 65 20 64 6f | we just| have do|
|00000960| 6e 65 20 69 73 20 64 65 | 66 69 6e 69 6e 67 20 74 |ne is de|fining t|
|00000970| 68 65 20 70 72 6f 62 6c | 65 6d 20 6f 66 20 73 6f |he probl|em of so|
|00000980| 6c 76 69 6e 67 20 74 68 | 65 20 38 2d 70 75 7a 7a |lving th|e 8-puzz|
|00000990| 6c 65 20 69 6e 0a 74 65 | 72 6d 73 20 6f 66 20 61 |le in.te|rms of a|
|000009a0| 20 3c 45 4d 3e 73 74 61 | 74 65 20 73 70 61 63 65 | <EM>sta|te space|
|000009b0| 20 73 65 61 72 63 68 26 | 6e 62 73 70 3b 3c 2f 45 | search&|nbsp;</E|
|000009c0| 4d 3e 2e 20 49 6e 20 61 | 20 73 74 61 74 65 20 73 |M>. In a| state s|
|000009d0| 70 61 63 65 20 73 65 61 | 72 63 68 20 74 68 65 20 |pace sea|rch the |
|000009e0| 6f 62 6a 65 63 74 20 69 | 73 20 74 6f 0a 72 65 61 |object i|s to.rea|
|000009f0| 63 68 20 61 20 63 65 72 | 74 61 69 6e 20 67 6f 61 |ch a cer|tain goa|
|00000a00| 6c 20 3c 45 4d 3e 73 74 | 61 74 65 26 6e 62 73 70 |l <EM>st|ate |
|00000a10| 3b 3c 2f 45 4d 3e 20 73 | 74 61 72 74 69 6e 67 20 |;</EM> s|tarting |
|00000a20| 77 69 74 68 20 61 6e 20 | 69 6e 69 74 69 61 6c 20 |with an |initial |
|00000a30| 73 74 61 74 65 2e 20 49 | 6e 20 74 68 65 20 63 61 |state. I|n the ca|
|00000a40| 73 65 0a 6f 66 20 74 68 | 65 20 38 2d 70 75 7a 7a |se.of th|e 8-puzz|
|00000a50| 6c 65 20 74 68 65 20 73 | 74 61 72 74 20 61 6e 64 |le the s|tart and|
|00000a60| 20 67 6f 61 6c 20 73 74 | 61 74 65 20 61 72 65 20 | goal st|ate are |
|00000a70| 74 68 65 20 63 6f 6e 66 | 69 67 75 72 61 74 69 6f |the conf|iguratio|
|00000a80| 6e 73 20 67 69 76 65 6e | 20 69 6e 0a 66 69 67 2e |ns given| in.fig.|
|00000a90| 26 6e 62 73 70 3b 3c 41 | 20 48 52 45 46 3d 22 6e | <A| HREF="n|
|00000aa0| 6f 64 65 33 5f 63 74 2e | 68 74 6d 6c 23 66 69 67 |ode3_ct.|html#fig|
|00000ab0| 73 74 61 74 65 22 3e 3c | 49 4d 47 20 20 41 4c 54 |state"><|IMG ALT|
|00000ac0| 3d 22 5b 2a 5d 22 20 53 | 52 43 3d 22 63 72 6f 73 |="[*]" S|RC="cros|
|00000ad0| 73 72 65 66 2e 70 6e 67 | 22 3e 3c 2f 41 3e 2e 0a |sref.png|"></A>..|
|00000ae0| 4d 6f 72 65 20 67 65 6e | 65 72 61 6c 6c 79 20 77 |More gen|erally w|
|00000af0| 65 20 63 61 6e 20 73 61 | 79 20 74 68 61 74 20 65 |e can sa|y that e|
|00000b00| 76 65 72 79 20 63 6f 6e | 66 69 67 75 72 61 74 69 |very con|figurati|
|00000b10| 6f 6e 20 77 65 20 70 72 | 6f 64 75 63 65 20 77 68 |on we pr|oduce wh|
|00000b20| 65 6e 20 74 72 79 69 6e | 67 20 74 6f 0a 73 6f 6c |en tryin|g to.sol|
|00000b30| 76 65 20 74 68 65 20 38 | 2d 70 75 7a 7a 6c 65 20 |ve the 8|-puzzle |
|00000b40| 63 6f 72 72 65 73 70 6f | 6e 64 73 20 74 6f 20 6f |correspo|nds to o|
|00000b50| 6e 65 20 73 74 61 74 65 | 20 69 6e 20 74 68 65 20 |ne state| in the |
|00000b60| 73 74 61 74 65 20 73 70 | 61 63 65 2e 20 41 6c 6c |state sp|ace. All|
|00000b70| 20 74 68 65 73 65 0a 73 | 74 61 74 65 73 20 74 6f | these.s|tates to|
|00000b80| 67 65 74 68 65 72 2c 20 | 69 2e 65 2e 2c 20 3c 45 |gether, |i.e., <E|
|00000b90| 4d 3e 61 6c 6c 20 70 6f | 73 73 69 62 6c 65 26 6e |M>all po|ssible&n|
|00000ba0| 62 73 70 3b 3c 2f 45 4d | 3e 20 63 6f 6e 66 69 67 |bsp;</EM|> config|
|00000bb0| 75 72 61 74 69 6f 6e 73 | 20 6d 61 6b 65 20 75 70 |urations| make up|
|00000bc0| 20 74 68 65 20 73 74 61 | 74 65 0a 73 70 61 63 65 | the sta|te.space|
|00000bd0| 2e 20 49 74 20 69 73 20 | 70 6f 73 73 69 62 6c 65 |. It is |possible|
|00000be0| 20 6f 66 20 63 6f 75 72 | 73 65 20 74 6f 20 64 65 | of cour|se to de|
|00000bf0| 66 69 6e 65 20 74 68 65 | 20 73 74 61 74 65 20 73 |fine the| state s|
|00000c00| 70 61 63 65 20 77 69 74 | 68 6f 75 74 20 65 78 70 |pace wit|hout exp|
|00000c10| 6c 69 63 69 74 6c 79 0a | 65 6e 75 6d 65 72 61 74 |licitly.|enumerat|
|00000c20| 69 6e 67 20 61 6c 6c 20 | 73 74 61 74 65 73 2e 20 |ing all |states. |
|00000c30| 49 6e 64 65 65 64 2c 20 | 6d 6f 73 74 20 6f 66 20 |Indeed, |most of |
|00000c40| 74 68 65 20 74 69 6d 65 | 20 74 68 69 73 20 69 73 |the time| this is|
|00000c50| 20 69 6d 70 6f 73 73 69 | 62 6c 65 0a 61 6e 64 20 | impossi|ble.and |
|00000c60| 74 68 65 20 73 74 61 74 | 65 20 73 70 61 63 65 20 |the stat|e space |
|00000c70| 77 69 6c 6c 20 62 65 20 | 64 65 66 69 6e 65 64 20 |will be |defined |
|00000c80| 69 6d 70 6c 69 63 69 74 | 6c 79 20 62 79 20 70 72 |implicit|ly by pr|
|00000c90| 6f 76 69 64 69 6e 67 20 | 72 75 6c 65 73 20 73 70 |oviding |rules sp|
|00000ca0| 65 63 69 66 79 69 6e 67 | 0a 68 6f 77 20 65 61 63 |ecifying|.how eac|
|00000cb0| 68 20 73 74 61 74 65 20 | 63 61 6e 20 62 65 20 64 |h state |can be d|
|00000cc0| 65 72 69 76 65 64 20 66 | 72 6f 6d 20 61 6e 6f 74 |erived f|rom anot|
|00000cd0| 68 65 72 2e 20 54 68 65 | 20 73 74 61 74 65 20 73 |her. The| state s|
|00000ce0| 70 61 63 65 20 6d 61 79 | 20 62 65 20 73 6d 61 6c |pace may| be smal|
|00000cf0| 6c 20 61 73 20 69 6e 0a | 74 68 65 20 63 61 73 65 |l as in.|the case|
|00000d00| 20 6f 66 20 74 68 65 20 | 38 2d 70 75 7a 7a 6c 65 | of the |8-puzzle|
|00000d10| 2c 20 62 75 74 20 66 6f | 72 20 6d 6f 73 74 20 65 |, but fo|r most e|
|00000d20| 76 65 72 79 20 64 61 79 | 20 70 72 6f 62 6c 65 6d |very day| problem|
|00000d30| 73 20 6f 72 20 6f 74 68 | 65 72 20 62 6f 61 72 64 |s or oth|er board|
|00000d40| 20 67 61 6d 65 73 0a 69 | 74 20 69 73 20 71 75 69 | games.i|t is qui|
|00000d50| 74 65 20 6c 61 72 67 65 | 20 28 65 2e 67 2e 2c 20 |te large| (e.g., |
|00000d60| 69 6e 20 63 68 65 73 73 | 20 74 68 65 20 74 6f 74 |in chess| the tot|
|00000d70| 61 6c 20 6e 75 6d 62 65 | 72 20 6f 66 20 70 6f 73 |al numbe|r of pos|
|00000d80| 73 69 62 6c 65 20 62 6f | 61 72 64 20 63 6f 6e 66 |sible bo|ard conf|
|00000d90| 69 67 75 72 61 74 69 6f | 6e 73 2c 0a 74 68 69 73 |iguratio|ns,.this|
|00000da0| 20 69 73 20 74 68 65 20 | 74 6f 74 61 6c 20 6e 75 | is the |total nu|
|00000db0| 6d 62 65 72 20 6f 66 20 | 70 6f 73 73 69 62 6c 65 |mber of |possible|
|00000dc0| 20 73 74 61 74 65 73 2c | 20 65 71 75 61 6c 73 20 | states,| equals |
|00000dd0| 72 6f 75 67 68 6c 79 20 | 31 30 3c 53 55 50 3e 31 |roughly |10<SUP>1|
|00000de0| 32 30 3c 2f 53 55 50 3e | 29 2e 0a 4f 62 76 69 6f |20</SUP>|)..Obvio|
|00000df0| 75 73 6c 79 20 69 74 20 | 77 6f 75 6c 64 20 62 65 |usly it |would be|
|00000e00| 20 69 6d 70 6f 73 73 69 | 62 6c 65 20 74 6f 20 65 | impossi|ble to e|
|00000e10| 78 70 6c 6f 72 65 20 74 | 68 65 20 65 6e 74 69 72 |xplore t|he entir|
|00000e20| 65 20 73 74 61 74 65 20 | 73 70 61 63 65 20 61 6e |e state |space an|
|00000e30| 64 20 6f 66 74 65 6e 0a | 74 68 69 73 20 69 73 20 |d often.|this is |
|00000e40| 6e 6f 74 20 6e 65 65 64 | 65 64 2c 20 62 65 63 61 |not need|ed, beca|
|00000e50| 75 73 65 20 77 65 20 61 | 72 65 20 69 6e 74 65 72 |use we a|re inter|
|00000e60| 65 73 74 65 64 20 69 6e | 20 66 69 6e 64 69 6e 67 |ested in| finding|
|00000e70| 20 6f 6e 6c 79 20 6f 6e | 65 20 73 6f 6c 75 74 69 | only on|e soluti|
|00000e80| 6f 6e 20 74 6f 0a 61 20 | 70 72 6f 62 6c 65 6d 2c |on to.a |problem,|
|00000e90| 20 69 2e 65 2e 2c 20 6f | 6e 6c 79 20 6f 6e 65 20 | i.e., o|nly one |
|00000ea0| 70 61 74 68 20 6c 65 61 | 64 69 6e 67 20 66 72 6f |path lea|ding fro|
|00000eb0| 6d 20 74 68 65 20 73 74 | 61 72 74 20 73 74 61 74 |m the st|art stat|
|00000ec0| 65 20 74 6f 20 74 68 65 | 20 67 6f 61 6c 20 73 74 |e to the| goal st|
|00000ed0| 61 74 65 2e 0a 54 68 69 | 73 20 6d 65 61 6e 73 20 |ate..Thi|s means |
|00000ee0| 74 68 61 74 20 77 65 20 | 64 6f 20 6e 6f 74 20 68 |that we |do not h|
|00000ef0| 61 76 65 20 74 6f 20 73 | 65 61 72 63 68 20 74 68 |ave to s|earch th|
|00000f00| 65 20 73 74 61 74 65 20 | 73 70 61 63 65 20 3c 45 |e state |space <E|
|00000f10| 4d 3e 65 78 68 61 75 73 | 74 69 76 65 6c 79 26 6e |M>exhaus|tively&n|
|00000f20| 62 73 70 3b 3c 2f 45 4d | 3e 2c 0a 62 75 74 20 61 |bsp;</EM|>,.but a|
|00000f30| 20 73 6d 61 6c 6c 28 65 | 72 29 20 70 6f 72 74 69 | small(e|r) porti|
|00000f40| 6f 6e 20 69 6e 73 74 65 | 61 64 2e 20 54 68 65 20 |on inste|ad. The |
|00000f50| 70 72 6f 62 6c 65 6d 20 | 6f 66 20 63 6f 75 72 73 |problem |of cours|
|00000f60| 65 20 69 73 2c 20 77 68 | 69 63 68 20 70 6f 72 74 |e is, wh|ich port|
|00000f70| 69 6f 6e 3f 0a 0a 3c 50 | 3e 0a 42 75 74 20 62 65 |ion?..<P|>.But be|
|00000f80| 66 6f 72 65 20 77 65 20 | 61 72 65 20 67 6f 69 6e |fore we |are goin|
|00000f90| 67 20 74 6f 20 64 69 73 | 63 75 73 73 20 74 68 69 |g to dis|cuss thi|
|00000fa0| 73 20 70 6f 69 6e 74 20 | 69 74 20 77 69 6c 6c 20 |s point |it will |
|00000fb0| 62 65 20 68 65 6c 70 66 | 75 6c 20 74 6f 20 6c 6f |be helpf|ul to lo|
|00000fc0| 6f 6b 0a 73 6f 6d 65 77 | 68 61 74 20 66 75 72 74 |ok.somew|hat furt|
|00000fd0| 68 65 72 20 61 74 20 74 | 68 65 20 61 70 70 72 6f |her at t|he appro|
|00000fe0| 61 63 68 20 77 65 20 68 | 61 76 65 20 64 65 73 63 |ach we h|ave desc|
|00000ff0| 72 69 62 65 64 20 73 6f | 20 66 61 72 2e 20 57 65 |ribed so| far. We|
|00001000| 20 73 61 69 64 20 74 68 | 61 74 20 74 6f 0a 73 6f | said th|at to.so|
|00001010| 6c 76 65 20 61 20 70 72 | 6f 62 6c 65 6d 20 69 74 |lve a pr|oblem it|
|00001020| 20 69 73 20 6e 65 63 65 | 73 73 61 72 79 20 74 6f | is nece|ssary to|
|00001030| 20 72 65 70 72 65 73 65 | 6e 74 20 74 68 65 20 70 | represe|nt the p|
|00001040| 72 6f 62 6c 65 6d 20 61 | 73 20 61 20 73 74 61 74 |roblem a|s a stat|
|00001050| 65 20 73 70 61 63 65 0a | 73 65 61 72 63 68 2e 20 |e space.|search. |
|00001060| 54 68 61 74 20 69 73 2c | 20 77 65 20 64 65 66 69 |That is,| we defi|
|00001070| 6e 65 20 61 20 73 74 61 | 72 74 20 73 74 61 74 65 |ne a sta|rt state|
|00001080| 2c 20 61 20 67 6f 61 6c | 20 73 74 61 74 65 20 61 |, a goal| state a|
|00001090| 6e 64 20 61 20 73 65 74 | 20 6f 66 20 6f 70 65 72 |nd a set| of oper|
|000010a0| 61 74 6f 72 73 0a 74 68 | 61 74 20 74 72 61 6e 73 |ators.th|at trans|
|000010b0| 66 6f 72 6d 20 6f 6e 65 | 20 73 74 61 74 65 20 69 |form one| state i|
|000010c0| 6e 74 6f 20 61 6e 6f 74 | 68 65 72 2e 20 54 68 65 |nto anot|her. The|
|000010d0| 20 61 63 74 75 61 6c 20 | 73 65 61 72 63 68 20 63 | actual |search c|
|000010e0| 6f 6e 73 69 73 74 73 20 | 69 6e 20 6d 6f 76 69 6e |onsists |in movin|
|000010f0| 67 0a 61 72 6f 75 6e 64 | 20 69 6e 20 74 68 65 20 |g.around| in the |
|00001100| 73 74 61 74 65 20 73 70 | 61 63 65 2c 20 6c 6f 6f |state sp|ace, loo|
|00001110| 6b 69 6e 67 20 66 6f 72 | 20 61 20 70 61 74 68 20 |king for| a path |
|00001120| 66 72 6f 6d 20 74 68 65 | 20 69 6e 69 74 69 61 6c |from the| initial|
|00001130| 20 73 74 61 74 65 20 74 | 6f 20 74 68 65 0a 67 6f | state t|o the.go|
|00001140| 61 6c 20 73 74 61 74 65 | 2e 20 49 6e 20 74 68 69 |al state|. In thi|
|00001150| 73 20 63 61 73 65 20 74 | 68 65 20 73 65 61 72 63 |s case t|he searc|
|00001160| 68 20 70 72 6f 63 65 73 | 73 20 70 72 6f 63 65 65 |h proces|s procee|
|00001170| 64 73 20 66 6f 72 77 61 | 72 64 20 62 65 63 61 75 |ds forwa|rd becau|
|00001180| 73 65 20 77 65 20 73 74 | 61 72 74 0a 77 69 74 68 |se we st|art.with|
|00001190| 20 74 68 65 20 69 6e 69 | 74 69 61 6c 20 73 74 61 | the ini|tial sta|
|000011a0| 74 65 20 61 6e 64 20 6d | 6f 76 65 20 74 6f 77 61 |te and m|ove towa|
|000011b0| 72 64 73 20 74 68 65 20 | 67 6f 61 6c 20 73 74 61 |rds the |goal sta|
|000011c0| 74 65 2e 20 48 65 6e 63 | 65 20 69 74 20 69 73 20 |te. Henc|e it is |
|000011d0| 63 61 6c 6c 65 64 20 61 | 0a 3c 45 4d 3e 66 6f 72 |called a|.<EM>for|
|000011e0| 77 61 72 64 20 72 65 61 | 73 6f 6e 69 6e 67 20 73 |ward rea|soning s|
|000011f0| 79 73 74 65 6d 26 6e 62 | 73 70 3b 3c 2f 45 4d 3e |ystem&nb|sp;</EM>|
|00001200| 2e 20 54 68 65 20 6f 70 | 70 6f 73 69 74 65 20 62 |. The op|posite b|
|00001210| 65 68 61 76 69 6f 75 72 | 20 69 73 20 61 6c 73 6f |ehaviour| is also|
|00001220| 20 70 6f 73 73 69 62 6c | 65 3a 20 61 0a 73 79 73 | possibl|e: a.sys|
|00001230| 74 65 6d 20 73 74 61 72 | 74 69 6e 67 20 74 68 65 |tem star|ting the|
|00001240| 20 73 65 61 72 63 68 20 | 77 69 74 68 20 74 68 65 | search |with the|
|00001250| 20 67 6f 61 6c 20 73 74 | 61 74 65 20 61 6e 64 20 | goal st|ate and |
|00001260| 6d 6f 76 69 6e 67 20 62 | 61 63 6b 77 61 72 64 20 |moving b|ackward |
|00001270| 74 6f 20 74 68 65 0a 69 | 6e 69 74 69 61 6c 20 73 |to the.i|nitial s|
|00001280| 74 61 74 65 2e 20 49 6e | 20 74 68 69 73 20 6d 65 |tate. In| this me|
|00001290| 74 68 6f 64 2c 20 6f 66 | 74 65 6e 20 63 61 6c 6c |thod, of|ten call|
|000012a0| 65 64 20 3c 45 4d 3e 62 | 61 63 6b 63 68 61 69 6e |ed <EM>b|ackchain|
|000012b0| 69 6e 67 26 6e 62 73 70 | 3b 3c 2f 45 4d 3e 20 77 |ing |;</EM> w|
|000012c0| 65 20 3c 45 4d 3e 72 65 | 61 73 6f 6e 0a 62 61 63 |e <EM>re|ason.bac|
|000012d0| 6b 77 61 72 64 26 6e 62 | 73 70 3b 3c 2f 45 4d 3e |kward&nb|sp;</EM>|
|000012e0| 20 66 72 6f 6d 20 74 68 | 65 20 67 6f 61 6c 20 73 | from th|e goal s|
|000012f0| 74 61 74 65 73 2e 20 54 | 68 65 73 65 20 74 77 6f |tates. T|hese two|
|00001300| 20 74 65 63 68 6e 69 71 | 75 65 73 20 63 61 6e 20 | techniq|ues can |
|00001310| 62 65 20 63 6f 6d 62 69 | 6e 65 64 2c 0a 72 65 73 |be combi|ned,.res|
|00001320| 75 6c 74 69 6e 67 20 69 | 6e 20 61 20 3c 45 4d 3e |ulting i|n a <EM>|
|00001330| 62 69 64 69 72 65 63 74 | 69 6f 6e 61 6c 20 73 65 |bidirect|ional se|
|00001340| 61 72 63 68 26 6e 62 73 | 70 3b 3c 2f 45 4d 3e 2e |arch&nbs|p;</EM>.|
|00001350| 20 49 6e 20 74 68 65 20 | 63 61 73 65 20 6f 66 20 | In the |case of |
|00001360| 74 68 65 20 38 2d 70 75 | 7a 7a 6c 65 20 69 74 0a |the 8-pu|zzle it.|
|00001370| 64 6f 65 73 20 6e 6f 74 | 20 6d 61 6b 65 20 6d 75 |does not| make mu|
|00001380| 63 68 20 64 69 66 66 65 | 72 65 6e 63 65 20 69 66 |ch diffe|rence if|
|00001390| 20 77 65 20 6d 6f 76 65 | 20 66 6f 72 77 61 72 64 | we move| forward|
|000013a0| 20 6f 72 20 62 61 63 6b | 77 61 72 64 2c 20 62 65 | or back|ward, be|
|000013b0| 63 61 75 73 65 20 61 62 | 6f 75 74 20 74 68 65 0a |cause ab|out the.|
|000013c0| 73 61 6d 65 20 6e 75 6d | 62 65 72 20 6f 66 20 70 |same num|ber of p|
|000013d0| 61 74 68 73 20 77 69 6c | 6c 20 62 65 20 67 65 6e |aths wil|l be gen|
|000013e0| 65 72 61 74 65 64 20 69 | 6e 20 65 69 74 68 65 72 |erated i|n either|
|000013f0| 20 63 61 73 65 2c 20 62 | 75 74 20 73 6f 6d 65 20 | case, b|ut some |
|00001400| 70 72 6f 62 6c 65 6d 73 | 20 63 61 6e 20 62 65 0a |problems| can be.|
|00001410| 73 6f 6c 76 65 64 20 6d | 6f 72 65 20 65 66 66 69 |solved m|ore effi|
|00001420| 63 69 65 6e 74 6c 79 20 | 77 68 65 6e 20 73 65 61 |ciently |when sea|
|00001430| 72 63 68 69 6e 67 20 69 | 6e 20 6f 6e 65 20 64 69 |rching i|n one di|
|00001440| 72 65 63 74 69 6f 6e 20 | 72 61 74 68 65 72 20 74 |rection |rather t|
|00001450| 68 61 6e 20 74 68 65 20 | 6f 74 68 65 72 0a 28 73 |han the |other.(s|
|00001460| 65 65 20 52 69 63 68 20 | 28 31 39 38 33 29 2c 20 |ee Rich |(1983), |
|00001470| 70 2e 35 38 29 2e 0a 0a | 3c 50 3e 0a 41 20 64 69 |p.58)...|<P>.A di|
|00001480| 66 66 65 72 65 6e 74 20 | 74 65 63 68 6e 69 71 75 |fferent |techniqu|
|00001490| 65 2c 20 6f 72 20 72 61 | 74 68 65 72 20 61 20 64 |e, or ra|ther a d|
|000014a0| 69 66 66 65 72 65 6e 74 | 20 77 61 79 20 74 6f 20 |ifferent| way to |
|000014b0| 72 65 70 72 65 73 65 6e | 74 20 70 72 6f 62 6c 65 |represen|t proble|
|000014c0| 6d 73 2c 20 74 68 61 74 | 0a 68 61 73 20 6e 6f 74 |ms, that|.has not|
|000014d0| 20 62 65 65 6e 20 6d 65 | 6e 74 69 6f 6e 65 64 20 | been me|ntioned |
|000014e0| 73 6f 20 66 61 72 20 69 | 73 20 74 68 61 74 20 6f |so far i|s that o|
|000014f0| 66 20 3c 45 4d 3e 70 72 | 6f 62 6c 65 6d 20 72 65 |f <EM>pr|oblem re|
|00001500| 64 75 63 74 69 6f 6e 26 | 6e 62 73 70 3b 3c 2f 45 |duction&|nbsp;</E|
|00001510| 4d 3e 2e 20 49 6e 20 74 | 68 69 73 0a 74 79 70 65 |M>. In t|his.type|
|00001520| 20 6f 66 20 72 65 70 72 | 65 73 65 6e 74 61 74 69 | of repr|esentati|
|00001530| 6f 6e 20 65 61 63 68 20 | 6f 70 65 72 61 74 6f 72 |on each |operator|
|00001540| 20 75 73 65 64 20 6d 61 | 79 20 64 69 76 69 64 65 | used ma|y divide|
|00001550| 20 74 68 65 20 70 72 6f | 62 6c 65 6d 20 69 6e 74 | the pro|blem int|
|00001560| 6f 20 61 20 73 65 74 20 | 6f 66 0a 73 75 62 2d 70 |o a set |of.sub-p|
|00001570| 72 6f 62 6c 65 6d 73 20 | 74 68 61 74 20 65 61 63 |roblems |that eac|
|00001580| 68 20 68 61 76 65 20 74 | 6f 20 62 65 20 73 6f 6c |h have t|o be sol|
|00001590| 76 65 64 20 73 65 70 65 | 72 61 74 65 6c 79 2e 20 |ved sepe|rately. |
|000015a0| 41 64 64 69 74 69 6f 6e | 61 6c 6c 79 2c 0a 74 68 |Addition|ally,.th|
|000015b0| 65 72 65 20 6d 61 79 20 | 62 65 20 72 65 73 74 72 |ere may |be restr|
|000015c0| 69 63 74 69 6f 6e 73 20 | 6f 6e 20 74 68 65 20 6f |ictions |on the o|
|000015d0| 72 64 65 72 20 69 6e 20 | 77 68 69 63 68 20 74 68 |rder in |which th|
|000015e0| 65 73 65 20 73 75 62 2d | 70 72 6f 62 6c 65 6d 73 |ese sub-|problems|
|000015f0| 20 68 61 76 65 20 74 6f | 20 62 65 0a 73 6f 6c 76 | have to| be.solv|
|00001600| 65 64 3c 41 20 4e 41 4d | 45 3d 22 74 65 78 32 68 |ed<A NAM|E="tex2h|
|00001610| 74 6d 6c 32 22 20 48 52 | 45 46 3d 22 66 6f 6f 74 |tml2" HR|EF="foot|
|00001620| 6e 6f 64 65 5f 6d 6e 2e | 68 74 6d 6c 23 66 6f 6f |node_mn.|html#foo|
|00001630| 74 33 36 22 20 54 41 52 | 47 45 54 3d 22 66 6f 6f |t36" TAR|GET="foo|
|00001640| 74 65 72 22 3e 3c 53 55 | 50 3e 31 3c 2f 53 55 50 |ter"><SU|P>1</SUP|
|00001650| 3e 3c 2f 41 3e 2e 20 54 | 68 65 20 6f 62 6a 65 63 |></A>. T|he objec|
|00001660| 74 20 6f 66 20 70 72 6f | 62 6c 65 6d 0a 72 65 64 |t of pro|blem.red|
|00001670| 75 63 74 69 6f 6e 20 69 | 73 20 74 6f 20 65 76 65 |uction i|s to eve|
|00001680| 6e 74 75 61 6c 6c 79 20 | 70 72 6f 64 75 63 65 20 |ntually |produce |
|00001690| 61 20 73 65 74 20 6f 66 | 20 3c 45 4d 3e 70 72 69 |a set of| <EM>pri|
|000016a0| 6d 69 74 69 76 65 20 70 | 72 6f 62 6c 65 6d 73 26 |mitive p|roblems&|
|000016b0| 6e 62 73 70 3b 3c 2f 45 | 4d 3e 3c 41 20 49 44 3d |nbsp;</E|M><A ID=|
|000016c0| 22 70 72 69 6d 70 72 6f | 62 22 3e 3c 2f 41 3e 77 |"primpro|b"></A>w|
|000016d0| 68 6f 73 65 20 73 6f 6c | 75 74 69 6f 6e 73 20 61 |hose sol|utions a|
|000016e0| 72 65 20 72 65 67 61 72 | 64 65 64 20 61 73 20 74 |re regar|ded as t|
|000016f0| 72 69 76 69 61 6c 3a 20 | 61 74 20 74 68 69 73 20 |rivial: |at this |
|00001700| 73 74 61 67 65 20 74 68 | 65 20 70 72 6f 63 65 73 |stage th|e proces|
|00001710| 73 20 6f 66 20 64 69 76 | 69 64 69 6e 67 0a 70 72 |s of div|iding.pr|
|00001720| 6f 62 6c 65 6d 73 20 69 | 6e 74 6f 20 73 75 62 2d |oblems i|nto sub-|
|00001730| 70 72 6f 62 6c 65 6d 73 | 20 68 61 6c 74 73 2e 0a |problems| halts..|
|00001740| 0a 3c 50 3e 0a 54 68 65 | 73 65 20 74 77 6f 20 61 |.<P>.The|se two a|
|00001750| 70 70 72 6f 61 63 68 65 | 73 2c 20 73 74 61 74 65 |pproache|s, state|
|00001760| 20 73 70 61 63 65 20 73 | 65 61 72 63 68 20 61 6e | space s|earch an|
|00001770| 64 20 70 72 6f 62 6c 65 | 6d 20 72 65 64 75 63 74 |d proble|m reduct|
|00001780| 69 6f 6e 2c 20 61 72 65 | 20 74 77 6f 20 6f 66 20 |ion, are| two of |
|00001790| 74 68 65 0a 6d 6f 73 74 | 20 63 6f 6d 6d 6f 6e 20 |the.most| common |
|000017a0| 6d 65 74 68 6f 64 73 20 | 75 73 65 64 20 69 6e 20 |methods |used in |
|000017b0| 70 72 6f 62 6c 65 6d 20 | 72 65 70 72 65 73 65 6e |problem |represen|
|000017c0| 74 61 74 69 6f 6e 2c 20 | 61 6c 74 68 6f 75 67 68 |tation, |although|
|000017d0| 20 76 61 72 69 61 74 69 | 6f 6e 73 20 6f 66 0a 74 | variati|ons of.t|
|000017e0| 68 65 73 65 20 61 70 70 | 72 6f 61 63 68 65 73 2c |hese app|roaches,|
|000017f0| 20 61 73 20 75 73 65 64 | 20 69 6e 2c 20 65 2e 67 | as used| in, e.g|
|00001800| 2e 2c 20 67 61 6d 65 2d | 70 6c 61 79 69 6e 67 20 |., game-|playing |
|00001810| 61 72 65 20 61 6c 73 6f | 20 70 6f 73 73 69 62 6c |are also| possibl|
|00001820| 65 0a 28 73 65 65 20 42 | 61 72 72 28 31 39 38 31 |e.(see B|arr(1981|
|00001830| 29 2c 20 70 2e 38 34 66 | 66 2e 2c 20 52 69 74 63 |), p.84f|f., Ritc|
|00001840| 68 28 31 39 38 33 29 2c | 20 70 2e 31 31 33 66 66 |h(1983),| p.113ff|
|00001850| 2e 2c 20 4e 69 6c 73 73 | 6f 6e 28 31 39 37 31 29 |., Nilss|on(1971)|
|00001860| 2c 20 70 2e 31 33 37 66 | 66 29 2e 0a 0a 3c 50 3e |, p.137f|f)...<P>|
|00001870| 0a 0a 3c 48 52 3e 0a 0a | 3c 2f 42 4f 44 59 3e 0a |..<HR>..|</BODY>.|
|00001880| 3c 2f 48 54 4d 4c 3e 0a | |</HTML>.| |
+--------+-------------------------+-------------------------+--------+--------+
