io Programmo 27

home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 27 / IOPROG_27.ISO / SOFT / GRAPH.ZIP / AI / DOC / SEARCH.TEX / node7_ct.html < prev next >
LaTeX Document | 1994-08-15 | 5.3 KB
open in:
MacOS 8.1 extracted |
Win98 extracted |
DOS extracted
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	Nim source code	default (weak)
`96%`	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 42 6c | 69 6e 64 20 73 65 61 72 |ts of Bl|ind sear|
|000000b0| 63 68 20 76 73 20 68 65 | 75 72 69 73 74 69 63 20 |ch vs he|uristic |
|000000c0| 73 65 61 72 63 68 2c 20 | 62 65 73 74 2d 66 69 72 |search, |best-fir|
|000000d0| 73 74 20 73 65 61 72 63 | 68 3c 2f 54 49 54 4c 45 |st searc|h</TITLE|
|000000e0| 3e 0a 0a 3c 4d 45 54 41 | 20 48 54 54 50 2d 45 51 |>..<META| HTTP-EQ|
|000000f0| 55 49 56 3d 22 43 6f 6e | 74 65 6e 74 2d 54 79 70 |UIV="Con|tent-Typ|
|00000100| 65 22 20 43 4f 4e 54 45 | 4e 54 3d 22 74 65 78 74 |e" CONTE|NT="text|
|00000110| 2f 68 74 6d 6c 3b 20 63 | 68 61 72 73 65 74 3d 75 |/html; c|harset=u|
|00000120| 74 66 2d 38 22 3e 0a 3c | 4d 45 54 41 20 4e 41 4d |tf-8">.<|META NAM|
|00000130| 45 3d 22 76 69 65 77 70 | 6f 72 74 22 20 43 4f 4e |E="viewp|ort" CON|
|00000140| 54 45 4e 54 3d 22 77 69 | 64 74 68 3d 64 65 76 69 |TENT="wi|dth=devi|
|00000150| 63 65 2d 77 69 64 74 68 | 2c 20 69 6e 69 74 69 61 |ce-width|, initia|
|00000160| 6c 2d 73 63 61 6c 65 3d | 31 2e 30 22 3e 0a 3c 4d |l-scale=|1.0">.<M|
|00000170| 45 54 41 20 4e 41 4d 45 | 3d 22 47 65 6e 65 72 61 |ETA NAME|="Genera|
|00000180| 74 6f 72 22 20 43 4f 4e | 54 45 4e 54 3d 22 4c 61 |tor" CON|TENT="La|
|00000190| 54 65 58 32 48 54 4d 4c | 20 76 32 30 32 32 22 3e |TeX2HTML| v2022">|
|000001a0| 0a 0a 3c 4c 49 4e 4b 20 | 52 45 4c 3d 22 53 54 59 |..<LINK |REL="STY|
|000001b0| 4c 45 53 48 45 45 54 22 | 20 48 52 45 46 3d 22 53 |LESHEET"| HREF="S|
|000001c0| 45 41 52 43 48 2e 63 73 | 73 22 3e 0a 0a 3c 4c 49 |EARCH.cs|s">..<LI|
|000001d0| 4e 4b 20 52 45 4c 3d 22 | 70 72 65 76 69 6f 75 73 |NK REL="|previous|
|000001e0| 22 20 48 52 45 46 3d 22 | 6e 6f 64 65 36 5f 6d 6e |" HREF="|node6_mn|
|000001f0| 2e 68 74 6d 6c 22 3e 0a | 3c 4c 49 4e 4b 20 52 45 |.html">.|<LINK RE|
|00000200| 4c 3d 22 75 70 22 20 48 | 52 45 46 3d 22 6e 6f 64 |L="up" H|REF="nod|
|00000210| 65 32 5f 6d 6e 2e 68 74 | 6d 6c 22 3e 0a 3c 4c 49 |e2_mn.ht|ml">.<LI|
|00000220| 4e 4b 20 52 45 4c 3d 22 | 6e 65 78 74 22 20 48 52 |NK REL="|next" HR|
|00000230| 45 46 3d 22 6e 6f 64 65 | 38 5f 6d 6e 2e 68 74 6d |EF="node|8_mn.htm|
|00000240| 6c 22 3e 0a 3c 2f 48 45 | 41 44 3e 0a 20 0a 3c 42 |l">.</HE|AD>. .<B|
|00000250| 4f 44 59 20 62 67 63 6f | 6c 6f 72 3d 22 23 66 66 |ODY bgco|lor="#ff|
|00000260| 66 66 66 66 22 20 74 65 | 78 74 3d 22 23 30 30 30 |ffff" te|xt="#000|
|00000270| 30 30 30 22 20 6c 69 6e | 6b 3d 22 23 39 39 34 34 |000" lin|k="#9944|
|00000280| 45 45 22 20 76 6c 69 6e | 6b 3d 22 23 30 30 30 30 |EE" vlin|k="#0000|
|00000290| 66 66 22 20 61 6c 69 6e | 6b 3d 22 23 30 30 66 66 |ff" alin|k="#00ff|
|000002a0| 30 30 22 3e 0a 0a 3c 48 | 32 3e 3c 41 20 49 44 3d |00">..<H|2><A ID=|
|000002b0| 22 53 45 43 54 49 4f 4e | 30 30 30 32 35 30 30 30 |"SECTION|00025000|
|000002c0| 30 30 30 30 30 30 30 30 | 30 30 30 30 22 3e 0a 42 |00000000|0000">.B|
|000002d0| 6c 69 6e 64 20 73 65 61 | 72 63 68 20 76 73 20 68 |lind sea|rch vs h|
|000002e0| 65 75 72 69 73 74 69 63 | 20 73 65 61 72 63 68 2c |euristic| search,|
|000002f0| 20 62 65 73 74 2d 66 69 | 72 73 74 20 73 65 61 72 | best-fi|rst sear|
|00000300| 63 68 3c 2f 41 3e 0a 3c | 2f 48 32 3e 0a 0a 3c 50 |ch</A>.<|/H2>..<P|
|00000310| 3e 0a 41 6c 6c 20 6f 66 | 20 74 68 65 20 6d 65 74 |>.All of| the met|
|00000320| 68 6f 64 73 20 64 65 73 | 63 72 69 62 65 64 20 73 |hods des|cribed s|
|00000330| 6f 20 66 61 72 20 61 72 | 65 20 63 61 6c 6c 65 64 |o far ar|e called|
|00000340| 20 3c 45 4d 3e 62 6c 69 | 6e 64 2d 73 65 61 72 63 | <EM>bli|nd-searc|
|00000350| 68 20 70 72 6f 63 65 64 | 75 72 65 73 26 6e 62 73 |h proced|ures&nbs|
|00000360| 70 3b 3c 2f 45 4d 3e 20 | 62 65 63 61 75 73 65 20 |p;</EM> |because |
|00000370| 74 68 65 79 0a 64 6f 20 | 6e 6f 74 20 75 73 65 20 |they.do |not use |
|00000380| 61 6e 79 20 73 70 65 63 | 69 66 69 63 20 69 6e 66 |any spec|ific inf|
|00000390| 6f 72 6d 61 74 69 6f 6e | 20 61 62 6f 75 74 20 74 |ormation| about t|
|000003a0| 68 65 20 70 72 6f 62 6c | 65 6d 20 74 6f 20 62 65 |he probl|em to be|
|000003b0| 20 73 6f 6c 76 65 64 2c | 20 69 2e 65 2c 20 74 68 | solved,| i.e, th|
|000003c0| 65 0a 73 65 61 72 63 68 | 20 70 72 6f 63 65 73 73 |e.search| process|
|000003d0| 20 6a 75 73 74 20 63 6f | 6e 74 69 6e 75 65 73 20 | just co|ntinues |
|000003e0| 75 6e 74 69 6c 20 69 74 | 20 68 61 70 70 65 6e 73 |until it| happens|
|000003f0| 20 6f 6e 20 61 20 73 6f | 6c 75 74 69 6f 6e 3a 20 | on a so|lution: |
|00000400| 69 74 20 69 73 20 6e 6f | 74 0a 64 69 72 65 63 74 |it is no|t.direct|
|00000410| 65 64 20 69 6e 20 73 6f | 6d 65 20 77 61 79 20 74 |ed in so|me way t|
|00000420| 6f 20 74 68 65 20 67 6f | 61 6c 2e 20 54 68 65 20 |o the go|al. The |
|00000430| 61 64 76 61 6e 74 61 67 | 65 20 6f 66 20 62 6c 69 |advantag|e of bli|
|00000440| 6e 64 2d 73 65 61 72 63 | 68 20 70 72 6f 63 65 64 |nd-searc|h proced|
|00000450| 75 72 65 73 20 69 73 0a | 74 68 61 74 20 74 68 65 |ures is.|that the|
|00000460| 79 20 61 72 65 20 65 61 | 73 79 20 74 6f 20 69 6d |y are ea|sy to im|
|00000470| 70 6c 65 6d 65 6e 74 20 | 61 6e 64 20 6d 61 79 20 |plement |and may |
|00000480| 66 69 6e 64 20 61 20 73 | 6f 6c 75 74 69 6f 6e 20 |find a s|olution |
|00000490| 71 75 69 63 6b 6c 79 20 | 66 6f 72 20 73 6d 61 6c |quickly |for smal|
|000004a0| 6c 0a 70 72 6f 62 6c 65 | 6d 73 2e 20 54 68 65 20 |l.proble|ms. The |
|000004b0| 6f 62 76 69 6f 75 73 20 | 64 69 73 61 64 76 61 6e |obvious |disadvan|
|000004c0| 74 61 67 65 20 6f 66 20 | 74 68 65 73 65 20 6d 65 |tage of |these me|
|000004d0| 74 68 6f 64 73 20 69 73 | 20 74 68 61 74 20 74 68 |thods is| that th|
|000004e0| 65 79 20 6d 61 79 20 62 | 65 20 6c 65 64 0a 61 73 |ey may b|e led.as|
|000004f0| 74 72 61 79 2c 20 65 78 | 70 61 6e 64 69 6e 67 20 |tray, ex|panding |
|00000500| 61 20 6c 6f 74 20 6f 66 | 20 6e 6f 64 65 73 20 74 |a lot of| nodes t|
|00000510| 68 61 74 20 61 72 65 20 | 6e 6f 74 20 70 61 72 74 |hat are |not part|
|00000520| 20 6f 66 20 74 68 65 20 | 73 6f 6c 75 74 69 6f 6e | of the |solution|
|00000530| 20 70 61 74 68 2e 20 46 | 6f 72 0a 65 78 61 6d 70 | path. F|or.examp|
|00000540| 6c 65 2c 20 77 68 65 6e | 20 74 72 61 76 65 72 73 |le, when| travers|
|00000550| 69 6e 67 20 61 20 74 72 | 65 65 20 69 6e 20 64 65 |ing a tr|ee in de|
|00000560| 70 74 68 2d 66 69 72 73 | 74 20 6f 72 64 65 72 20 |pth-firs|t order |
|00000570| 77 65 20 64 69 76 65 20 | 69 6e 74 6f 20 74 68 65 |we dive |into the|
|00000580| 0a 6c 65 66 74 20 6d 6f | 73 74 20 62 72 61 6e 63 |.left mo|st branc|
|00000590| 68 2c 20 74 68 69 73 20 | 69 73 20 66 69 6e 65 20 |h, this |is fine |
|000005a0| 69 66 20 77 65 20 68 61 | 70 70 65 6e 20 74 6f 20 |if we ha|ppen to |
|000005b0| 66 69 6e 64 20 61 20 73 | 6f 6c 75 74 69 6f 6e 20 |find a s|olution |
|000005c0| 74 68 65 72 65 2e 20 42 | 75 74 20 73 75 70 70 6f |there. B|ut suppo|
|000005d0| 73 65 0a 74 68 65 20 67 | 6f 61 6c 20 6e 6f 64 65 |se.the g|oal node|
|000005e0| 20 69 73 20 6c 6f 63 61 | 74 65 64 20 69 6e 20 61 | is loca|ted in a|
|000005f0| 20 64 69 66 66 65 72 65 | 6e 74 20 70 61 72 74 20 | differe|nt part |
|00000600| 6f 66 20 74 68 65 20 74 | 72 65 65 2c 20 65 2e 67 |of the t|ree, e.g|
|00000610| 2e 2c 20 61 74 20 74 68 | 65 20 72 69 67 68 74 20 |., at th|e right |
|00000620| 6d 6f 73 74 0a 62 72 61 | 6e 63 68 2e 20 49 6e 20 |most.bra|nch. In |
|00000630| 74 68 69 73 20 63 61 73 | 65 20 77 65 20 77 69 6c |this cas|e we wil|
|00000640| 6c 20 68 61 76 65 20 73 | 65 61 72 63 68 65 64 20 |l have s|earched |
|00000650| 74 68 65 20 65 6e 74 69 | 72 65 20 74 72 65 65 20 |the enti|re tree |
|00000660| 62 65 66 6f 72 65 20 67 | 65 74 74 69 6e 67 0a 6f |before g|etting.o|
|00000670| 6e 20 74 68 65 20 72 69 | 67 68 74 20 74 72 61 63 |n the ri|ght trac|
|00000680| 6b 2e 20 49 74 20 77 6f | 75 6c 64 20 68 61 76 65 |k. It wo|uld have|
|00000690| 20 62 65 65 6e 20 6d 75 | 63 68 20 62 65 74 74 65 | been mu|ch bette|
|000006a0| 72 20 69 66 20 77 65 20 | 68 61 64 20 6b 6e 6f 77 |r if we |had know|
|000006b0| 6e 20 69 6e 20 61 64 76 | 61 6e 63 65 0a 77 68 69 |n in adv|ance.whi|
|000006c0| 63 68 20 77 61 79 20 74 | 6f 20 67 6f 2e 20 42 75 |ch way t|o go. Bu|
|000006d0| 74 20 6f 66 20 63 6f 75 | 72 73 65 2c 20 74 68 69 |t of cou|rse, thi|
|000006e0| 73 20 69 73 20 69 6d 70 | 6f 73 73 69 62 6c 65 3b |s is imp|ossible;|
|000006f0| 20 69 66 20 77 65 20 68 | 61 64 20 6b 6e 6f 77 6e | if we h|ad known|
|00000700| 20 74 68 69 73 0a 77 65 | 20 77 6f 75 6c 64 20 6e | this.we| would n|
|00000710| 65 76 65 72 20 68 61 76 | 65 20 74 6f 20 3c 45 4d |ever hav|e to <EM|
|00000720| 3e 73 65 61 72 63 68 26 | 6e 62 73 70 3b 3c 2f 45 |>search&|nbsp;</E|
|00000730| 4d 3e 20 66 6f 72 20 61 | 20 73 6f 6c 75 74 69 6f |M> for a| solutio|
|00000740| 6e 2e 20 53 74 69 6c 6c | 2c 20 74 68 65 72 65 20 |n. Still|, there |
|00000750| 6d 61 79 20 62 65 0a 73 | 69 74 75 61 74 69 6f 6e |may be.s|ituation|
|00000760| 73 20 77 68 65 72 65 20 | 77 65 20 64 6f 20 6e 6f |s where |we do no|
|00000770| 74 20 6b 6e 6f 77 20 65 | 78 61 63 74 6c 79 20 77 |t know e|xactly w|
|00000780| 68 65 72 65 20 74 6f 20 | 67 6f 2c 20 62 75 74 20 |here to |go, but |
|00000790| 63 61 6e 20 67 69 76 65 | 20 61 6e 20 65 73 74 69 |can give| an esti|
|000007a0| 6d 61 74 65 0a 6f 66 20 | 68 6f 77 20 66 61 72 20 |mate.of |how far |
|000007b0| 61 20 6e 6f 64 65 20 69 | 73 20 72 65 6d 6f 76 65 |a node i|s remove|
|000007c0| 64 20 66 72 6f 6d 20 74 | 68 65 20 67 6f 61 6c 20 |d from t|he goal |
|000007d0| 6e 6f 64 65 20 61 6e 64 | 20 68 65 6e 63 65 20 64 |node and| hence d|
|000007e0| 65 74 65 72 6d 69 6e 65 | 20 69 66 20 69 74 20 69 |etermine| if it i|
|000007f0| 73 20 6f 6e 0a 74 68 65 | 20 28 62 65 73 74 29 20 |s on.the| (best) |
|00000800| 73 6f 6c 75 74 69 6f 6e | 20 70 61 74 68 2e 20 55 |solution| path. U|
|00000810| 73 69 6e 67 20 74 68 69 | 73 20 69 6e 66 6f 72 6d |sing thi|s inform|
|00000820| 61 74 69 6f 6e 20 69 74 | 20 69 73 20 70 6f 73 73 |ation it| is poss|
|00000830| 69 62 6c 65 20 74 6f 20 | 69 6d 70 72 6f 76 65 20 |ible to |improve |
|00000840| 74 68 65 0a 65 66 66 69 | 63 69 65 6e 63 79 20 6f |the.effi|ciency o|
|00000850| 66 20 74 68 65 20 73 65 | 61 72 63 68 20 70 72 6f |f the se|arch pro|
|00000860| 63 65 73 73 2e 20 48 65 | 72 65 2c 20 77 65 20 68 |cess. He|re, we h|
|00000870| 61 76 65 20 69 6e 74 72 | 6f 64 75 63 65 64 20 74 |ave intr|oduced t|
|00000880| 68 65 20 69 64 65 61 20 | 6f 66 20 75 73 69 6e 67 |he idea |of using|
|00000890| 20 61 0a 3c 45 4d 3e 68 | 65 75 72 69 73 74 69 63 | a.<EM>h|euristic|
|000008a0| 26 6e 62 73 70 3b 3c 2f | 45 4d 3e 2e 0a 0a 3c 50 |&nbsp;</|EM>...<P|
|000008b0| 3e 0a 41 20 68 65 75 72 | 69 73 74 69 63 20 69 73 |>.A heur|istic is|
|000008c0| 20 61 20 72 75 6c 65 20 | 6f 66 20 74 68 75 6d 62 | a rule |of thumb|
|000008d0| 2c 20 61 20 74 65 63 68 | 6e 69 71 75 65 20 74 68 |, a tech|nique th|
|000008e0| 61 74 20 69 6d 70 72 6f | 76 65 73 20 74 68 65 20 |at impro|ves the |
|000008f0| 65 66 66 69 63 69 65 6e | 63 79 20 6f 66 20 61 0a |efficien|cy of a.|
|00000900| 73 65 61 72 63 68 20 70 | 72 6f 63 65 73 73 2c 20 |search p|rocess, |
|00000910| 70 6f 73 73 69 62 6c 79 | 20 62 79 20 73 61 63 72 |possibly| by sacr|
|00000920| 69 66 69 63 69 6e 67 20 | 63 6c 61 69 6d 73 20 74 |ificing |claims t|
|00000930| 6f 20 63 6f 6d 70 6c 65 | 74 65 6e 65 73 73 0a 5b |o comple|teness.[|
|00000940| 52 69 63 68 20 31 39 38 | 33 2c 20 33 35 5d 2e 20 |Rich 198|3, 35]. |
|00000950| 54 68 69 73 20 6d 65 61 | 6e 73 20 74 68 61 74 2c |This mea|ns that,|
|00000960| 20 6c 69 6b 65 20 61 6c | 6c 20 72 75 6c 65 73 20 | like al|l rules |
|00000970| 6f 66 20 74 68 75 6d 62 | 2c 20 68 65 75 72 69 73 |of thumb|, heuris|
|00000980| 74 69 63 73 20 6d 61 79 | 20 6c 65 61 64 0a 74 68 |tics may| lead.th|
|00000990| 65 20 73 65 61 72 63 68 | 20 69 6e 20 74 68 65 20 |e search| in the |
|000009a0| 6d 6f 73 74 20 70 72 6f | 6d 69 73 69 6e 67 20 77 |most pro|mising w|
|000009b0| 61 79 2c 20 66 69 6e 64 | 69 6e 67 20 61 20 73 6f |ay, find|ing a so|
|000009c0| 6c 75 74 69 6f 6e 20 71 | 75 69 63 6b 6c 79 2c 20 |lution q|uickly, |
|000009d0| 62 75 74 20 61 6c 73 6f | 0a 74 68 61 74 20 74 68 |but also|.that th|
|000009e0| 65 79 20 6d 61 79 20 74 | 61 6b 65 20 61 20 77 72 |ey may t|ake a wr|
|000009f0| 6f 6e 67 20 74 75 72 6e | 20 28 62 75 74 20 73 74 |ong turn| (but st|
|00000a00| 69 6c 6c 20 6c 65 61 64 | 69 6e 67 20 74 6f 20 74 |ill lead|ing to t|
|00000a10| 68 65 20 67 6f 61 6c 29 | 20 6f 72 20 6c 65 61 64 |he goal)| or lead|
|00000a20| 20 74 6f 0a 64 65 61 64 | 65 6e 64 73 2e 20 41 20 | to.dead|ends. A |
|00000a30| 67 6f 6f 64 20 77 61 79 | 20 74 6f 20 75 73 65 20 |good way| to use |
|00000a40| 68 65 75 72 69 73 74 69 | 63 20 69 6e 66 6f 72 6d |heuristi|c inform|
|00000a50| 61 74 69 6f 6e 20 69 73 | 20 62 79 20 6d 65 61 6e |ation is| by mean|
|00000a60| 73 20 6f 66 20 61 20 3c | 45 4d 3e 68 65 75 72 69 |s of a <|EM>heuri|
|00000a70| 73 74 69 63 0a 66 75 6e | 63 74 69 6f 6e 26 6e 62 |stic.fun|ction&nb|
|00000a80| 73 70 3b 3c 2f 45 4d 3e | 20 74 68 61 74 20 65 76 |sp;</EM>| that ev|
|00000a90| 61 6c 75 61 74 65 73 20 | 65 76 65 72 79 20 6e 6f |aluates |every no|
|00000aa0| 64 65 20 74 68 61 74 20 | 69 73 20 62 65 69 6e 67 |de that |is being|
|00000ab0| 20 67 65 6e 65 72 61 74 | 65 64 2c 20 69 2e 65 2e | generat|ed, i.e.|
|00000ac0| 20 74 68 61 74 20 64 65 | 74 65 72 6d 69 6e 65 73 | that de|termines|
|00000ad0| 0a 74 68 65 20 67 6f 6f | 64 6e 65 73 73 20 6f 72 |.the goo|dness or|
|00000ae0| 20 62 61 64 6e 65 73 73 | 20 6f 66 20 61 20 6e 6f | badness| of a no|
|00000af0| 64 65 2e 20 55 73 69 6e | 67 20 61 20 68 65 75 72 |de. Usin|g a heur|
|00000b00| 69 73 74 69 63 20 66 75 | 6e 63 74 69 6f 6e 20 69 |istic fu|nction i|
|00000b10| 74 20 77 69 6c 6c 20 62 | 65 0a 70 6f 73 73 69 62 |t will b|e.possib|
|00000b20| 6c 65 20 74 6f 20 63 6f | 6e 64 75 63 74 20 74 68 |le to co|nduct th|
|00000b30| 65 20 73 65 61 72 63 68 | 20 69 6e 20 74 68 65 20 |e search| in the |
|00000b40| 6d 6f 73 74 20 70 72 6f | 66 69 74 61 62 6c 65 20 |most pro|fitable |
|00000b50| 64 69 72 65 63 74 69 6f | 6e 2c 20 62 79 20 73 75 |directio|n, by su|
|00000b60| 67 67 65 73 74 69 6e 67 | 0a 77 68 69 63 68 20 70 |ggesting|.which p|
|00000b70| 61 74 68 20 74 6f 20 66 | 6f 6c 6c 6f 77 20 66 69 |ath to f|ollow fi|
|00000b80| 72 73 74 20 77 68 65 6e | 20 6d 6f 72 65 20 74 68 |rst when| more th|
|00000b90| 61 6e 20 6f 6e 65 20 69 | 73 20 61 76 61 69 6c 61 |an one i|s availa|
|00000ba0| 62 6c 65 2e 0a 0a 3c 50 | 3e 0a 57 65 20 77 69 6c |ble...<P|>.We wil|
|00000bb0| 6c 20 64 65 66 69 6e 65 | 20 61 20 68 65 75 72 69 |l define| a heuri|
|00000bc0| 73 74 69 63 20 66 75 6e | 63 74 69 6f 6e 20 3c 45 |stic fun|ction <E|
|00000bd0| 4d 3e 66 28 6e 29 26 6e | 62 73 70 3b 3c 2f 45 4d |M>f(n)&n|bsp;</EM|
|00000be0| 3e 3c 41 20 49 44 3d 22 | 66 66 75 6e 63 22 3e 3c |><A ID="|ffunc"><|
|00000bf0| 2f 41 3e 20 62 65 69 6e | 67 20 74 68 65 20 73 75 |/A> bein|g the su|
|00000c00| 6d 20 6f 66 20 74 77 6f | 20 63 6f 6d 70 6f 6e 65 |m of two| compone|
|00000c10| 6e 74 73 0a 3c 45 4d 3e | 67 28 6e 29 26 6e 62 73 |nts.<EM>|g(n)&nbs|
|00000c20| 70 3b 3c 2f 45 4d 3e 20 | 61 6e 64 20 3c 45 4d 3e |p;</EM> |and <EM>|
|00000c30| 68 28 6e 29 26 6e 62 73 | 70 3b 3c 2f 45 4d 3e 3a |h(n)&nbs|p;</EM>:|
|00000c40| 0a 20 20 20 20 3c 50 3e | 3c 21 2d 2d 20 4d 41 54 |.    <P>|<!-- MAT|
|00000c50| 48 0a 20 5c 62 65 67 69 | 6e 7b 64 69 73 70 6c 61 |H. \begi|n{displa|
|00000c60| 79 6d 61 74 68 7d 0a 66 | 28 6e 29 20 3d 20 67 28 |ymath}.f|(n) = g(|
|00000c70| 6e 29 20 2b 20 68 28 6e | 29 0a 5c 65 6e 64 7b 64 |n) + h(n|).\end{d|
|00000c80| 69 73 70 6c 61 79 6d 61 | 74 68 7d 0a 20 2d 2d 3e |isplayma|th}. -->|
|00000c90| 0a 3c 2f 50 3e 0a 3c 44 | 49 56 20 41 4c 49 47 4e |.</P>.<D|IV ALIGN|
|00000ca0| 3d 22 43 45 4e 54 45 52 | 22 3e 0a 3c 49 3e 66 3c |="CENTER|">.<I>f<|
|00000cb0| 2f 49 3e 20 28 3c 49 3e | 6e 3c 2f 49 3e 29 20 3d |/I> (<I>|n</I>) =|
|00000cc0| 20 3c 49 3e 67 3c 2f 49 | 3e 28 3c 49 3e 6e 3c 2f | <I>g</I|>(<I>n</|
|00000cd0| 49 3e 29 20 2b 20 3c 49 | 3e 68 3c 2f 49 3e 28 3c |I>) + <I|>h</I>(<|
|00000ce0| 49 3e 6e 3c 2f 49 3e 29 | 0a 3c 2f 44 49 56 3e 3c |I>n</I>)|.</DIV><|
|00000cf0| 50 3e 3c 2f 50 3e 0a 46 | 75 6e 63 74 69 6f 6e 20 |P></P>.F|unction |
|00000d00| 67 28 6e 29 20 69 73 20 | 74 68 65 20 73 61 6d 65 |g(n) is |the same|
|00000d10| 20 61 73 20 74 68 65 20 | 6f 6e 65 20 64 65 73 63 | as the |one desc|
|00000d20| 72 69 62 65 64 20 69 6e | 20 73 65 63 74 69 6f 6e |ribed in| section|
|00000d30| 26 6e 62 73 70 3b 3c 41 | 20 48 52 45 46 3d 22 6e |&nbsp;<A| HREF="n|
|00000d40| 6f 64 65 36 5f 63 74 2e | 68 74 6d 6c 23 67 66 75 |ode6_ct.|html#gfu|
|00000d50| 6e 63 22 3e 3c 49 4d 47 | 20 20 41 4c 54 3d 22 5b |nc"><IMG|  ALT="[|
|00000d60| 2a 5d 22 20 53 52 43 3d | 22 63 72 6f 73 73 72 65 |*]" SRC=|"crossre|
|00000d70| 66 2e 70 6e 67 22 3e 3c | 2f 41 3e 3a 20 61 20 6d |f.png"><|/A>: a m|
|00000d80| 65 61 73 75 72 65 20 6f | 66 20 74 68 65 20 63 6f |easure o|f the co|
|00000d90| 73 74 0a 6f 66 20 67 65 | 74 74 69 6e 67 20 66 72 |st.of ge|tting fr|
|00000da0| 6f 6d 20 74 68 65 20 69 | 6e 69 74 69 61 6c 20 73 |om the i|nitial s|
|00000db0| 74 61 74 65 20 74 6f 20 | 74 68 65 20 63 75 72 72 |tate to |the curr|
|00000dc0| 65 6e 74 20 6e 6f 64 65 | 2e 20 54 68 65 20 66 75 |ent node|. The fu|
|00000dd0| 6e 63 74 69 6f 6e 20 68 | 28 6e 29 20 69 73 20 61 |nction h|(n) is a|
|00000de0| 6e 0a 65 73 74 69 6d 61 | 74 65 20 6f 66 20 74 68 |n.estima|te of th|
|00000df0| 65 20 61 64 64 69 74 69 | 6f 6e 61 6c 20 63 6f 73 |e additi|onal cos|
|00000e00| 74 20 6f 66 20 67 65 74 | 74 69 6e 67 20 66 72 6f |t of get|ting fro|
|00000e10| 6d 20 74 68 65 20 63 75 | 72 72 65 6e 74 20 6e 6f |m the cu|rrent no|
|00000e20| 64 65 20 74 6f 20 61 20 | 67 6f 61 6c 0a 73 74 61 |de to a |goal.sta|
|00000e30| 74 65 2e 20 50 75 74 20 | 64 69 66 66 65 72 65 6e |te. Put |differen|
|00000e40| 74 6c 79 2c 20 68 28 6e | 29 20 69 73 20 74 68 65 |tly, h(n|) is the|
|00000e50| 20 66 75 6e 63 74 69 6f | 6e 20 69 6e 20 77 68 69 | functio|n in whi|
|00000e60| 63 68 20 74 68 65 20 72 | 65 61 6c 20 68 65 75 72 |ch the r|eal heur|
|00000e70| 69 73 74 69 63 0a 6b 6e | 6f 77 6c 65 64 67 65 20 |istic.kn|owledge |
|00000e80| 69 73 20 69 6d 62 65 64 | 64 65 64 2e 20 55 73 69 |is imbed|ded. Usi|
|00000e90| 6e 67 20 66 28 6e 29 20 | 77 65 20 61 72 65 20 61 |ng f(n) |we are a|
|00000ea0| 62 6c 65 20 74 6f 20 6f | 72 64 65 72 20 74 68 65 |ble to o|rder the|
|00000eb0| 20 73 65 74 20 6f 66 20 | 6e 6f 64 65 73 20 77 61 | set of |nodes wa|
|00000ec0| 69 74 69 6e 67 0a 66 6f | 72 20 65 78 70 61 6e 73 |iting.fo|r expans|
|00000ed0| 69 6f 6e 2c 20 62 79 20 | 63 6f 6e 76 65 6e 74 69 |ion, by |conventi|
|00000ee0| 6f 6e 20 74 68 69 73 20 | 77 69 6c 6c 20 62 65 20 |on this |will be |
|00000ef0| 64 6f 6e 65 20 74 68 69 | 73 20 69 6e 20 3c 45 4d |done thi|s in <EM|
|00000f00| 3e 69 6e 63 72 65 61 73 | 69 6e 67 26 6e 62 73 70 |>increas|ing&nbsp|
|00000f10| 3b 3c 2f 45 4d 3e 20 6f | 72 64 65 72 2e 0a 41 6e |;</EM> o|rder..An|
|00000f20| 20 61 6c 67 6f 72 69 74 | 68 6d 20 63 61 6e 20 74 | algorit|hm can t|
|00000f30| 68 65 6e 20 62 65 20 75 | 73 65 64 20 74 6f 20 73 |hen be u|sed to s|
|00000f40| 65 6c 65 63 74 20 74 68 | 65 20 6e 6f 64 65 20 68 |elect th|e node h|
|00000f50| 61 76 69 6e 67 20 74 68 | 65 20 73 6d 61 6c 6c 65 |aving th|e smalle|
|00000f60| 73 74 20 66 28 6e 29 20 | 76 61 6c 75 65 0a 6e 65 |st f(n) |value.ne|
|00000f70| 78 74 20 66 6f 72 20 65 | 78 70 61 6e 73 69 6f 6e |xt for e|xpansion|
|00000f80| 2e 20 4f 6e 65 20 6f 66 | 20 74 68 65 20 6d 65 74 |. One of| the met|
|00000f90| 68 6f 64 73 20 74 68 61 | 74 20 75 73 65 73 20 74 |hods tha|t uses t|
|00000fa0| 68 69 73 20 74 65 63 68 | 6e 69 71 75 65 20 69 73 |his tech|nique is|
|00000fb0| 20 74 68 65 0a 3c 45 4d | 3e 62 65 73 74 2d 66 69 | the.<EM|>best-fi|
|00000fc0| 72 73 74 20 73 65 61 72 | 63 68 20 6d 65 74 68 6f |rst sear|ch metho|
|00000fd0| 64 26 6e 62 73 70 3b 3c | 2f 45 4d 3e 20 6f 72 20 |d&nbsp;<|/EM> or |
|00000fe0| 3c 45 4d 3e 3c 49 3e 41 | 3c 2f 49 3e 3c 53 55 50 |<EM><I>A|</I><SUP|
|00000ff0| 3e 2a 3c 2f 53 55 50 3e | 20 61 6c 67 6f 72 69 74 |>*</SUP>| algorit|
|00001000| 68 6d 26 6e 62 73 70 3b | 3c 2f 45 4d 3e 2e 0a 0a |hm&nbsp;|</EM>...|
|00001010| 3c 50 3e 0a 49 74 20 69 | 73 20 69 6d 70 6f 72 74 |<P>.It i|s import|
|00001020| 61 6e 74 20 74 6f 20 6b | 65 65 70 20 69 6e 20 6d |ant to k|eep in m|
|00001030| 69 6e 64 20 74 68 61 74 | 20 6d 6f 73 74 20 68 65 |ind that| most he|
|00001040| 75 72 69 73 74 69 63 73 | 20 61 72 65 20 69 6d 70 |uristics| are imp|
|00001050| 65 72 66 65 63 74 20 61 | 6e 64 20 74 68 61 74 2c |erfect a|nd that,|
|00001060| 0a 69 6e 65 76 69 74 61 | 62 6c 79 2c 20 74 68 65 |.inevita|bly, the|
|00001070| 20 73 65 61 72 63 68 20 | 70 72 6f 63 65 73 73 20 | search |process |
|00001080| 77 69 6c 6c 20 62 65 20 | 61 66 66 65 63 74 65 64 |will be |affected|
|00001090| 20 62 79 20 74 68 69 73 | 2e 20 49 6e 20 67 65 6e | by this|. In gen|
|000010a0| 65 72 61 6c 2c 20 61 20 | 73 65 61 72 63 68 0a 61 |eral, a |search.a|
|000010b0| 6c 67 6f 72 69 74 68 6d | 20 69 73 20 63 61 6c 6c |lgorithm| is call|
|000010c0| 65 64 20 3c 45 4d 3e 61 | 64 6d 69 73 73 69 62 6c |ed <EM>a|dmissibl|
|000010d0| 65 26 6e 62 73 70 3b 3c | 2f 45 4d 3e 20 69 66 20 |e&nbsp;<|/EM> if |
|000010e0| 66 6f 72 20 61 6e 79 20 | 67 72 61 70 68 20 69 74 |for any |graph it|
|000010f0| 20 74 65 72 6d 69 6e 61 | 74 65 73 20 69 6e 20 61 | termina|tes in a|
|00001100| 6e 0a 6f 70 74 69 6d 61 | 6c 20 70 61 74 68 20 74 |n.optima|l path t|
|00001110| 6f 20 61 20 67 6f 61 6c | 20 77 68 65 6e 65 76 65 |o a goal| wheneve|
|00001120| 72 20 61 20 70 61 74 68 | 20 65 78 69 73 74 73 2e |r a path| exists.|
|00001130| 20 55 73 69 6e 67 20 61 | 20 68 65 75 72 69 73 74 | Using a| heurist|
|00001140| 69 63 20 66 75 6e 63 74 | 69 6f 6e 0a 74 6f 20 63 |ic funct|ion.to c|
|00001150| 6f 6e 64 75 63 74 20 74 | 68 65 20 73 65 61 72 63 |onduct t|he searc|
|00001160| 68 20 70 72 6f 63 65 73 | 73 20 77 65 20 63 61 6e |h proces|s we can|
|00001170| 6e 6f 74 20 61 6c 77 61 | 79 73 20 6d 61 6b 65 20 |not alwa|ys make |
|00001180| 74 68 69 73 20 63 6c 61 | 69 6d 20 62 65 63 61 75 |this cla|im becau|
|00001190| 73 65 20 74 68 65 0a 62 | 65 68 61 76 69 6f 75 72 |se the.b|ehaviour|
|000011a0| 20 6f 66 20 74 68 65 20 | 73 65 61 72 63 68 20 77 | of the |search w|
|000011b0| 69 6c 6c 20 64 65 70 65 | 6e 64 20 6f 6e 20 68 6f |ill depe|nd on ho|
|000011c0| 77 20 61 63 63 75 72 61 | 74 65 6c 79 20 74 68 65 |w accura|tely the|
|000011d0| 20 66 75 6e 63 74 69 6f | 6e 20 65 76 61 6c 75 61 | functio|n evalua|
|000011e0| 74 65 73 0a 6e 6f 64 65 | 73 2e 20 49 66 20 77 65 |tes.node|s. If we|
|000011f0| 20 75 73 65 20 61 20 70 | 65 72 66 65 63 74 20 68 | use a p|erfect h|
|00001200| 65 75 72 69 73 74 69 63 | 20 66 75 6e 63 74 69 6f |euristic| functio|
|00001210| 6e 20 77 65 20 61 72 65 | 20 67 75 61 72 61 6e 74 |n we are| guarant|
|00001220| 65 65 64 20 74 6f 20 66 | 69 6e 64 20 61 6e 0a 6f |eed to f|ind an.o|
|00001230| 70 74 69 6d 61 6c 20 73 | 6f 6c 75 74 69 6f 6e 2c |ptimal s|olution,|
|00001240| 20 62 75 74 20 68 65 75 | 72 69 73 74 69 63 73 20 | but heu|ristics |
|00001250| 68 61 76 69 6e 67 20 74 | 68 69 73 20 70 72 6f 70 |having t|his prop|
|00001260| 65 72 74 79 20 61 72 65 | 20 68 61 72 64 20 74 6f |erty are| hard to|
|00001270| 20 66 69 6e 64 2e 0a 46 | 75 72 74 68 65 72 6d 6f | find..F|urthermo|
|00001280| 72 65 2c 20 74 68 65 20 | 64 69 66 66 69 63 75 6c |re, the |difficul|
|00001290| 74 79 20 6f 66 20 63 6f | 6d 70 75 74 69 6e 67 20 |ty of co|mputing |
|000012a0| 74 68 65 20 66 75 6e 63 | 74 69 6f 6e 27 73 20 72 |the func|tion's r|
|000012b0| 65 73 75 6c 74 20 61 66 | 66 65 63 74 73 20 74 68 |esult af|fects th|
|000012c0| 65 0a 74 6f 74 61 6c 20 | 63 6f 6d 70 75 74 61 74 |e.total |computat|
|000012d0| 69 6f 6e 61 6c 20 65 66 | 66 6f 72 74 20 6f 66 20 |ional ef|fort of |
|000012e0| 74 68 65 20 73 65 61 72 | 63 68 20 70 72 6f 63 65 |the sear|ch proce|
|000012f0| 73 73 2e 20 41 6c 73 6f | 2c 20 69 74 20 6d 61 79 |ss. Also|, it may|
|00001300| 20 62 65 20 6c 65 73 73 | 0a 69 6d 70 6f 72 74 61 | be less|.importa|
|00001310| 6e 74 20 74 6f 20 66 69 | 6e 64 20 61 20 73 6f 6c |nt to fi|nd a sol|
|00001320| 75 74 69 6f 6e 20 77 68 | 6f 73 65 20 63 6f 73 74 |ution wh|ose cost|
|00001330| 20 69 73 20 61 62 73 6f | 6c 75 74 65 6c 79 20 6d | is abso|lutely m|
|00001340| 69 6e 69 6d 61 6c 20 74 | 68 61 6e 20 74 6f 20 66 |inimal t|han to f|
|00001350| 69 6e 64 20 61 0a 73 6f | 6c 75 74 69 6f 6e 20 6f |ind a.so|lution o|
|00001360| 66 20 72 65 61 73 6f 6e | 61 62 6c 65 20 63 6f 73 |f reason|able cos|
|00001370| 74 20 77 69 74 68 69 6e | 20 61 20 72 65 61 73 6f |t within| a reaso|
|00001380| 6e 61 62 6c 65 20 61 6d | 6f 75 6e 74 20 6f 66 20 |nable am|ount of |
|00001390| 74 69 6d 65 2e 20 49 6e | 20 74 68 69 73 20 63 61 |time. In| this ca|
|000013a0| 73 65 0a 6f 6e 65 20 6d | 61 79 20 70 72 65 66 65 |se.one m|ay prefe|
|000013b0| 72 20 61 20 68 65 75 72 | 69 73 74 69 63 20 66 75 |r a heur|istic fu|
|000013c0| 6e 63 74 69 6f 6e 20 74 | 68 61 74 20 65 76 61 6c |nction t|hat eval|
|000013d0| 75 61 74 65 73 20 6e 6f | 64 65 73 20 6d 6f 72 65 |uates no|des more|
|000013e0| 20 61 63 63 75 72 61 74 | 65 6c 79 20 69 6e 0a 6d | accurat|ely in.m|
|000013f0| 6f 73 74 20 63 61 73 65 | 73 2c 20 62 75 74 20 73 |ost case|s, but s|
|00001400| 6f 6d 65 74 69 6d 65 73 | 20 6f 76 65 72 65 73 74 |ometimes| overest|
|00001410| 69 6d 61 74 65 73 20 74 | 68 65 20 64 69 73 74 61 |imates t|he dista|
|00001420| 6e 63 65 20 74 6f 20 74 | 68 65 20 67 6f 61 6c 2c |nce to t|he goal,|
|00001430| 20 74 68 75 73 20 72 65 | 73 75 6c 74 69 6e 67 0a | thus re|sulting.|
|00001440| 69 6e 20 61 6e 20 69 6e | 61 64 6d 69 73 73 69 62 |in an in|admissib|
|00001450| 6c 65 20 61 6c 67 6f 72 | 69 74 68 6d 2e 20 4d 6f |le algor|ithm. Mo|
|00001460| 73 74 20 6f 66 20 74 68 | 65 20 74 69 6d 65 20 77 |st of th|e time w|
|00001470| 65 20 6e 65 65 64 20 74 | 6f 20 6d 61 6b 65 20 74 |e need t|o make t|
|00001480| 68 69 73 20 73 6f 72 74 | 20 6f 66 0a 63 6f 6d 70 |his sort| of.comp|
|00001490| 72 6f 6d 69 73 65 3a 20 | 74 68 65 20 65 66 66 69 |romise: |the effi|
|000014a0| 63 69 65 6e 63 79 20 6f | 66 20 74 68 65 20 73 65 |ciency o|f the se|
|000014b0| 61 72 63 68 20 70 72 6f | 63 65 73 73 20 6e 65 65 |arch pro|cess nee|
|000014c0| 64 73 20 74 6f 20 62 65 | 20 69 6d 70 72 6f 76 65 |ds to be| improve|
|000014d0| 64 20 61 74 20 74 68 65 | 0a 73 61 63 72 69 66 69 |d at the|.sacrifi|
|000014e0| 63 65 20 6f 66 20 61 64 | 6d 69 73 73 69 62 69 6c |ce of ad|missibil|
|000014f0| 69 74 79 20 28 73 65 65 | 20 42 61 72 72 28 31 39 |ity (see| Barr(19|
|00001500| 38 31 29 2c 20 70 2e 36 | 35 2f 36 36 2c 20 4e 69 |81), p.6|5/66, Ni|
|00001510| 6c 73 73 6f 6e 28 31 39 | 37 31 29 2c 20 70 2e 35 |lsson(19|71), p.5|
|00001520| 39 66 66 2e 29 0a 0a 3c | 50 3e 0a 0a 3c 48 52 3e |9ff.)..<|P>..<HR>|
|00001530| 0a 0a 3c 2f 42 4f 44 59 | 3e 0a 3c 2f 48 54 4d 4c |..</BODY|>.</HTML|
|00001540| 3e 0a                   |                         |>.      |        |
+--------+-------------------------+-------------------------+--------+--------+