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 54 72 | 65 65 73 20 61 6e 64 20 |ts of Tr|ees and |
|000000b0| 67 72 61 70 68 73 3c 2f | 54 49 54 4c 45 3e 0a 0a |graphs</|TITLE>..|
|000000c0| 3c 4d 45 54 41 20 48 54 | 54 50 2d 45 51 55 49 56 |<META HT|TP-EQUIV|
|000000d0| 3d 22 43 6f 6e 74 65 6e | 74 2d 54 79 70 65 22 20 |="Conten|t-Type" |
|000000e0| 43 4f 4e 54 45 4e 54 3d | 22 74 65 78 74 2f 68 74 |CONTENT=|"text/ht|
|000000f0| 6d 6c 3b 20 63 68 61 72 | 73 65 74 3d 75 74 66 2d |ml; char|set=utf-|
|00000100| 38 22 3e 0a 3c 4d 45 54 | 41 20 4e 41 4d 45 3d 22 |8">.<MET|A NAME="|
|00000110| 76 69 65 77 70 6f 72 74 | 22 20 43 4f 4e 54 45 4e |viewport|" CONTEN|
|00000120| 54 3d 22 77 69 64 74 68 | 3d 64 65 76 69 63 65 2d |T="width|=device-|
|00000130| 77 69 64 74 68 2c 20 69 | 6e 69 74 69 61 6c 2d 73 |width, i|nitial-s|
|00000140| 63 61 6c 65 3d 31 2e 30 | 22 3e 0a 3c 4d 45 54 41 |cale=1.0|">.<META|
|00000150| 20 4e 41 4d 45 3d 22 47 | 65 6e 65 72 61 74 6f 72 | NAME="G|enerator|
|00000160| 22 20 43 4f 4e 54 45 4e | 54 3d 22 4c 61 54 65 58 |" CONTEN|T="LaTeX|
|00000170| 32 48 54 4d 4c 20 76 32 | 30 32 32 22 3e 0a 0a 3c |2HTML v2|022">..<|
|00000180| 4c 49 4e 4b 20 52 45 4c | 3d 22 53 54 59 4c 45 53 |LINK REL|="STYLES|
|00000190| 48 45 45 54 22 20 48 52 | 45 46 3d 22 53 45 41 52 |HEET" HR|EF="SEAR|
|000001a0| 43 48 2e 63 73 73 22 3e | 0a 0a 3c 4c 49 4e 4b 20 |CH.css">|..<LINK |
|000001b0| 52 45 4c 3d 22 6e 65 78 | 74 22 20 48 52 45 46 3d |REL="nex|t" HREF=|
|000001c0| 22 6e 6f 64 65 35 5f 6d | 6e 2e 68 74 6d 6c 22 3e |"node5_m|n.html">|
|000001d0| 0a 3c 4c 49 4e 4b 20 52 | 45 4c 3d 22 70 72 65 76 |.<LINK R|EL="prev|
|000001e0| 69 6f 75 73 22 20 48 52 | 45 46 3d 22 6e 6f 64 65 |ious" HR|EF="node|
|000001f0| 33 5f 6d 6e 2e 68 74 6d | 6c 22 3e 0a 3c 4c 49 4e |3_mn.htm|l">.<LIN|
|00000200| 4b 20 52 45 4c 3d 22 75 | 70 22 20 48 52 45 46 3d |K REL="u|p" HREF=|
|00000210| 22 6e 6f 64 65 32 5f 6d | 6e 2e 68 74 6d 6c 22 3e |"node2_m|n.html">|
|00000220| 0a 3c 4c 49 4e 4b 20 52 | 45 4c 3d 22 6e 65 78 74 |.<LINK R|EL="next|
|00000230| 22 20 48 52 45 46 3d 22 | 6e 6f 64 65 35 5f 6d 6e |" HREF="|node5_mn|
|00000240| 2e 68 74 6d 6c 22 3e 0a | 3c 2f 48 45 41 44 3e 0a |.html">.|</HEAD>.|
|00000250| 20 0a 3c 42 4f 44 59 20 | 62 67 63 6f 6c 6f 72 3d | .<BODY |bgcolor=|
|00000260| 22 23 66 66 66 66 66 66 | 22 20 74 65 78 74 3d 22 |"#ffffff|" text="|
|00000270| 23 30 30 30 30 30 30 22 | 20 6c 69 6e 6b 3d 22 23 |#000000"| link="#|
|00000280| 39 39 34 34 45 45 22 20 | 76 6c 69 6e 6b 3d 22 23 |9944EE" |vlink="#|
|00000290| 30 30 30 30 66 66 22 20 | 61 6c 69 6e 6b 3d 22 23 |0000ff" |alink="#|
|000002a0| 30 30 66 66 30 30 22 3e | 0a 0a 3c 48 32 3e 3c 41 |00ff00">|..<H2><A|
|000002b0| 20 49 44 3d 22 53 45 43 | 54 49 4f 4e 30 30 30 32 | ID="SEC|TION0002|
|000002c0| 32 30 30 30 30 30 30 30 | 30 30 30 30 30 30 30 30 |20000000|00000000|
|000002d0| 22 3e 0a 54 72 65 65 73 | 20 61 6e 64 20 67 72 61 |">.Trees| and gra|
|000002e0| 70 68 73 3c 2f 41 3e 0a | 3c 2f 48 32 3e 0a 0a 3c |phs</A>.|</H2>..<|
|000002f0| 50 3e 0a 53 6f 20 66 61 | 72 20 77 65 20 68 61 76 |P>.So fa|r we hav|
|00000300| 65 20 73 65 65 6e 20 74 | 68 61 74 20 61 20 73 74 |e seen t|hat a st|
|00000310| 61 74 65 20 73 70 61 63 | 65 20 72 65 70 72 65 73 |ate spac|e repres|
|00000320| 65 6e 74 61 74 69 6f 6e | 20 63 6f 6e 73 69 73 74 |entation| consist|
|00000330| 73 20 6f 66 20 74 68 65 | 20 66 6f 6c 6c 6f 77 69 |s of the| followi|
|00000340| 6e 67 0a 63 6f 6d 70 6f | 6e 65 6e 74 73 3a 0a 0a |ng.compo|nents:..|
|00000350| 3c 55 4c 3e 0a 3c 4c 49 | 3e 54 68 65 20 73 74 61 |<UL>.<LI|>The sta|
|00000360| 74 65 20 64 65 73 63 72 | 69 70 74 69 6f 6e 73 2e |te descr|iptions.|
|00000370| 0a 3c 2f 4c 49 3e 0a 3c | 4c 49 3e 41 20 73 74 61 |.</LI>.<|LI>A sta|
|00000380| 72 74 20 73 74 61 74 65 | 2c 20 64 65 73 63 72 69 |rt state|, descri|
|00000390| 62 69 6e 67 20 74 68 65 | 20 73 69 74 75 61 74 69 |bing the| situati|
|000003a0| 6f 6e 20 66 72 6f 6d 20 | 77 68 69 63 68 20 74 68 |on from |which th|
|000003b0| 65 0a 20 20 20 20 70 72 | 6f 62 6c 65 6d 2d 73 6f |e. pr|oblem-so|
|000003c0| 6c 76 69 6e 67 20 70 72 | 6f 63 65 73 73 20 6d 61 |lving pr|ocess ma|
|000003d0| 79 20 73 74 61 72 74 2e | 0a 3c 2f 4c 49 3e 0a 3c |y start.|.</LI>.<|
|000003e0| 4c 49 3e 41 20 67 6f 61 | 6c 20 73 74 61 74 65 2c |LI>A goa|l state,|
|000003f0| 20 64 65 73 63 72 69 62 | 69 6e 67 20 61 6e 20 61 | describ|ing an a|
|00000400| 63 63 65 70 74 61 62 6c | 65 20 73 6f 6c 75 74 69 |cceptabl|e soluti|
|00000410| 6f 6e 20 74 6f 20 74 68 | 65 20 70 72 6f 62 6c 65 |on to th|e proble|
|00000420| 6d 2e 0a 3c 2f 4c 49 3e | 0a 3c 4c 49 3e 41 20 73 |m..</LI>|.<LI>A s|
|00000430| 65 74 20 6f 66 20 6f 70 | 65 72 61 74 6f 72 73 20 |et of op|erators |
|00000440| 64 65 73 63 72 69 62 69 | 6e 67 20 68 6f 77 20 74 |describi|ng how t|
|00000450| 6f 20 74 72 61 6e 73 66 | 6f 72 6d 20 6f 6e 65 20 |o transf|orm one |
|00000460| 73 74 61 74 65 20 69 6e | 74 6f 0a 20 20 20 20 61 |state in|to. a|
|00000470| 6e 6f 74 68 65 72 2e 0a | 3c 2f 4c 49 3e 0a 3c 2f |nother..|</LI>.</|
|00000480| 55 4c 3e 0a 0a 3c 50 3e | 0a 0a 3c 50 3e 3c 50 3e |UL>..<P>|..<P><P>|
|00000490| 0a 3c 42 52 3e 0a 41 6c | 73 6f 2c 20 77 65 20 73 |.<BR>.Al|so, we s|
|000004a0| 61 69 64 20 74 68 61 74 | 20 74 6f 20 73 6f 6c 76 |aid that| to solv|
|000004b0| 65 20 61 20 70 72 6f 62 | 6c 65 6d 20 77 65 20 64 |e a prob|lem we d|
|000004c0| 6f 20 6e 6f 74 20 6e 65 | 65 64 20 74 6f 20 73 65 |o not ne|ed to se|
|000004d0| 61 72 63 68 20 74 68 65 | 20 65 6e 74 69 72 65 20 |arch the| entire |
|000004e0| 73 74 61 74 65 0a 73 70 | 61 63 65 20 62 75 74 20 |state.sp|ace but |
|000004f0| 6f 6e 6c 79 20 74 68 61 | 74 20 70 61 72 74 20 77 |only tha|t part w|
|00000500| 68 69 63 68 20 6c 65 61 | 64 73 20 74 6f 20 61 20 |hich lea|ds to a |
|00000510| 73 6f 6c 75 74 69 6f 6e | 2c 20 69 2e 65 2e 2c 20 |solution|, i.e., |
|00000520| 77 65 20 6e 65 65 64 20 | 74 6f 20 73 65 61 72 63 |we need |to searc|
|00000530| 68 20 66 6f 72 0a 61 6e | 20 61 70 70 72 6f 70 72 |h for.an| appropr|
|00000540| 69 61 74 65 20 6f 70 65 | 72 61 74 6f 72 20 73 65 |iate ope|rator se|
|00000550| 71 75 65 6e 63 65 2c 20 | 74 72 61 6e 73 66 6f 72 |quence, |transfor|
|00000560| 6d 69 6e 67 20 74 68 65 | 20 69 6e 69 74 69 61 6c |ming the| initial|
|00000570| 20 73 74 61 74 65 20 74 | 68 72 6f 75 67 68 20 61 | state t|hrough a|
|00000580| 0a 6e 75 6d 62 65 72 20 | 6f 66 20 69 6e 74 65 72 |.number |of inter|
|00000590| 6d 65 64 69 61 74 65 20 | 73 74 61 74 65 73 20 69 |mediate |states i|
|000005a0| 6e 74 6f 20 74 68 65 20 | 67 6f 61 6c 20 73 74 61 |nto the |goal sta|
|000005b0| 74 65 2e 20 54 6f 20 70 | 65 72 66 6f 72 6d 20 74 |te. To p|erform t|
|000005c0| 68 69 73 20 73 65 61 72 | 63 68 0a 73 79 73 74 65 |his sear|ch.syste|
|000005d0| 6d 61 74 69 63 61 6c 6c | 79 20 77 65 20 6e 65 65 |maticall|y we nee|
|000005e0| 64 20 61 20 63 6f 6e 74 | 72 6f 6c 20 73 74 72 61 |d a cont|rol stra|
|000005f0| 74 65 67 79 20 74 68 61 | 74 20 64 65 63 69 64 65 |tegy tha|t decide|
|00000600| 73 20 77 68 69 63 68 20 | 6f 70 65 72 61 74 6f 72 |s which |operator|
|00000610| 20 74 6f 20 61 70 70 6c | 79 0a 6e 65 78 74 20 64 | to appl|y.next d|
|00000620| 75 72 69 6e 67 20 74 68 | 65 20 73 65 61 72 63 68 |uring th|e search|
|00000630| 2e 20 54 68 65 73 65 20 | 73 74 72 61 74 65 67 69 |. These |strategi|
|00000640| 65 73 20 61 72 65 20 63 | 6f 6d 6d 6f 6e 6c 79 20 |es are c|ommonly |
|00000650| 72 65 70 72 65 73 65 6e | 74 65 64 20 75 73 69 6e |represen|ted usin|
|00000660| 67 0a 3c 45 4d 3e 74 72 | 65 65 73 26 6e 62 73 70 |g.<EM>tr|ees |
|00000670| 3b 3c 2f 45 4d 3e 3c 41 | 20 49 44 3d 22 74 72 65 |;</EM><A| ID="tre|
|00000680| 65 70 72 6f 63 22 3e 3c | 2f 41 3e 3c 41 20 4e 41 |eproc"><|/A><A NA|
|00000690| 4d 45 3d 22 74 65 78 32 | 68 74 6d 6c 33 22 20 48 |ME="tex2|html3" H|
|000006a0| 52 45 46 3d 22 66 6f 6f | 74 6e 6f 64 65 5f 6d 6e |REF="foo|tnode_mn|
|000006b0| 2e 68 74 6d 6c 23 66 6f | 6f 74 34 34 22 20 54 41 |.html#fo|ot44" TA|
|000006c0| 52 47 45 54 3d 22 66 6f | 6f 74 65 72 22 3e 3c 53 |RGET="fo|oter"><S|
|000006d0| 55 50 3e 32 3c 2f 53 55 | 50 3e 3c 2f 41 3e 3a 20 |UP>2</SU|P></A>: |
|000006e0| 63 6f 6e 73 74 72 75 63 | 74 20 61 20 74 72 65 65 |construc|t a tree|
|000006f0| 20 77 69 74 68 20 74 68 | 65 20 69 6e 69 74 69 61 | with th|e initia|
|00000700| 6c 20 73 74 61 74 65 20 | 61 73 20 69 74 73 0a 72 |l state |as its.r|
|00000710| 6f 6f 74 2c 20 6e 65 78 | 74 20 67 65 6e 65 72 61 |oot, nex|t genera|
|00000720| 74 65 20 61 6c 6c 20 74 | 68 65 20 6f 66 66 73 70 |te all t|he offsp|
|00000730| 72 69 6e 67 20 6f 66 20 | 74 68 65 20 72 6f 6f 74 |ring of |the root|
|00000740| 20 62 79 20 61 70 70 6c | 79 69 6e 67 20 61 6c 6c | by appl|ying all|
|00000750| 20 6f 66 20 74 68 65 0a | 61 70 70 6c 69 63 61 62 | of the.|applicab|
|00000760| 6c 65 20 6f 70 65 72 61 | 74 6f 72 73 20 74 6f 20 |le opera|tors to |
|00000770| 74 68 65 20 69 6e 69 74 | 69 61 6c 20 73 74 61 74 |the init|ial stat|
|00000780| 65 2c 20 6e 65 78 74 20 | 66 6f 72 20 65 76 65 72 |e, next |for ever|
|00000790| 79 20 6c 65 61 66 20 6e | 6f 64 65 20 67 65 6e 65 |y leaf n|ode gene|
|000007a0| 72 61 74 65 20 69 74 73 | 0a 73 75 63 63 65 73 73 |rate its|.success|
|000007b0| 6f 72 73 20 62 79 20 61 | 70 70 6c 79 69 6e 67 20 |ors by a|pplying |
|000007c0| 61 6c 6c 20 6f 66 20 74 | 68 65 20 61 70 70 6c 69 |all of t|he appli|
|000007d0| 63 61 62 6c 65 20 6f 70 | 65 72 61 74 6f 72 73 2c |cable op|erators,|
|000007e0| 20 65 74 63 2e 20 57 68 | 65 6e 20 74 68 65 73 65 | etc. Wh|en these|
|000007f0| 20 73 74 65 70 73 0a 61 | 72 65 20 70 65 72 66 6f | steps.a|re perfo|
|00000800| 72 6d 65 64 20 61 20 73 | 74 72 75 63 74 75 72 65 |rmed a s|tructure|
|00000810| 20 61 73 20 64 69 73 70 | 6c 61 79 65 64 20 69 6e | as disp|layed in|
|00000820| 20 66 69 67 2e 26 6e 62 | 73 70 3b 3c 41 20 48 52 | fig.&nb|sp;<A HR|
|00000830| 45 46 3d 22 6e 6f 64 65 | 34 5f 63 74 2e 68 74 6d |EF="node|4_ct.htm|
|00000840| 6c 23 66 69 67 74 72 65 | 65 22 3e 3c 49 4d 47 20 |l#figtre|e"><IMG |
|00000850| 20 41 4c 54 3d 22 5b 2a | 5d 22 20 53 52 43 3d 22 | ALT="[*|]" SRC="|
|00000860| 63 72 6f 73 73 72 65 66 | 2e 70 6e 67 22 3e 3c 2f |crossref|.png"></|
|00000870| 41 3e 20 73 74 72 75 63 | 74 75 72 65 20 77 69 6c |A> struc|ture wil|
|00000880| 6c 0a 61 72 69 73 65 2e | 0a 0a 3c 44 49 56 20 63 |l.arise.|..<DIV c|
|00000890| 6c 61 73 73 3d 22 43 45 | 4e 54 45 52 22 3e 3c 41 |lass="CE|NTER"><A|
|000008a0| 20 49 44 3d 22 66 69 67 | 74 72 65 65 22 3e 3c 2f | ID="fig|tree"></|
|000008b0| 41 3e 3c 41 20 49 44 3d | 22 37 32 22 3e 3c 2f 41 |A><A ID=|"72"></A|
|000008c0| 3e 0a 3c 54 41 42 4c 45 | 3e 0a 3c 43 41 50 54 49 |>.<TABLE|>.<CAPTI|
|000008d0| 4f 4e 20 63 6c 61 73 73 | 3d 22 42 4f 54 54 4f 4d |ON class|="BOTTOM|
|000008e0| 22 3e 3c 53 54 52 4f 4e | 47 3e 46 69 67 75 72 65 |"><STRON|G>Figure|
|000008f0| 3a 3c 2f 53 54 52 4f 4e | 47 3e 0a 53 74 61 72 74 |:</STRON|G>.Start|
|00000900| 20 6f 66 20 61 20 73 65 | 61 72 63 68 20 74 72 65 | of a se|arch tre|
|00000910| 65 3c 2f 43 41 50 54 49 | 4f 4e 3e 0a 3c 54 52 3e |e</CAPTI|ON>.<TR>|
|00000920| 3c 54 44 3e 3c 49 4d 47 | 0a 20 53 54 59 4c 45 3d |<TD><IMG|. STYLE=|
|00000930| 22 68 65 69 67 68 74 3a | 20 32 38 36 2e 37 36 65 |"height:| 286.76e|
|00000940| 78 3b 20 22 20 53 52 43 | 3d 22 69 6d 67 32 2e 70 |x; " SRC|="img2.p|
|00000950| 6e 67 22 0a 20 41 4c 54 | 3d 22 5c 62 65 67 69 6e |ng". ALT|="\begin|
|00000960| 7b 66 69 67 75 72 65 7d | 5c 62 65 67 69 6e 7b 63 |{figure}|\begin{c|
|00000970| 65 6e 74 65 72 7d 0a 5c | 75 6e 69 74 6c 65 6e 67 |enter}.\|unitleng|
|00000980| 74 68 3d 30 2e 37 30 6d | 6d 5c 6c 69 6e 65 74 68 |th=0.70m|m\lineth|
|00000990| 69 63 6b 6e 65 73 73 7b | 30 2e 34 70 74 7d 0a 5c |ickness{|0.4pt}.\|
|000009a0| 62 65 67 69 6e 7b 70 2e | 2e 2e 0a 2e 2e 2e 7d 0a |begin{p.|......}.|
|000009b0| 5c 70 75 74 28 37 30 2e | 30 30 2c 31 30 2e 30 30 |\put(70.|00,10.00|
|000009c0| 29 7b 5c 6d 61 6b 65 62 | 6f 78 28 30 2c 30 29 5b |){\makeb|ox(0,0)[|
|000009d0| 63 63 5d 7b 67 7d 7d 0a | 5c 65 6e 64 7b 70 69 63 |cc]{g}}.|\end{pic|
|000009e0| 74 75 72 65 7d 20 5c 65 | 6e 64 7b 63 65 6e 74 65 |ture} \e|nd{cente|
|000009f0| 72 7d 5c 65 6e 64 7b 66 | 69 67 75 72 65 7d 22 3e |r}\end{f|igure}">|
|00000a00| 3c 2f 54 44 3e 3c 2f 54 | 52 3e 0a 3c 2f 54 41 42 |</TD></T|R>.</TAB|
|00000a10| 4c 45 3e 0a 3c 2f 44 49 | 56 3e 0a 49 6e 20 74 68 |LE>.</DI|V>.In th|
|00000a20| 69 73 20 72 65 70 72 65 | 73 65 6e 74 61 74 69 6f |is repre|sentatio|
|00000a30| 6e 20 65 76 65 72 79 20 | 6c 65 61 66 20 6e 6f 64 |n every |leaf nod|
|00000a40| 65 20 63 6f 72 72 65 73 | 70 6f 6e 64 73 20 74 6f |e corres|ponds to|
|00000a50| 20 61 20 73 74 61 74 65 | 2c 20 77 69 74 68 20 74 | a state|, with t|
|00000a60| 68 65 20 72 6f 6f 74 0a | 6e 6f 64 65 20 72 65 70 |he root.|node rep|
|00000a70| 72 65 73 65 6e 74 69 6e | 67 20 74 68 65 20 69 6e |resentin|g the in|
|00000a80| 69 74 69 61 6c 20 73 74 | 61 74 65 2e 20 45 61 63 |itial st|ate. Eac|
|00000a90| 68 20 6f 70 65 72 61 74 | 6f 72 20 61 70 70 6c 69 |h operat|or appli|
|00000aa0| 63 61 74 69 6f 6e 20 69 | 73 20 72 65 70 72 65 73 |cation i|s repres|
|00000ab0| 65 6e 74 65 64 20 62 79 | 0a 61 20 63 6f 6e 6e 65 |ented by|.a conne|
|00000ac0| 63 74 69 6f 6e 20 62 65 | 74 77 65 65 6e 20 74 77 |ction be|tween tw|
|00000ad0| 6f 20 6e 6f 64 65 73 2e | 0a 0a 3c 50 3e 0a 54 72 |o nodes.|..<P>.Tr|
|00000ae0| 65 65 73 20 61 72 65 20 | 61 20 73 70 65 63 69 61 |ees are |a specia|
|00000af0| 6c 20 63 61 73 65 20 6f | 66 20 61 20 6d 6f 72 65 |l case o|f a more|
|00000b00| 20 67 65 6e 65 72 61 6c | 20 73 74 72 75 63 74 75 | general| structu|
|00000b10| 72 65 20 63 61 6c 6c 65 | 64 20 61 20 3c 45 4d 3e |re calle|d a <EM>|
|00000b20| 67 72 61 70 68 26 6e 62 | 73 70 3b 3c 2f 45 4d 3e |graph&nb|sp;</EM>|
|00000b30| 0a 3c 41 20 4e 41 4d 45 | 3d 22 74 65 78 32 68 74 |.<A NAME|="tex2ht|
|00000b40| 6d 6c 35 22 20 48 52 45 | 46 3d 22 66 6f 6f 74 6e |ml5" HRE|F="footn|
|00000b50| 6f 64 65 5f 6d 6e 2e 68 | 74 6d 6c 23 66 6f 6f 74 |ode_mn.h|tml#foot|
|00000b60| 37 37 22 20 54 41 52 47 | 45 54 3d 22 66 6f 6f 74 |77" TARG|ET="foot|
|00000b70| 65 72 22 3e 3c 53 55 50 | 3e 33 3c 2f 53 55 50 3e |er"><SUP|>3</SUP>|
|00000b80| 3c 2f 41 3e 2e 0a 41 20 | 74 72 65 65 20 69 73 20 |</A>..A |tree is |
|00000b90| 61 20 67 72 61 70 68 20 | 65 61 63 68 20 6f 66 20 |a graph |each of |
|00000ba0| 77 68 6f 73 65 20 6e 6f | 64 65 73 20 68 61 73 20 |whose no|des has |
|00000bb0| 61 20 75 6e 69 71 75 65 | 20 70 61 72 65 6e 74 20 |a unique| parent |
|00000bc0| 28 65 78 63 65 70 74 20 | 66 6f 72 20 74 68 65 20 |(except |for the |
|00000bd0| 72 6f 6f 74 0a 6e 6f 64 | 65 2c 20 77 68 69 63 68 |root.nod|e, which|
|00000be0| 20 68 61 73 20 6e 6f 20 | 70 61 72 65 6e 74 29 2e | has no |parent).|
|00000bf0| 20 53 65 61 72 63 68 69 | 6e 67 20 61 20 74 72 65 | Searchi|ng a tre|
|00000c00| 65 20 69 73 20 65 61 73 | 69 65 72 20 74 68 61 6e |e is eas|ier than|
|00000c10| 20 73 65 61 72 63 68 69 | 6e 67 20 61 20 67 72 61 | searchi|ng a gra|
|00000c20| 70 68 2c 0a 62 65 63 61 | 75 73 65 20 77 68 65 6e |ph,.beca|use when|
|00000c30| 20 61 20 6e 65 77 20 6e | 6f 64 65 20 69 73 20 67 | a new n|ode is g|
|00000c40| 65 6e 65 72 61 74 65 64 | 20 69 6e 20 74 68 65 20 |enerated| in the |
|00000c50| 74 72 65 65 20 77 65 20 | 63 61 6e 20 62 65 20 73 |tree we |can be s|
|00000c60| 75 72 65 20 69 74 20 68 | 61 73 20 6e 6f 74 0a 62 |ure it h|as not.b|
|00000c70| 65 65 6e 20 67 65 6e 65 | 72 61 74 65 64 20 62 65 |een gene|rated be|
|00000c80| 66 6f 72 65 2e 20 54 68 | 69 73 20 69 73 20 74 72 |fore. Th|is is tr|
|00000c90| 75 65 20 62 65 63 61 75 | 73 65 20 65 76 65 72 79 |ue becau|se every|
|00000ca0| 20 6e 6f 64 65 20 68 61 | 73 20 6f 6e 6c 79 20 6f | node ha|s only o|
|00000cb0| 6e 65 20 70 61 72 65 6e | 74 2c 20 73 6f 0a 74 68 |ne paren|t, so.th|
|00000cc0| 65 72 65 20 63 61 6e 6e | 6f 74 20 62 65 20 74 77 |ere cann|ot be tw|
|00000cd0| 6f 20 6f 72 20 6d 6f 72 | 65 20 64 69 66 66 65 72 |o or mor|e differ|
|00000ce0| 65 6e 74 20 70 61 74 68 | 73 20 6c 65 61 64 69 6e |ent path|s leadin|
|00000cf0| 67 20 74 6f 20 74 68 65 | 20 73 61 6d 65 20 6e 6f |g to the| same no|
|00000d00| 64 65 2e 20 49 6e 20 61 | 0a 67 72 61 70 68 2c 20 |de. In a|.graph, |
|00000d10| 68 6f 77 65 76 65 72 2c | 20 6e 6f 64 65 73 20 75 |however,| nodes u|
|00000d20| 73 75 61 6c 6c 79 20 68 | 61 76 65 20 6d 6f 72 65 |sually h|ave more|
|00000d30| 20 74 68 61 6e 20 6f 6e | 65 20 70 61 72 65 6e 74 | than on|e parent|
|00000d40| 2e 20 20 54 68 65 72 65 | 66 6f 72 65 2c 20 77 68 |. There|fore, wh|
|00000d50| 65 6e 0a 73 65 61 72 63 | 68 69 6e 67 20 61 20 67 |en.searc|hing a g|
|00000d60| 72 61 70 68 20 6f 6e 65 | 20 73 68 6f 75 6c 64 20 |raph one| should |
|00000d70| 6d 61 6b 65 20 70 72 6f | 76 69 73 69 6f 6e 73 20 |make pro|visions |
|00000d80| 74 6f 20 64 65 61 6c 20 | 77 69 74 68 20 74 68 65 |to deal |with the|
|00000d90| 73 65 20 73 69 74 75 61 | 74 69 6f 6e 73 2e 0a 53 |se situa|tions..S|
|00000da0| 61 79 69 6e 67 20 74 68 | 61 74 20 61 20 6e 6f 64 |aying th|at a nod|
|00000db0| 65 20 68 61 73 20 6d 6f | 72 65 20 74 68 61 6e 20 |e has mo|re than |
|00000dc0| 6f 6e 65 20 70 61 72 65 | 6e 74 20 6d 65 61 6e 73 |one pare|nt means|
|00000dd0| 20 74 68 61 74 20 74 68 | 65 20 6e 6f 64 65 20 69 | that th|e node i|
|00000de0| 73 20 67 65 6e 65 72 61 | 74 65 64 0a 62 79 20 61 |s genera|ted.by a|
|00000df0| 20 64 69 66 66 65 72 65 | 6e 74 20 73 65 71 75 65 | differe|nt seque|
|00000e00| 6e 63 65 20 6f 66 20 74 | 68 65 20 73 61 6d 65 20 |nce of t|he same |
|00000e10| 6f 70 65 72 61 74 6f 72 | 73 2e 20 54 68 61 74 20 |operator|s. That |
|00000e20| 69 73 2c 20 74 68 65 20 | 73 61 6d 65 20 6e 6f 64 |is, the |same nod|
|00000e30| 65 20 6d 61 79 20 62 65 | 0a 70 61 72 74 20 6f 66 |e may be|.part of|
|00000e40| 20 73 65 76 65 72 61 6c | 20 70 61 74 68 73 2c 20 | several| paths, |
|00000e50| 61 6e 64 20 63 6f 6e 74 | 69 6e 75 69 6e 67 20 74 |and cont|inuing t|
|00000e60| 68 65 20 70 72 6f 63 65 | 73 73 69 6e 67 20 6f 66 |he proce|ssing of|
|00000e70| 20 62 6f 74 68 20 74 68 | 65 73 65 20 6e 6f 64 65 | both th|ese node|
|00000e80| 73 20 28 77 68 69 63 68 | 20 61 72 65 0a 72 65 61 |s (which| are.rea|
|00000e90| 6c 6c 79 20 74 68 65 20 | 73 61 6d 65 20 6e 6f 64 |lly the |same nod|
|00000ea0| 65 29 20 77 6f 75 6c 64 | 20 62 65 20 72 65 64 75 |e) would| be redu|
|00000eb0| 6e 64 61 6e 74 20 61 6e | 64 20 61 20 77 61 73 74 |ndant an|d a wast|
|00000ec0| 65 20 6f 66 20 65 66 66 | 6f 72 74 2e 20 54 68 69 |e of eff|ort. Thi|
|00000ed0| 73 20 63 61 6e 20 62 65 | 0a 61 76 6f 69 64 65 64 |s can be|.avoided|
|00000ee0| 20 61 74 20 74 68 65 20 | 70 72 69 63 65 20 6f 66 | at the |price of|
|00000ef0| 20 61 64 64 69 74 69 6f | 6e 61 6c 20 62 6f 6f 6b | additio|nal book|
|00000f00| 6b 65 65 70 69 6e 67 2e | 20 49 6e 73 74 65 61 64 |keeping.| Instead|
|00000f10| 20 6f 66 20 74 72 61 76 | 65 72 73 69 6e 67 20 61 | of trav|ersing a|
|00000f20| 20 74 72 65 65 20 77 65 | 0a 74 72 61 76 65 72 73 | tree we|.travers|
|00000f30| 65 20 61 20 3c 45 4d 3e | 64 69 72 65 63 74 65 64 |e a <EM>|directed|
|00000f40| 20 67 72 61 70 68 26 6e | 62 73 70 3b 3c 2f 45 4d | graph&n|bsp;</EM|
|00000f50| 3e 3c 41 20 4e 41 4d 45 | 3d 22 74 65 78 32 68 74 |><A NAME|="tex2ht|
|00000f60| 6d 6c 36 22 20 48 52 45 | 46 3d 22 66 6f 6f 74 6e |ml6" HRE|F="footn|
|00000f70| 6f 64 65 5f 6d 6e 2e 68 | 74 6d 6c 23 66 6f 6f 74 |ode_mn.h|tml#foot|
|00000f80| 37 39 22 20 54 41 52 47 | 45 54 3d 22 66 6f 6f 74 |79" TARG|ET="foot|
|00000f90| 65 72 22 3e 3c 53 55 50 | 3e 34 3c 2f 53 55 50 3e |er"><SUP|>4</SUP>|
|00000fa0| 3c 2f 41 3e 3a 20 65 76 | 65 72 79 20 74 69 6d 65 |</A>: ev|ery time|
|00000fb0| 20 61 0a 6e 6f 64 65 20 | 69 73 20 67 65 6e 65 72 | a.node |is gener|
|00000fc0| 61 74 65 64 20 77 65 20 | 65 78 61 6d 69 6e 65 20 |ated we |examine |
|00000fd0| 74 68 65 20 73 65 74 20 | 6f 66 20 6e 6f 64 65 73 |the set |of nodes|
|00000fe0| 20 67 65 6e 65 72 61 74 | 65 64 20 73 6f 20 66 61 | generat|ed so fa|
|00000ff0| 72 20 74 6f 20 73 65 65 | 20 69 66 20 74 68 69 73 |r to see| if this|
|00001000| 0a 6e 6f 64 65 20 61 6c | 72 65 61 64 79 20 65 78 |.node al|ready ex|
|00001010| 69 73 74 73 20 69 6e 20 | 74 68 65 20 67 72 61 70 |ists in |the grap|
|00001020| 68 2e 20 49 66 20 69 74 | 20 64 6f 65 73 2c 20 77 |h. If it| does, w|
|00001030| 65 20 74 68 72 6f 77 20 | 69 74 20 61 77 61 79 20 |e throw |it away |
|00001040| 28 6e 6f 74 65 3a 20 73 | 65 65 0a 70 61 67 65 26 |(note: s|ee.page&|
|00001050| 6e 62 73 70 3b 3c 41 20 | 48 52 45 46 3d 22 6e 6f |nbsp;<A |HREF="no|
|00001060| 64 65 36 5f 63 74 2e 68 | 74 6d 6c 23 67 72 61 70 |de6_ct.h|tml#grap|
|00001070| 68 2d 6b 65 65 70 22 3e | 3c 49 4d 47 20 20 41 4c |h-keep">|<IMG AL|
|00001080| 54 3d 22 5b 2a 5d 22 20 | 53 52 43 3d 22 63 72 6f |T="[*]" |SRC="cro|
|00001090| 73 73 72 65 66 2e 70 6e | 67 22 3e 3c 2f 41 3e 20 |ssref.pn|g"></A> |
|000010a0| 66 6f 72 20 65 78 63 65 | 70 74 69 6f 6e 73 20 74 |for exce|ptions t|
|000010b0| 6f 20 74 68 69 73 20 72 | 75 6c 65 29 2c 20 69 66 |o this r|ule), if|
|000010c0| 20 6e 6f 74 2c 20 77 65 | 20 61 64 64 20 69 74 20 | not, we| add it |
|000010d0| 74 6f 0a 74 68 65 20 67 | 72 61 70 68 2e 0a 0a 3c |to.the g|raph...<|
|000010e0| 50 3e 0a 54 68 69 73 20 | 77 61 79 20 77 65 20 77 |P>.This |way we w|
|000010f0| 69 6c 6c 20 61 6c 73 6f | 20 61 76 6f 69 64 20 61 |ill also| avoid a|
|00001100| 20 72 65 6c 61 74 65 64 | 20 70 72 6f 62 6c 65 6d | related| problem|
|00001110| 3a 20 69 66 20 77 65 20 | 64 69 64 20 6e 6f 74 20 |: if we |did not |
|00001120| 63 68 65 63 6b 0a 77 68 | 65 74 68 65 72 20 61 20 |check.wh|ether a |
|00001130| 6e 6f 64 65 20 68 61 64 | 20 62 65 65 6e 20 67 65 |node had| been ge|
|00001140| 6e 65 72 61 74 65 64 20 | 62 65 66 6f 72 65 2c 20 |nerated |before, |
|00001150| 74 68 65 20 73 65 61 72 | 63 68 20 70 72 6f 63 65 |the sear|ch proce|
|00001160| 73 73 20 77 6f 75 6c 64 | 20 76 65 72 79 20 6c 69 |ss would| very li|
|00001170| 6b 65 6c 79 0a 65 6e 64 | 20 75 70 20 69 6e 20 61 |kely.end| up in a|
|00001180| 20 3c 45 4d 3e 63 79 63 | 6c 65 26 6e 62 73 70 3b | <EM>cyc|le |
|00001190| 3c 2f 45 4d 3e 2c 20 69 | 6e 20 77 68 69 63 68 20 |</EM>, i|n which |
|000011a0| 74 68 65 20 73 61 6d 65 | 20 73 65 74 20 6f 66 20 |the same| set of |
|000011b0| 6e 6f 64 65 73 20 69 73 | 20 67 65 6e 65 72 61 74 |nodes is| generat|
|000011c0| 65 64 20 6f 76 65 72 20 | 61 6e 64 20 6f 76 65 72 |ed over |and over|
|000011d0| 0a 61 67 61 69 6e 2e 20 | 46 6f 72 20 69 6e 73 74 |.again. |For inst|
|000011e0| 61 6e 63 65 2c 20 77 68 | 65 6e 20 77 65 20 61 70 |ance, wh|en we ap|
|000011f0| 70 6c 79 20 6f 70 65 72 | 61 74 6f 72 20 27 6d 6f |ply oper|ator 'mo|
|00001200| 76 65 20 65 6d 70 74 79 | 20 74 69 6c 65 20 6c 65 |ve empty| tile le|
|00001210| 66 74 27 2c 20 6e 65 78 | 74 20 27 6d 6f 76 65 0a |ft', nex|t 'move.|
|00001220| 65 6d 70 74 79 20 72 69 | 67 68 74 27 20 61 6e 64 |empty ri|ght' and|
|00001230| 20 6e 65 78 74 20 6d 6f | 76 65 20 27 65 6d 70 74 | next mo|ve 'empt|
|00001240| 79 20 74 69 6c 65 20 6c | 65 66 74 27 20 65 74 63 |y tile l|eft' etc|
|00001250| 2e 20 74 6f 20 74 68 65 | 20 38 2d 70 75 7a 7a 6c |. to the| 8-puzzl|
|00001260| 65 2c 20 74 68 65 0a 70 | 72 6f 62 6c 65 6d 2d 73 |e, the.p|roblem-s|
|00001270| 6f 6c 76 69 6e 67 20 70 | 72 6f 63 65 73 73 20 77 |olving p|rocess w|
|00001280| 6f 75 6c 64 20 67 6f 20 | 6f 6e 20 70 72 6f 64 75 |ould go |on produ|
|00001290| 63 69 6e 67 20 74 68 65 | 20 73 61 6d 65 20 6e 6f |cing the| same no|
|000012a0| 64 65 73 20 77 69 74 68 | 6f 75 74 20 65 6e 64 2e |des with|out end.|
|000012b0| 20 57 68 65 6e 0a 77 65 | 20 6d 6f 64 69 66 79 20 | When.we| modify |
|000012c0| 74 68 65 20 73 65 61 72 | 63 68 20 70 72 6f 63 65 |the sear|ch proce|
|000012d0| 64 75 72 65 20 61 73 20 | 64 65 73 63 72 69 62 65 |dure as |describe|
|000012e0| 64 20 61 62 6f 76 65 2c | 20 74 68 69 73 20 73 69 |d above,| this si|
|000012f0| 74 75 61 74 69 6f 6e 20 | 77 69 6c 6c 20 6e 65 76 |tuation |will nev|
|00001300| 65 72 0a 61 72 69 73 65 | 2c 20 62 65 63 61 75 73 |er.arise|, becaus|
|00001310| 65 20 77 65 20 74 72 79 | 20 74 6f 20 6c 6f 6f 6b |e we try| to look|
|00001320| 20 75 70 20 65 76 65 72 | 79 20 6e 6f 64 65 20 74 | up ever|y node t|
|00001330| 68 61 74 20 69 73 20 67 | 65 6e 65 72 61 74 65 64 |hat is g|enerated|
|00001340| 2c 20 62 65 66 6f 72 65 | 20 69 74 20 69 73 0a 61 |, before| it is.a|
|00001350| 64 64 65 64 20 74 6f 20 | 74 68 65 20 67 72 61 70 |dded to |the grap|
|00001360| 68 2e 0a 0a 3c 50 3e 0a | 41 20 73 70 65 63 69 61 |h...<P>.|A specia|
|00001370| 6c 20 6b 69 6e 64 20 6f | 66 20 67 72 61 70 68 20 |l kind o|f graph |
|00001380| 69 73 20 74 68 65 20 3c | 45 4d 3e 41 4e 44 2f 4f |is the <|EM>AND/O|
|00001390| 52 20 67 72 61 70 68 26 | 6e 62 73 70 3b 3c 2f 45 |R graph&|nbsp;</E|
|000013a0| 4d 3e 3c 41 20 49 44 3d | 22 61 6e 64 6f 72 67 72 |M><A ID=|"andorgr|
|000013b0| 61 70 68 22 3e 3c 2f 41 | 3e 20 74 68 61 74 20 69 |aph"></A|> that i|
|000013c0| 73 20 75 73 65 64 20 69 | 6e 0a 70 72 6f 62 6c 65 |s used i|n.proble|
|000013d0| 6d 2d 73 6f 6c 76 69 6e | 67 20 6d 65 74 68 6f 64 |m-solvin|g method|
|000013e0| 73 20 69 6e 76 6f 6c 76 | 69 6e 67 20 70 72 6f 62 |s involv|ing prob|
|000013f0| 6c 65 6d 20 72 65 64 75 | 63 74 69 6f 6e 2e 20 49 |lem redu|ction. I|
|00001400| 6e 20 74 68 65 20 63 61 | 73 65 20 6f 66 20 61 20 |n the ca|se of a |
|00001410| 6e 6f 72 6d 61 6c 0a 67 | 72 61 70 68 2c 20 65 61 |normal.g|raph, ea|
|00001420| 63 68 20 6e 6f 64 65 20 | 72 65 70 72 65 73 65 6e |ch node |represen|
|00001430| 74 73 20 61 20 64 69 66 | 66 65 72 65 6e 74 20 61 |ts a dif|ferent a|
|00001440| 6c 74 65 72 6e 61 74 69 | 76 65 20 73 74 61 74 65 |lternati|ve state|
|00001450| 20 74 6f 20 62 65 20 63 | 68 6f 73 65 6e 20 6e 65 | to be c|hosen ne|
|00001460| 78 74 20 61 6e 64 0a 74 | 68 65 20 73 65 61 72 63 |xt and.t|he searc|
|00001470| 68 20 70 72 6f 63 65 73 | 73 20 6d 61 79 20 63 6f |h proces|s may co|
|00001480| 6e 74 69 6e 75 65 20 61 | 6c 6f 6e 67 20 6f 6e 65 |ntinue a|long one|
|00001490| 20 6f 66 20 74 68 65 73 | 65 20 6e 6f 64 65 73 20 | of thes|e nodes |
|000014a0| 61 72 62 69 74 72 61 74 | 69 6c 79 2e 20 49 6e 20 |arbitrat|ily. In |
|000014b0| 61 0a 70 72 6f 62 6c 65 | 6d 2d 72 65 64 75 63 74 |a.proble|m-reduct|
|000014c0| 69 6f 6e 20 72 65 70 72 | 65 73 65 6e 74 61 74 69 |ion repr|esentati|
|000014d0| 6f 6e 2c 20 68 6f 77 65 | 76 65 72 2c 20 77 65 20 |on, howe|ver, we |
|000014e0| 61 6c 73 6f 20 6e 65 65 | 64 20 74 6f 20 64 65 61 |also nee|d to dea|
|000014f0| 6c 20 77 69 74 68 20 6f | 70 65 72 61 74 6f 72 73 |l with o|perators|
|00001500| 0a 74 68 61 74 20 64 69 | 76 69 64 65 20 74 68 65 |.that di|vide the|
|00001510| 20 6f 72 69 67 69 6e 61 | 6c 20 70 72 6f 62 6c 65 | origina|l proble|
|00001520| 6d 20 69 6e 74 6f 20 61 | 20 73 65 74 20 6f 66 20 |m into a| set of |
|00001530| 73 75 62 2d 70 72 6f 62 | 6c 65 6d 73 20 3c 45 4d |sub-prob|lems <EM|
|00001540| 3e 65 61 63 68 26 6e 62 | 73 70 3b 3c 2f 45 4d 3e |>each&nb|sp;</EM>|
|00001550| 20 6f 66 20 77 68 69 63 | 68 0a 6e 65 65 64 20 74 | of whic|h.need t|
|00001560| 6f 20 62 65 20 73 6f 6c | 76 65 64 2c 20 69 6e 73 |o be sol|ved, ins|
|00001570| 74 65 61 64 20 6f 66 20 | 61 6e 79 20 6f 66 20 74 |tead of |any of t|
|00001580| 68 65 6d 2e 20 46 6f 72 | 20 65 78 61 6d 70 6c 65 |hem. For| example|
|00001590| 2c 20 73 75 70 70 6f 73 | 65 20 70 72 6f 62 6c 65 |, suppos|e proble|
|000015a0| 6d 20 41 20 63 61 6e 20 | 62 65 20 73 6f 6c 76 65 |m A can |be solve|
|000015b0| 64 0a 65 69 74 68 65 72 | 20 62 79 20 73 6f 6c 76 |d.either| by solv|
|000015c0| 69 6e 67 20 70 72 6f 62 | 6c 65 6d 73 20 42 20 61 |ing prob|lems B a|
|000015d0| 6e 64 20 43 20 6f 72 20 | 62 79 20 73 6f 6c 76 69 |nd C or |by solvi|
|000015e0| 6e 67 20 70 72 6f 62 6c | 65 6d 73 20 44 20 61 6e |ng probl|ems D an|
|000015f0| 64 20 45 20 6f 72 20 62 | 79 20 73 6f 6c 76 69 6e |d E or b|y solvin|
|00001600| 67 0a 70 72 6f 62 6c 65 | 6d 20 46 2e 20 54 68 69 |g.proble|m F. Thi|
|00001610| 73 20 73 69 74 75 61 74 | 69 6f 6e 20 69 73 20 64 |s situat|ion is d|
|00001620| 65 70 69 63 74 65 64 20 | 69 6e 20 66 69 67 2e 26 |epicted |in fig.&|
|00001630| 6e 62 73 70 3b 3c 41 20 | 48 52 45 46 3d 22 6e 6f |nbsp;<A |HREF="no|
|00001640| 64 65 34 5f 63 74 2e 68 | 74 6d 6c 23 66 69 67 74 |de4_ct.h|tml#figt|
|00001650| 72 65 65 5f 32 22 3e 3c | 49 4d 47 20 20 41 4c 54 |ree_2"><|IMG ALT|
|00001660| 3d 22 5b 2a 5d 22 20 53 | 52 43 3d 22 63 72 6f 73 |="[*]" S|RC="cros|
|00001670| 73 72 65 66 2e 70 6e 67 | 22 3e 3c 2f 41 3e 2e 0a |sref.png|"></A>..|
|00001680| 0a 3c 44 49 56 20 63 6c | 61 73 73 3d 22 43 45 4e |.<DIV cl|ass="CEN|
|00001690| 54 45 52 22 3e 3c 41 20 | 49 44 3d 22 66 69 67 74 |TER"><A |ID="figt|
|000016a0| 72 65 65 5f 32 22 3e 3c | 2f 41 3e 3c 41 20 49 44 |ree_2"><|/A><A ID|
|000016b0| 3d 22 31 31 30 22 3e 3c | 2f 41 3e 0a 3c 54 41 42 |="110"><|/A>.<TAB|
|000016c0| 4c 45 3e 0a 3c 43 41 50 | 54 49 4f 4e 20 63 6c 61 |LE>.<CAP|TION cla|
|000016d0| 73 73 3d 22 42 4f 54 54 | 4f 4d 22 3e 3c 53 54 52 |ss="BOTT|OM"><STR|
|000016e0| 4f 4e 47 3e 46 69 67 75 | 72 65 3a 3c 2f 53 54 52 |ONG>Figu|re:</STR|
|000016f0| 4f 4e 47 3e 0a 41 20 73 | 74 72 75 63 74 75 72 65 |ONG>.A s|tructure|
|00001700| 20 73 68 6f 77 69 6e 67 | 20 61 6c 74 65 72 6e 61 | showing| alterna|
|00001710| 74 69 76 65 20 73 65 74 | 73 20 6f 66 20 73 75 62 |tive set|s of sub|
|00001720| 70 72 6f 62 6c 65 6d 73 | 20 66 6f 72 20 41 2e 3c |problems| for A.<|
|00001730| 2f 43 41 50 54 49 4f 4e | 3e 0a 3c 54 52 3e 3c 54 |/CAPTION|>.<TR><T|
|00001740| 44 3e 3c 49 4d 47 0a 20 | 53 54 59 4c 45 3d 22 68 |D><IMG. |STYLE="h|
|00001750| 65 69 67 68 74 3a 20 32 | 38 36 2e 37 36 65 78 3b |eight: 2|86.76ex;|
|00001760| 20 22 20 53 52 43 3d 22 | 69 6d 67 33 2e 70 6e 67 | " SRC="|img3.png|
|00001770| 22 0a 20 41 4c 54 3d 22 | 5c 62 65 67 69 6e 7b 66 |". ALT="|\begin{f|
|00001780| 69 67 75 72 65 7d 5c 62 | 65 67 69 6e 7b 63 65 6e |igure}\b|egin{cen|
|00001790| 74 65 72 7d 0a 5c 75 6e | 69 74 6c 65 6e 67 74 68 |ter}.\un|itlength|
|000017a0| 3d 30 2e 37 30 6d 6d 5c | 6c 69 6e 65 74 68 69 63 |=0.70mm\|linethic|
|000017b0| 6b 6e 65 73 73 7b 30 2e | 34 70 74 7d 0a 5c 62 65 |kness{0.|4pt}.\be|
|000017c0| 67 69 6e 7b 70 2e 2e 2e | 0a 2e 2e 2e 36 37 7d 7d |gin{p...|....67}}|
|000017d0| 0a 5c 70 75 74 28 32 36 | 2e 30 30 2c 33 35 2e 30 |.\put(26|.00,35.0|
|000017e0| 30 29 7b 5c 6c 69 6e 65 | 28 36 2c 2d 35 29 7b 37 |0){\line|(6,-5){7|
|000017f0| 2e 30 30 7d 7d 0a 5c 65 | 6e 64 7b 70 69 63 74 75 |.00}}.\e|nd{pictu|
|00001800| 72 65 7d 20 5c 65 6e 64 | 7b 63 65 6e 74 65 72 7d |re} \end|{center}|
|00001810| 5c 65 6e 64 7b 66 69 67 | 75 72 65 7d 22 3e 3c 2f |\end{fig|ure}"></|
|00001820| 54 44 3e 3c 2f 54 52 3e | 0a 3c 2f 54 41 42 4c 45 |TD></TR>|.</TABLE|
|00001830| 3e 0a 3c 2f 44 49 56 3e | 0a 49 6e 20 66 69 67 2e |>.</DIV>|.In fig.|
|00001840| 26 6e 62 73 70 3b 3c 41 | 20 48 52 45 46 3d 22 6e | <A| HREF="n|
|00001850| 6f 64 65 34 5f 63 74 2e | 68 74 6d 6c 23 66 69 67 |ode4_ct.|html#fig|
|00001860| 74 72 65 65 5f 32 22 3e | 3c 49 4d 47 20 20 41 4c |tree_2">|<IMG AL|
|00001870| 54 3d 22 5b 2a 5d 22 20 | 53 52 43 3d 22 63 72 6f |T="[*]" |SRC="cro|
|00001880| 73 73 72 65 66 2e 70 6e | 67 22 3e 3c 2f 41 3e 20 |ssref.pn|g"></A> |
|00001890| 74 68 65 20 6e 6f 64 65 | 73 20 77 68 69 63 68 20 |the node|s which |
|000018a0| 66 6f 72 6d 20 61 20 73 | 65 74 20 74 68 61 74 20 |form a s|et that |
|000018b0| 68 61 73 20 74 6f 20 62 | 65 20 73 6f 6c 76 65 64 |has to b|e solved|
|000018c0| 0a 65 6e 74 69 72 65 6c | 79 20 61 72 65 20 69 6e |.entirel|y are in|
|000018d0| 64 69 63 61 74 65 64 20 | 62 79 20 61 20 73 70 65 |dicated |by a spe|
|000018e0| 63 69 61 6c 20 6d 61 72 | 6b 20 6c 69 6e 6b 69 6e |cial mar|k linkin|
|000018f0| 67 20 74 68 65 69 72 20 | 69 6e 63 6f 6d 69 6e 67 |g their |incoming|
|00001900| 20 61 72 63 73 2e 20 49 | 74 20 69 73 0a 75 73 75 | arcs. I|t is.usu|
|00001910| 61 6c 2c 20 68 6f 77 65 | 76 65 72 2c 20 74 6f 20 |al, howe|ver, to |
|00001920| 69 6e 74 72 6f 64 75 63 | 65 20 73 6f 6d 65 20 65 |introduc|e some e|
|00001930| 78 74 72 61 20 6e 6f 64 | 65 73 20 69 6e 74 6f 20 |xtra nod|es into |
|00001940| 74 68 65 20 73 74 72 75 | 63 74 75 72 65 20 73 6f |the stru|cture so|
|00001950| 20 74 68 61 74 20 65 61 | 63 68 0a 73 65 74 20 63 | that ea|ch.set c|
|00001960| 6f 6e 74 61 69 6e 69 6e | 67 20 6d 6f 72 65 20 74 |ontainin|g more t|
|00001970| 68 61 6e 20 6f 6e 65 20 | 73 75 63 63 65 73 73 6f |han one |successo|
|00001980| 72 20 70 72 6f 62 6c 65 | 6d 20 69 73 20 67 72 6f |r proble|m is gro|
|00001990| 75 70 65 64 20 62 65 6c | 6f 77 20 69 74 73 20 6f |uped bel|ow its o|
|000019a0| 77 6e 0a 70 61 72 65 6e | 74 20 6e 6f 64 65 2e 20 |wn.paren|t node. |
|000019b0| 57 69 74 68 20 74 68 69 | 73 20 63 6f 6e 76 65 6e |With thi|s conven|
|000019c0| 74 69 6f 6e 20 74 68 65 | 20 73 74 72 75 63 74 75 |tion the| structu|
|000019d0| 72 65 20 6f 66 20 66 69 | 67 2e 26 6e 62 73 70 3b |re of fi|g. |
|000019e0| 3c 41 20 48 52 45 46 3d | 22 6e 6f 64 65 34 5f 63 |<A HREF=|"node4_c|
|000019f0| 74 2e 68 74 6d 6c 23 66 | 69 67 74 72 65 65 5f 32 |t.html#f|igtree_2|
|00001a00| 22 3e 3c 49 4d 47 20 20 | 41 4c 54 3d 22 5b 2a 5d |"><IMG |ALT="[*]|
|00001a10| 22 20 53 52 43 3d 22 63 | 72 6f 73 73 72 65 66 2e |" SRC="c|rossref.|
|00001a20| 70 6e 67 22 3e 3c 2f 41 | 3e 0a 62 65 63 6f 6d 65 |png"></A|>.become|
|00001a30| 73 20 61 73 20 73 68 6f | 77 6e 20 69 6e 20 66 69 |s as sho|wn in fi|
|00001a40| 67 2e 26 6e 62 73 70 3b | 3c 41 20 48 52 45 46 3d |g. |<A HREF=|
|00001a50| 22 6e 6f 64 65 34 5f 63 | 74 2e 68 74 6d 6c 23 66 |"node4_c|t.html#f|
|00001a60| 69 67 74 72 65 65 5f 33 | 22 3e 3c 49 4d 47 20 20 |igtree_3|"><IMG |
|00001a70| 41 4c 54 3d 22 5b 2a 5d | 22 20 53 52 43 3d 22 63 |ALT="[*]|" SRC="c|
|00001a80| 72 6f 73 73 72 65 66 2e | 70 6e 67 22 3e 3c 2f 41 |rossref.|png"></A|
|00001a90| 3e 2e 20 49 6e 20 74 68 | 69 73 20 66 69 67 75 72 |>. In th|is figur|
|00001aa0| 65 20 74 68 65 20 61 64 | 64 65 64 20 6e 6f 64 65 |e the ad|ded node|
|00001ab0| 73 0a 6c 61 62 65 6c 6c | 65 64 20 4e 20 61 6e 64 |s.labell|ed N and|
|00001ac0| 20 4d 20 73 65 72 76 65 | 20 61 73 20 65 78 63 6c | M serve| as excl|
|00001ad0| 75 73 69 76 65 20 70 61 | 72 65 6e 74 73 20 66 6f |usive pa|rents fo|
|00001ae0| 72 20 73 65 74 73 20 7b | 42 2c 43 7d 20 61 6e 64 |r sets {|B,C} and|
|00001af0| 20 7b 44 2c 45 7d 2c 20 | 72 65 73 70 65 63 74 69 | {D,E}, |respecti|
|00001b00| 76 65 6c 79 2e 0a 54 68 | 69 73 20 77 61 79 20 6f |vely..Th|is way o|
|00001b10| 6e 65 20 63 61 6e 20 74 | 68 69 6e 6b 20 6f 66 20 |ne can t|hink of |
|00001b20| 4e 20 61 6e 64 20 4d 20 | 61 6e 64 20 46 20 61 73 |N and M |and F as|
|00001b30| 20 3c 45 4d 3e 4f 52 26 | 6e 62 73 70 3b 3c 2f 45 | <EM>OR&|nbsp;</E|
|00001b40| 4d 3e 20 6e 6f 64 65 73 | 2c 20 62 65 63 61 75 73 |M> nodes|, becaus|
|00001b50| 65 20 61 6e 79 20 6f 66 | 20 74 68 65 6d 0a 6d 61 |e any of| them.ma|
|00001b60| 79 20 62 65 20 73 6f 6c | 76 65 64 20 74 6f 20 73 |y be sol|ved to s|
|00001b70| 6f 6c 76 65 20 6e 6f 64 | 65 20 41 2e 20 50 72 6f |olve nod|e A. Pro|
|00001b80| 62 6c 65 6d 20 4e 2c 20 | 68 6f 77 65 76 65 72 2c |blem N, |however,|
|00001b90| 20 69 73 20 72 65 64 75 | 63 65 64 20 74 6f 20 61 | is redu|ced to a|
|00001ba0| 20 73 69 6e 67 6c 65 0a | 73 65 74 20 6f 66 20 73 | single.|set of s|
|00001bb0| 75 62 2d 70 72 6f 62 6c | 65 6d 73 20 42 20 61 6e |ub-probl|ems B an|
|00001bc0| 64 20 43 2c 20 61 6e 64 | 20 3c 45 4d 3e 65 61 63 |d C, and| <EM>eac|
|00001bd0| 68 26 6e 62 73 70 3b 3c | 2f 45 4d 3e 20 6f 66 20 |h <|/EM> of |
|00001be0| 74 68 65 73 65 20 73 75 | 62 2d 70 72 6f 62 6c 65 |these su|b-proble|
|00001bf0| 6d 73 20 6d 75 73 74 0a | 62 65 20 73 6f 6c 76 65 |ms must.|be solve|
|00001c00| 64 20 74 6f 20 73 6f 6c | 76 65 20 4e 2e 20 46 6f |d to sol|ve N. Fo|
|00001c10| 72 20 74 68 69 73 20 72 | 65 61 73 6f 6e 20 6e 6f |r this r|eason no|
|00001c20| 64 65 73 20 42 2c 20 43 | 2c 20 44 20 61 6e 64 20 |des B, C|, D and |
|00001c30| 45 20 61 72 65 20 63 61 | 6c 6c 65 64 20 3c 45 4d |E are ca|lled <EM|
|00001c40| 3e 41 4e 44 26 6e 62 73 | 70 3b 3c 2f 45 4d 3e 0a |>AND&nbs|p;</EM>.|
|00001c50| 6e 6f 64 65 73 2e 20 49 | 6e 20 66 69 67 2e 26 6e |nodes. I|n fig.&n|
|00001c60| 62 73 70 3b 3c 41 20 48 | 52 45 46 3d 22 6e 6f 64 |bsp;<A H|REF="nod|
|00001c70| 65 34 5f 63 74 2e 68 74 | 6d 6c 23 66 69 67 74 72 |e4_ct.ht|ml#figtr|
|00001c80| 65 65 5f 33 22 3e 3c 49 | 4d 47 20 20 41 4c 54 3d |ee_3"><I|MG ALT=|
|00001c90| 22 5b 2a 5d 22 20 53 52 | 43 3d 22 63 72 6f 73 73 |"[*]" SR|C="cross|
|00001ca0| 72 65 66 2e 70 6e 67 22 | 3e 3c 2f 41 3e 20 41 4e |ref.png"|></A> AN|
|00001cb0| 44 20 6e 6f 64 65 73 20 | 61 72 65 20 69 6e 64 69 |D nodes |are indi|
|00001cc0| 63 61 74 65 64 20 62 79 | 20 61 20 6d 61 72 6b 20 |cated by| a mark |
|00001cd0| 6f 6e 20 74 68 65 69 72 | 0a 69 6e 63 6f 6d 69 6e |on their|.incomin|
|00001ce0| 67 20 61 72 63 73 2e 0a | 0a 3c 44 49 56 20 63 6c |g arcs..|.<DIV cl|
|00001cf0| 61 73 73 3d 22 43 45 4e | 54 45 52 22 3e 3c 41 20 |ass="CEN|TER"><A |
|00001d00| 49 44 3d 22 66 69 67 74 | 72 65 65 5f 33 22 3e 3c |ID="figt|ree_3"><|
|00001d10| 2f 41 3e 3c 41 20 49 44 | 3d 22 31 35 33 22 3e 3c |/A><A ID|="153"><|
|00001d20| 2f 41 3e 0a 3c 54 41 42 | 4c 45 3e 0a 3c 43 41 50 |/A>.<TAB|LE>.<CAP|
|00001d30| 54 49 4f 4e 20 63 6c 61 | 73 73 3d 22 42 4f 54 54 |TION cla|ss="BOTT|
|00001d40| 4f 4d 22 3e 3c 53 54 52 | 4f 4e 47 3e 46 69 67 75 |OM"><STR|ONG>Figu|
|00001d50| 72 65 3a 3c 2f 53 54 52 | 4f 4e 47 3e 0a 41 6e 20 |re:</STR|ONG>.An |
|00001d60| 41 4e 44 2f 4f 52 20 67 | 72 61 70 68 3c 2f 43 41 |AND/OR g|raph</CA|
|00001d70| 50 54 49 4f 4e 3e 0a 3c | 54 52 3e 3c 54 44 3e 3c |PTION>.<|TR><TD><|
|00001d80| 49 4d 47 0a 20 53 54 59 | 4c 45 3d 22 68 65 69 67 |IMG. STY|LE="heig|
|00001d90| 68 74 3a 20 32 38 36 2e | 37 36 65 78 3b 20 22 20 |ht: 286.|76ex; " |
|00001da0| 53 52 43 3d 22 69 6d 67 | 34 2e 70 6e 67 22 0a 20 |SRC="img|4.png". |
|00001db0| 41 4c 54 3d 22 5c 62 65 | 67 69 6e 7b 66 69 67 75 |ALT="\be|gin{figu|
|00001dc0| 72 65 7d 5c 62 65 67 69 | 6e 7b 63 65 6e 74 65 72 |re}\begi|n{center|
|00001dd0| 7d 0a 5c 75 6e 69 74 6c | 65 6e 67 74 68 3d 30 2e |}.\unitl|ength=0.|
|00001de0| 37 30 6d 6d 5c 6c 69 6e | 65 74 68 69 63 6b 6e 65 |70mm\lin|ethickne|
|00001df0| 73 73 7b 30 2e 34 70 74 | 7d 0a 5c 62 65 67 69 6e |ss{0.4pt|}.\begin|
|00001e00| 7b 70 2e 2e 2e 0a 2e 2e | 2e 30 30 7d 7d 0a 5c 70 |{p......|.00}}.\p|
|00001e10| 75 74 28 34 33 2e 30 30 | 2c 32 31 2e 30 30 29 7b |ut(43.00|,21.00){|
|00001e20| 5c 6c 69 6e 65 28 31 2c | 30 29 7b 31 30 2e 30 30 |\line(1,|0){10.00|
|00001e30| 7d 7d 0a 5c 65 6e 64 7b | 70 69 63 74 75 72 65 7d |}}.\end{|picture}|
|00001e40| 20 5c 65 6e 64 7b 63 65 | 6e 74 65 72 7d 5c 65 6e | \end{ce|nter}\en|
|00001e50| 64 7b 66 69 67 75 72 65 | 7d 22 3e 3c 2f 54 44 3e |d{figure|}"></TD>|
|00001e60| 3c 2f 54 52 3e 0a 3c 2f | 54 41 42 4c 45 3e 0a 3c |</TR>.</|TABLE>.<|
|00001e70| 2f 44 49 56 3e 0a 0a 3c | 50 3e 0a 0a 3c 48 52 3e |/DIV>..<|P>..<HR>|
|00001e80| 0a 0a 3c 2f 42 4f 44 59 | 3e 0a 3c 2f 48 54 4d 4c |..</BODY|>.</HTML|
|00001e90| 3e 0a | |>. | |
+--------+-------------------------+-------------------------+--------+--------+
