計算機科學(xué)基礎(chǔ) 18 Artificial Intelligence

18

Artificial

Intelligence

Objectives

Afterstudyingthischapter,thestudentshouldbeableto:

□Defineandgiveabriefhistoryofartificialintelligence.

□Describehowknowledgeisrepresentedinanintelligentagent.

□Showhowexpertsystemscanbeusedwhenahumanexpertisnotavailable.

□ShowhowanartiHcialagentcanbeusedtosimulatemundanetasks

performedbyhumanbeings.

□Showhowexpertsystemsandmundanesystemscanusedifferentsearch

techniquestosolveproblems.

□Showhowthelearningprocessinhumanscanbesimulated,tosomeextent,

usingneuralnetworksthatcreatetheelectronicversionofaneuroncalleda

perceptron.

18.2

18-1INTRODUCTION

Inthissectionwefirsttrytodefinethetermartificial

intelligence(AI)informallyandgiveabriefhistoryofit.

Wealsodefineanintelligentagentanditstwobroad

categories.Finally,wementiontwoprogramming

languagesthatarecommonlyusedinartificial

intelligence.

18.3

Whatisartificialintelligence?

Althoughthereisnouniversally-agreeddefinitionof

artificialintelligence,weacceptthefollowingdefinitionthat

matchesthetopicscoveredinthischapter:

Artificialintelligenceisthestudyofprogrammed

systemsthatcansimulate,tosomeextent,human

activitiessuchasperceiving,thinking,

learningandacting.

18.4

Abriefhistoryofartificialintelligence

Althoughartificialintelligenceasanindependentfieldof

studyisrelativelynew,ithassomerootsinthepast.Wecan

saythatitstarted2,400yearsagowhentheGreek

philosopherAristotleinventedtheconceptoflogical

reasoning.Theefforttofinalizethelanguageoflogic

continuedwithLeibnizandNewton.GeorgeBoole

developedBooleanalgebrainthenineteenthcentury

(AppendixE)thatlaidthefoundationofcomputercircuits.

However,themainideaofathinkingmachinecamefrom

AlanTuring,whoproposedtheTuringtest.Theterm

"artificialintelligence55wasfirstcoinedbyJohnMcCarthyin

1956.

18.5

TheTuringtest

In1950,AlanTuringproposedtheTuringtest,which

providesadefinitionofintelligenceinamachine.Thetest

simplycomparestheintelligentbehaviorofahumanbeing

withthatofacomputer.Aninterrogatorasksasetof

questionsthatareforwardedtobothacomputerandahuman

being.Theinterrogatorreceivestwosetsofresponses,but

doesnotknowwhichsetcomesfromthehumanandwhich

setfromthecomputer.Aftercarefulexaminationofthetwo

sets,iftheinterrogatorcannotdefinitelytellwhichsethas

comefromthecomputerandwhichfromthehuman,the

computerhaspassedtheTuringtestforintelligentbehavior.

18.6

Intelligentagents

Anintelligentagentisasystemthatperceivesits

environment,learnsfromit,andinteractswithit

intelligently.Intelligentagentscanbedividedintotwobroad

categories:softwareagentsandphysicalagents.

Softwareagents

Asoftwareagentisasetofprogramsthataredesignedtodo

particulartasks.Forexample,asoftwareagentcancheckthe

contentsofreceivede-mailsandclassifythemintodifferent

categories(junk,lessimportant,important,veryimportant

andsoon).Anotherexampleofasoftwareagentisasearch

engineusedtosearchtheWorldWideWebandfindsitesthat

canprovideinformationaboutarequestedsubject.

18.7

Physicalagents

Aphysicalagent(robot)isaprogrammablesystemthatcan

beusedtoperformavarietyoftasks.Simplerobotscanbe

usedinmanufacturingtodoroutinejobssuchasassembling,

welding,orpainting.Someorganizationsusemobilerobots

thatdoroutinedeliveryjobssuchasdistributingmailor

correspondencetodifferentrooms.Mobilerobotsareused

underwatertoprospectforoil.Ahumanoidrobotisan

autonomousmobilerobotthatissupposedtobehavelikea

human.

18.8

Programminglanguages

Althoughsomeall-purposelanguagessuchasC,C++and

Javaareusedtocreateintelligentsoftware,twolanguages

arespecificallydesignedforAI:LISPandPROLOG.

LISP

LISP(LIStProgramming)wasinventedbyJohnMcCarthy

in1958.Asthenameimplies,LISPisaprogramming

languagethatmanipulateslists.

PROLOG

PROLOG(PROgramminginLOGic)isalanguagethatcan

buildadatabaseoffactsandaknowledgebaseofrules.A

programinPROLOGcanuselogicalreasoningtoanswer

questionsthatcanbeinferredfromtheknowledgebase.

18.9

18-2KNOWLEDGEREPRESENTATION

Ifanartificialagentissupposedtosolvesomeproblems

relatedtotherealworld,itsomehowneedstobeableto

representknowledge.Factsarerepresentedasdata

structuresthatcanbemanipulatedbyprogramsstored

insidethecomputer.Inthissection,wedescribefour

commonmethodsforrepresentingknowledge:

semanticnetworks,frames,predicatelogicandrule-

basedsystems.

18.10

Semanticnetworks

Asemanticnetworkusesdirectedgraphstorepresent

knowledge.AdirectedgraphasdiscussedinChapter12is

madeofvertices(nodes)andedges(arcs).

Figure18.1Asimplesemanticnetwork

18.11

Concepts

Aconceptcanbethoughtofasasetorasubset.For

example,animaldefinesthesetofallanimals,horsedefines

thesetofallhorsesandisasubsetofthesetanimal.

Relations

Inasemanticnetwork,relationsareshownbyedges.An

edgecandefineasubclassrelation,aninstancerelation

attribute,anobject(color,size,...),orapropertyofan

object.

18.12

Frames

Framesarecloselyrelatedtosemanticnetworks.Inframes,

datastructures(records)areusedtorepresentthesame

knowledge.Oneadvantageofframesoversemantic

networksisthatprogramscanhandleframesmoreeasily

thansemanticnetworks.

Figure18.2AsetofframesrepresentingthesemanticnetworkinFigure18.1

18.13

Objects

Anodeinasemanticnetworkbecomesanobjectinasetof

frames,soanobjectcandefineaclass,asubclassoran

instanceofaclass.InFigure18.2,reptile,mammal,dog,

RoxyandRingoareobjects.

Slots

Edgesinsemanticnetworksaretranslatedintoslots一fields

inthedatastructure.Thenameoftheslotdefinesthetypeof

therelationshipandthevalueoftheslotcompletesthe

relationship.InFigure18.2,forexample,animalisaslotin

thereptileobject.

18.14

Predicatelogic

Themostcommonknowledgerepresentationispredicate

logic.Predicatelogiccanbeusedtorepresentcomplexfacts.

Itisawell-definedlanguagedevelopedviaalonghistoryof

theoreticallogic.Althoughthissectiondefinespredicate

logic,wefirstintroducepropositionallogic,asimpler

language.Wethendiscusspredicatelogic,whichemploys

propositionallogic.

18.15

Propositionallogic

Propositionallogicisalanguagemadeupfromasetof

sentencesthatcanbeusedtocarryoutlogicalreasoning

abouttheworld.Propositionallogicusesfiveoperators.

A

F

T

Figure18.3Truthtableforfiveoperatorsinpropositionallogic

18.16

Asentenceinthislanguageisdefinedrecursivelyasshown

below:

1.Anuppercaseletter,suchasA,B,SorT,thatrepresentsa

statementinanaturallanguages,isasentence.

2.Anyofthetwoconstantvalues(trueandfalse)isa

sentence.

3.IfPisasentence,then「Pisasentence.

4.IfPandQaresentences,thenPAQ,PvQ,P—>Qand

P—Qaresentences.

18.17

Example18.1

Thefollowingaresentencesinpropositionallanguage:

a.TodayisSunday(S).

b.Itisraining(R).

c.TodayisSundayorMonday(SvM).

d.Itisnotraining(「R).

e.Ifadogisamammalthenacatisamammal(D—C).

18.18

Deduction

InAIweneedtocreatenewfactsfromtheexistingfacts.In

propositionallogic,theprocessiscalleddeduction.Given

twopresumablytruesentences,wecandeduceanewtrue

sentence.Forexample:

EitherheisathomeorattheofficePremise1:

HeisnotathomePremise2:

Therefore,heisattheofficeConclusion

IfweuseHfor"heisathome”,Ofor"heisatoffice55and

thesymbolI-forthe"therefdre”,thenwecanshowthe

aboveargumentas:

{HvO,「H}|-O

18.19

Onewaytofindifanargumentisvalidistocreateatruth

tableforthepremissesandtheconclusion.Aconclusionis

invalidifwecanfindacounterexamplecase:acaseinwhich

bothpremissesaretrue,buttheconclusionisfalse.

Anargumentisvalidifno

counterexamplecanbefound.

18.20

Example18.2

Thevalidityoftheargument{HvO,->H}|-Ocanbeproved

usingthefollowingtruthtable:

H0Hv0「H0

FFFTF

FTTTT

TFTFF

TTTFT

PremisePremiseConclusion

Theonlyrowtobecheckedisthesecondrow.Thisrowdoesnot

showacounterexample,sotheargumentisvalid.

18.21

Example18.3

Theargument{R一C,C}|-Risnotvalidbecauseacounter

examplecanbefound:

F

F

T

T

PremisePremiseConclusion

Hererow2androw4needtobechecked.Althoughrow4isok,

row2showsacounterexample(twotruepremissesresultina

falseconclusion).Theargumentisthereforeinvalid.

18.22

Predicatelogic

Inpropositionallogic,asymbolthatrepresentsasentenceis

atomic:itcannotbebrokenuptofindinformationaboutits

components.Forexample,considerthesentences:

,,

P/"LindaisMary'smother"P2:MaryisAnne'smother”

Wecancombinethesetwosentencesinmanywaystocreate

othersentences,butwecannotextractanyrelationbetween

LindaandAnne.Forexample,wecannotinferfromthe

abovetwosentencesthatLindaisthegrandmotherofAnne.

Todoso,weneedpredicatelogic:thelogicthatdefinesthe

relationbetweenthepartsinaproposition.

18.23

Inpredicatelogic,asentenceisdividedintoapredicateand

arguments.Forexample,eachofthefollowingpropositions

canbewrittenaspredicateswithtwoarguments:

“LindaisMary'smother“becomesmother(Linda,Mary)

H

P2:MaryisAnne'smother“becomesmother(Mary,Anne)

Therelationshipofmotherhoodineachoftheabove

sentencesisdefinedbythepredicatemother.Iftheobject

Maryinbothsentencesreferstothesameperson,wecan

inferanewrelationbetweenLindaandAnne:

grandmother(Linda,Anne)

18.24

Asentenceinpredicatelanguageisdefinedasfollows:

1.Apredicatewithnargumentsisasentence.

2.Anyofthetwoconstantvalues(trueandfalse)isa

sentence.

3.IfPisasentence,then「Pisasentence.

4.IfPandQaresentences,thenPAQ,PvQ,P一Q,and

P<->Qaresentences.

18.25

Example18.4

1.Thesentence“JohnworksforAnn'ssister“canbewrittenas:

Works[John,sister(Ann)]inwhichthefunctionsister(Ann)is

usedasanargument.

2.Thesentence“John'sfatherlovesAnn'ssister“canbewritten

as:loves[father(John),sister(Ann)]

18.26

Predicatelogicallowsustousequantifiers.Twoquantifiers

arecommoninpredicatelogic:

and三

1.Thefirst,whichisreadas"fbrall”,iscalledtheuniversal

quantifier:itstatesthatsomethingistrueforeveryobject

thatitsvariablerepresents.

2.Thesecond,whichisreadas"thereexists”,iscalledthe

existentialquantifier:itstatesthatsomethingistruefor

oneormoreobjectsthatitsvariablerepresents.

18.27

Example18.5

1.Thesentence"Allmenaremortals“canbewrittenas:

Vx[man(x)-mortal(x)]

2.Thesentence"Frogsaregreen“canbewrittenas:

Vx[frog(x)-green(x)]

3.Thesentence"Someflowersarered”canbewrittenas:

3x[flower(x)Ared(x)]

18.28

Example18.5Continued

4.Thesentence"Johnhasabook"canbewrittenas:

3x[book(x)Ahas(John,x)]

5.Thesentence“Nofrogisyellow"canbewrittenas:

Vx[frog(x)--yellow(x)]

or

-3x[frog(x)Ayellow(x)]

18.29

Deduction

Inpredicatelogic,ifthereisnoquantifier,theverificationof

anargumentisthesameasthatwhichwediscussedin

propositionallogic.However,theverificationbecomesmore

complicatediftherearequantifiers.Forexample,the

followingargumentiscompletelyvalid.

AllmenaremortalsPremise1:

SocratesisamanPremise2:

Therefore,SocratesismortalConclusion

Verificationofthissimpleargumentisnotdifficult.Wecan

writethisargumentasshownnext:

18.30

Vx[man(x)-?mortal(x)],man(Socrates)|-mortal(Socrates)

Sincethefirstpremisetalksaboutallmen,wecanreplace

oneinstanceoftheclassman(Socrates)inthatpremiseto

getthefollowingargument:

man(Socrates)-*mortal(Socrates),man(Socrates)|-mortal(Socrates)

WhichisreducedtoMl—>M2,Ml|-M2,inwhichMlis

man(Socrates)andM2ismortal(Socrates).Theresultisan

argumentinpropositionallogicandcanbeeasilyvalidated.

18.31

Beyondpredicatelogic

Therehavebeenfurtherdevelopmentsinlogictoincludethe

needforlogicalreasoning.Someexamplesoftheseinclude

high-orderlogic,defaultlogic,modallogicandtemporal

logic.

18.32

Rule-basedsystems

Arule-basedsystemrepresentsknowledgeusingasetof

rulesthatcanbeusedtodeducenewfactsfromknownfacts.

Therulesexpresswhatistrueifspecificconditionsaremet.

Arule-baseddatabaseisasetofif...then...statementsin

theform

IfAthenBorA—B

inwhichAiscalledtheantecedentandBiscalledthe

consequent.Notethatinarule-basedsystem,eachruleis

handledindependentlywithoutanyconnectiontootherrules.

18.33

Components

Arule-basedsystemismadeupofthreecomponents:an

interpreter(orinferenceengine),aknowledgebaseandafact

database,asshowninFigure18.4.

Factdatabase

Interpreter

Knowledgebase(Interferenceengine)

Figure18.4Thecomponentsofarule-basedsystem

18.34

Forwardchaining

Forwardchainingisaprocessinwhichaninterpreterusesa

setofrulesandasetoffactstoperformanaction.

Figure18.5Flowdiagramforforwardchaining

18.35

Backwardchaining

Forwardchainingisnotveryefficientifthesystemtriesto

proveaconclusion.Inthiscase,itmaybemoreefficientif

backwardchainingisused.

Figure18.6Flowdiagramforbackwardchaining

18.36

18-3EXPERTSYSTEMS

Expertsystemsusetheknowledgerepresentation

languagesdiscussedintheprevioussectiontoperform

tasksthatnormallyneedhumanexpertise.Theycanbe

usedinsituationsinwhichthatexpertiseisinshort

supply,expensiveorunavailablewhenrequired.For

example,inmedicine,anexpertsystemcanbeusedto

narrowdownasetofsymptomstoalikelysubsetof

causes,atasknormallycarriedoutbyadoctor.

18.37

Extractingknowledge

Anexpertsystemisbuiltonpredefinedknowledgeaboutits

fieldofexpertise.Anexpertsysteminmedicine,for

example,isbuiltontheknowledgeofadoctorspecializedin

thefieldforwhichthesystemisbuilt:anexpertsystemis

supposedtodothesamejobasthehumanexpert.Thefirst

stepinbuildinganexpertsystemis,therefore,toextractthe

knowledgefromahumanexpert.Thisextractedknowledge

becomestheknowledgebasewediscussedintheprevious

section.

18.38

Extractingknowledge

Tobeabletoinfernewfactsorperformactions,afact

databaseisneededinadditiontotheknowledgebasefora

knowledgerepresentationlanguage.Thefactdatabaseinan

expertsystemiscase-based,inwhichfactscollectedor

measuredareenteredintothesystemtobeusedbythe

inferenceengine.

18.39

Architecture

Figure18.7showsthegeneralideabehindthearchitectureof

anexpertsystem.

美User

Expertsystemshell

Knowledge

basedatabase

Figure18.7Thearchitectureofanexpertsystem

18.40

18-4PERCEPTION

AnothergoalofAIistocreateamachinethatbehaves

likeanordinaryhuman.Oneofthemeaningsofthe

word“perception“isunderstandingwhatisreceived

throughthesenses——sight,hearing,touch,smell,taste.

Ahumanbeingseesascenethroughtheeyes,andthe

braininterpretsittoextractthetypeofobjectsinthe

scene.Ahumanbeinghearsasetofvoicesignals

throughtheears,andthebraininterpretsitasa

meaningfulsentence,andsoon.

18.41

Imageprocessing

ImageprocessingorcomputervisionisanareaofAIthat

dealswiththeperceptionofobjectsthroughtheartificial

eyesofanagent,suchasacamera.Animageprocessortakes

atwo-dimensionalimagefromtheoutsideworldandtriesto

createadescriptionofthethree-dimensionalobjectspresent

inthescene.Although,thisisaneasytasksforahuman

being,itturnsouttobeadifficulttaskforanartificialagent.

Theinputpresentedtoanimageprocessisoneormore

imagesfromthescene,whiletheoutputisadescriptionof

theobjectsinthescene.Theprocessorusesadatabase

containingthecharacteristicsofobjectsforcomparison.

18.42

Fwo-dimensional

images

Imageprocessor

Databaseofobject

characteristics

Three-dimensional

characteristicsofobjects

Figure18.8Thecomponentsofanimageprocessor

18.43

Edgedetection

Thefirststageinimageprocessingisedgedetection:finding

wheretheedgesintheimageare.Edgescandefinethe

boundariesbetweenanobjectanditsbackgroundinthe

image.Normallythereisasharpcontrastbetweenthe

surfacesbelongingtoanobjectandtheenvironment,

assumingthatthereisnocamouflage.

99999999

99999999

92322999

92474999

92345329

92932929

99999999

99999999

ImageIntensityofpixels

Figure18.9Theedge-detectionprocess

18.44

Segmentation

Segmentationisthenextstageinimageanalysis.

Segmentationdividestheimageintohomogenoussegments

orareas.Thedefinitionofhomogeneitydiffersindifferent

methods,butingeneral,ahomogenousareaisanareain

whichtheintensityofpixelsvariessmoothly.Segmentation

isverysimilartoedgedetection.Inedgedetection,the

boundariesoftheobjectandthebackgroundarefound:in

segmentation,theboundariesbetweendifferentareasinside

theobjectarefound.Aftersegmentation,theobjectis

dividedintodifferentareas.

18.45

Findingdepth

Thenextstepinimageanalysisistofindthedepthofthe

objectorobjectsintheimage.Twogeneralmethodshave

beenusedforthispurpose:stereovisionandmotion.

Findingorientation

Orientationoftheobjectinthescenecanbefoundusingtwo

techniques:shadingandtexture.

Figure18.10Theeffectofshadingonorientationfinding

18.46

Objectrecognition

Thelaststepinimageprocessingisobjectrecognition.To

recognizeanobject,theagentneedstohaveamodelofthe

objectinmemoryforcomparison.However,creatingand

storingamodelforeachobjectintheviewisanimpossible

task.Onesolutionistoassumethattheobjectstobe

recognizedarecompoundobjectsmadeofasetofsimple

geometricshapes.

BlockCylinderConeTruncatedpyramid

Figure18.11Primitivegeometricshapes

18.47

Languageunderstanding

Oneoftheinherentcapabilitiesofahumanbeingisto

understand-thatis,interpret-theaudiosignalthatthey

perceive.Amachinethatcanunderstandnaturallanguage

canbeveryusefulindailylife.Forexample,itcanreplacea

telephoneoperator-mostofthetime.Itcanalsobeusedon

occasionswhenasystemneedsapredefinedformatof

queries.Wecandividethetaskofamachinethatunderstands

naturallanguageintofourconsecutivesteps:speech

recognition,syntacticanalysis,semanticanalysisand

pragmaticanalysis.

18.48

Speechrecognition

Thefirststepinnaturallanguageprocessingisspeech

recognition.Inthisstep,aspeechsignalisanalyzedandthe

sequenceofwordsitcontainsareextracted.Theinputtothe

speechrecognitionsubsystemisacontinuous(analog)

signal:theoutputisasequenceofwords.Thesignalneedsto

bedividedintodifferentsounds,sometimescalled

phonemes.Thesoundsthenneedtobecombinedintowords.

Thedetailedprocess,however,isbeyondthescopeofthis

book:weleavethetasktospecializedbooksinspeech

recognition.

18.49

Syntacticanalysis

Thesyntacticanalysisstepisusedtodefinehowwordsare

tobegroupedinasentence.Thisisadifficulttaskina

languagelikeEnglish,inwhichthefunctionofawordina

sentenceisnotdeterminedbyitspositioninthesentence.

Forexample,inthefollowingtwosentences:

MaryrewardedJohn.

JohnwasrewardedbyMary.

itisalwaysJohnwhoisrewarded,butinthefirstsentence

JohnisinthelastpositionandMaryisinthefirstposition.A

machinethathearsanyoftheabovesentencesneedsto

interpretthemcorrectlyandcometothesameconclusionno

matterwhichsentenceisheard.

18.50

Grammar

Thefirsttooltocorrectlyanalyzeasentenceisawell-

definedgrammar.WeuseasimpleversionofBNF(Backus-

NaurForm)thatisusedincomputersciencetodefinethe

syntaxofaprogramminglanguage(Table18.1).

Table18.1Asimplegrammar

Rule

1Sentence—>NounPhraseVerbPhrase

2NounPhrase—>NounArticleNounArticleAdjectiveNoun

3VerbPhrase—>VerbVerbNounPhraseVerbNounPhraseAdverb

4Noun—>[home]'[cat][water][dog]|[John][Mary]|

5Article—>[a]|[the]

6Adjective—>[big]|[small]|[tall]|[short]|[white]|[black]|

7Verb―>[goes]|[comes]|[eats]|[drinks]|[has]

18.51

Parser

Itshouldbeclearthatevenasimplegrammarasdefinedin

Table18.1usesdifferentoptions.Amachinethatdetermines

ifasentenceisgrammatically(syntactically)correctdoesnot

needtocheckallpossiblechoicesbeforerejectingasentence

asaninvalidone.Thisisdonebyaparser.

Sentence

Figure18.12Parsingasentence

18.52

Semanticanalysis

Thesemanticanalysisextractsthemeaningofasentence

afterithasbeensyntacticallyanalyzed.Thisanalysiscreates

arepresentationoftheobjectsinvolvedinthesentence,their

relationsandtheirattributes.Theanalysiscanuseanyofthe

knowledgerepresentationschemeswediscussedbefore.For

example,thesentence"Johnhasadog“canberepresented

usingpredicatelogicas:

3xdog(x)has(John,x)

18.53

Pragmaticanalysis

Thethreeprevioussteps一speechrecognition,syntax

analysisandsemanticanalysis一cancreateaknowledge

representationofaspokensentence.Inmostcases,another

step,pragmaticanalysis,isneededtofurtherclarifythe

purposeofthesentenceandtoremoveambiguities.

18.54

18-5SEARCHING

Oneofthetechniquesforsolvingproblemsinartificial

intelligenceissearching,whichisdiscussedbrieflyin

thissection.Searchingcanbedescribeassolvinga

problemusingasetofstates(asituation).Asearch

procedurestartsfromaninitialstate,goesthrough

intermediatestatesuntilfinallyreachingatargetstate.

Forexample,insolvingapuzzle,theinitialstateisthe

unsolvedpuzzle,theintermediatestatesarethesteps

takentosolvethepuzzleandthetargetstateisthe

situationinwhichthepuzzleissolved.Thesetofall

statesusedbyasearchingprocessisreferredtoasthe

searchspace.

18.55

Figure18.13Anexampleofasearchspace

18.56

Example18.6

Oneexampleofapuzzlethatshowsthesearchspaceisthe

famous8-puzzle.Thetilesarenumberedfrom1to8.Givenan

initialrandomarrangementofthetiles(theinitialstate),thegoal

istorearrangethetilesuntilaorderedarrangementofthetilesis

reached(thetargetstate).Theruleofthegameisthatatilecanbe

slidintoanemptyslot.

UnsolvedSolved

puzzle□puzzle

SearchIn

HL

ln

OnepossibleOnnelpossible

initialstatetareetstlatne

Figure8.14ApossibleinitialandfinalstateforExample18.6

18.57

Searchmethods

Therearetwogeneralsearchmethods:brute-forceand

heuristic.Thebruteforcemethodisitselfeitherbreadth-first

ordepthfirst

Brute-forcesearch

Weusebrute-forcesearchifwedonothaveanyprior

knowledgeaboutthesearch.Forexample,considerthesteps

requiredtofindourwaythroughthemazeinFigure18.15

withpointsAandTasstartingandfinishingpoints

respectively.Thetreediagramforthemazeisshownin

Figure18.16.

18.58

pi

Bj

8

s

3

2

0

J

3

uI

q

A

oi

q

ss

p

s

ns

Q

Z

UE

vI

S

I

8.

I

g

x

n

M

E

6

g

cdL

Figure18.16ThetreeforthemazeinFigure18.15

18.60

Figure18.17Depth-firstsearchofthetreeinFigure18.16

18.61

Level1

Level2

Level3

Level4

Level5

Level6

Level7

Figure18.18Breadth-firstsearchofthetreeinFigure18.16

18.62

Heuristicsearch

Usingheuristicsearch,weassignaquantitativevaluecalled

aheuristicvalue(hvalue)toeachnode.Thisquantitative

valueshowstherelativeclosenessofthenodetothegoal

state.Forexample,considersolvingthe8-puzzleofFigure

18.19.

InitialstateGoalstate

123123

78684

54765

h=6h=0

Figure18.19Initialandgoalstatesforheuristicsearch

18.63

Table18.2Heuristicvalue

Tilenumber12345678Total

Heuristicvalueofinitialstate000112116