nodegraphsearch
graphsearch 时间:2021-05-25 阅读:()
CS347–IntroductiontoArtificialIntelligenceDr.
DanielTauritz(Dr.
T)DepartmentofComputerSciencetauritzd@mst.
eduhttp://web.
mst.
edu/~tauritzd/CS347coursewebsite:http://web.
mst.
edu/~tauritzd/courses/cs347/WhatisAISystemsthat…actlikehumans(TuringTest)thinklikehumansthinkrationallyactrationallyPlayUltimatumGameKeyhistoricaleventsforAI4thcenturyBCAristotlepropositionallogic1600'sDescartesmind-bodyconnection1805FirstprogrammablemachineMid1800'sCharlesBabbage's"differenceengine"&"analyticalengine"LadyLovelace'sObjection1847GeorgeBoolepropositionallogic1879GottlobFregepredicatelogicKeyhistoricaleventsforAI1931KurtGodel:IncompletenessTheoremInanylanguageexpressiveenoughtodescribenaturalnumberproperties,thereareundecidable(incomputable)truestatements1943McCulloch&Pitts:NeuralComputation1956Term"AI"coined1976Newell&Simon's"PhysicalSymbolSystemHypothesis"Aphysicalsymbolsystemhasthenecessaryandsufficientmeansforgeneralintelligentaction.
HowdifficultisittoachieveAIThreeSistersPuzzleRationalAgentsEnvironmentSensors(percepts)Actuators(actions)AgentFunctionAgentProgramPerformanceMeasuresRationalBehaviorDependson:Agent'sperformancemeasureAgent'spriorknowledgePossibleperceptsandactionsAgent'sperceptsequenceRationalAgentDefinition"Foreachpossibleperceptsequence,arationalagentselectsanactionthatisexpectedtomaximizeitsperformancemeasure,giventheevidenceprovidedbytheperceptsequenceandanypriorknowledgetheagenthas.
"TaskEnvironmentsPEASdescription&properties:Fully/PartiallyObservableDeterministic,Stochastic,StrategicEpisodic,SequentialStatic,Dynamic,Semi-dynamicDiscrete,ContinuousSingleagent,MultiagentCompetitive,CooperativeProblem-solvingagentsAdefinition:Problem-solvingagentsaregoalbasedagentsthatdecidewhattodobasedonanactionsequenceleadingtoagoalstate.
Problem-solvingstepsProblem-formulation(actions&states)Goal-formulation(states)Search(actionsequences)ExecutesolutionWell-definedproblemsInitialstateActionsetTransitionmodel:RESULT(s,a)GoaltestPathcostSolution/optimalsolutionExampleproblemsVacuumworldTic-tac-toe8-puzzle8-queensproblemSearchtreesRootcorrespondswithinitialstateVacuumstatespacevs.
searchtreeSearchalgorithmsiteratethroughgoaltestingandexpandingastateuntilgoalfoundOrderofstateexpansioniscritical!
Searchnodedatastructuren.
STATEn.
PARENT-NODEn.
ACTIONn.
PATH-COSTStatesareNOTsearchnodes!
FrontierFrontier=SetofleafnodesImplementedasaqueuewithops:EMPTY(queue)POP(queue)INSERT(element,queue)Queuetypes:FIFO,LIFO(stack),andpriorityqueueProblem-solvingperformanceCompletenessOptimalityTimecomplexitySpacecomplexityComplexityinAIb–branchingfactord–depthofshallowestgoalnodem–maxpathlengthinstatespaceTimecomplexity:#generatednodesSpacecomplexity:max#nodesstoredSearchcost:time+spacecomplexityTotalcost:search+pathcostTreeSearchBreadthFirstTreeSearch(BFTS)UniformCostTreeSearch(UCTS)Depth-FirstTreeSearch(DFTS)Depth-LimitedTreeSearch(DLTS)Iterative-DeepeningDepth-FirstTreeSearch(ID-DFTS)Examplestatespace#1BreadthFirstTreeSearch(BFTS)Frontier:FIFOqueueComplete:ifbanddarefiniteOptimal:ifpath-costisnon-decreasingfunctionofdepthTimecomplexity:O(b^d)Spacecomplexity:O(b^d)UniformCostTreeSearch(UCTS)Frontier:priorityqueueorderedbyg(n)DepthFirstTreeSearch(DFTS)Frontier:LIFOqueue(a.
k.
a.
stack)Complete:noOptimal:noTimecomplexity:O(bm)Spacecomplexity:O(bm)BacktrackingversionofDFTShasaspacecomplexityof:O(m)Depth-LimitedTreeSearch(DLTS)Frontier:LIFOqueue(a.
k.
a.
stack)Complete:notwhenl=βPruneiffail-lowforMin-playerPruneiffail-highforMax-playerDLMw/Alpha-BetaPruningTimeComplexityWorst-case:O(bd)Best-case:O(bd/2)[Knuth&Moore,1975]Average-case:O(b3d/4)MoveOrderingHeuristicsKnowledgebasedKillerMove:thelastmoveatagivendepththatcausedAB-pruningorhadbestminimaxvalueHistoryTableExamplegametreeExamplegametreeSearchDepthHeuristicsTimebased/StatebasedHorizonEffect:thephenomenonofdecidingonanon-optimalprincipalvariantbecauseanultimatelyunavoidabledamagingmoveseemstobeavoidedbyblockingittillpassedthesearchdepthSingularExtensions/QuiescenceSearchTimePerMoveConstantPercentageofremainingtimeStatedependentHybridQuiescenceSearchWhensearchdepthreached,computequiescencestateevaluationheuristicIfstatequiescent,thenproceedasusual;otherwiseincreasesearchdepthifquiescencesearchdepthnotyetreachedCallformat:QSDLM(root,depth,QSdepth),QSABDLM(root,depth,QSdepth,α,β),etc.
QSgametreeEx.
1QSgametreeEx.
2ForwardpruningBeamSearch(nbestmoves)ProbCut(forwardpruningversionofalpha-betapruning)TranspositionTables(1)HashtableofpreviouslycalculatedstateevaluationheuristicvaluesSpeedupisparticularlyhugeforiterativedeepeningsearchalgorithms!
GoodforchessbecauseoftenrepeatedstatesinsamesearchTranspositionTables(2)Datastructure:HashtableindexedbypositionElement:StateevaluationheuristicvalueSearchdepthofstoredvalueHashkeyofposition(toeliminatecollisions)(optional)BestmovefrompositionTranspositionTables(3)ZobristhashkeyGenerate3d-arrayofrandom64-bitnumbers(piecetype,locationandcolor)Startwitha64-bithashkeyinitializedto0Loopthroughcurrentposition,XOR'inghashkeywithZobristvalueofeachpiecefound(note:onceakeyhasbeenfound,useanincrementalapporachthatXOR'sthe"from"locationandthe"to"locationtomoveapiece)MTD(f)MTDf(root,guess,depth){lower=-∞;upper=∞;do{beta=guess+(guess==lower);guess=ABMaxV(root,depth,beta-1,beta);if(guessExtendedFutilityPruningRazoringState-SpaceSearchComplete-stateformulationObjectivefunctionGlobaloptimaLocaloptima(don'tusetextbook'sdefinition!
)Ridges,plateaus,andshouldersRandomsearchandlocalsearchSteepest-AscentHill-ClimbingGreedyAlgorithm-makeslocallyoptimalchoicesExample8queensproblemhas88≈17MstatesSAHCfindsglobaloptimumfor14%ofinstancesinonaverage4steps(3stepswhenstuck)SAHCw/upto100consecutivesidewaysmoves,findsglobaloptimumfor94%ofinstancesinonaverage21steps(64stepswhenstuck)StochasticHill-ClimbingChoosesatrandomfromamonguphillmovesProbabilityofselectioncanvarywiththesteepnessoftheuphillmoveOnaverageslowerconvergence,butalsolesschanceofprematureconvergenceMoreLocalSearchAlgorithmsFirst-choicehill-climbingRandom-restarthill-climbingSimulatedAnnealingPopulationBasedLocalSearchDeterministiclocalbeamsearchStochasticlocalbeamsearchEvolutionaryAlgorithmsParticleSwarmOptimizationAntColonyOptimizationParticleSwarmOptimizationPSOisastochasticpopulation-basedoptimizationtechniquewhichassignsvelocitiestopopulationmembersencodingtrialsolutionsPSOupdaterules:PSOdemo:http://www.
borgelt.
net//psopt.
htmlAntColonyOptimizationPopulationbasedPheromonetrailandstigmergeticcommunicationShortestpathsearchingStochasticmovesOnlineSearchOfflinesearchvs.
onlinesearchInterleavingcomputation&actionExplorationproblems,safelyexplorableAgentshaveaccessto:ACTIONS(s)c(s,a,s')GOAL-TEST(s)OnlineSearchOptimalityCR–CompetitiveRatioTAPC–TotalActualPathCostC*-OptimalPathCostBestcase:CR=1Worstcase:CR=∞OnlineSearchAlgorithmsOnline-DFS-AgentRandomWalkLearningReal-TimeA*(LRTA*)OnlineSearchExampleGraph1OnlineSearchExampleGraph2OnlineSearchExampleGraph3AIcoursesatS&TCS345ComputationalRoboticManipulation(SP2012)CS347IntroductiontoArtificialIntelligence(SP2012)CS348EvolutionaryComputing(FS2011)CS434DataMining&KnowledgeDiscovery(FS2011)CS447AdvancedTopicsinAI(SP2013)CS448AdvancedEvolutionaryComputing(SP2012)CpE358ComputationalIntelligence(FS2011)SysEng378IntrotoNeuralNetworks&Applications
DanielTauritz(Dr.
T)DepartmentofComputerSciencetauritzd@mst.
eduhttp://web.
mst.
edu/~tauritzd/CS347coursewebsite:http://web.
mst.
edu/~tauritzd/courses/cs347/WhatisAISystemsthat…actlikehumans(TuringTest)thinklikehumansthinkrationallyactrationallyPlayUltimatumGameKeyhistoricaleventsforAI4thcenturyBCAristotlepropositionallogic1600'sDescartesmind-bodyconnection1805FirstprogrammablemachineMid1800'sCharlesBabbage's"differenceengine"&"analyticalengine"LadyLovelace'sObjection1847GeorgeBoolepropositionallogic1879GottlobFregepredicatelogicKeyhistoricaleventsforAI1931KurtGodel:IncompletenessTheoremInanylanguageexpressiveenoughtodescribenaturalnumberproperties,thereareundecidable(incomputable)truestatements1943McCulloch&Pitts:NeuralComputation1956Term"AI"coined1976Newell&Simon's"PhysicalSymbolSystemHypothesis"Aphysicalsymbolsystemhasthenecessaryandsufficientmeansforgeneralintelligentaction.
HowdifficultisittoachieveAIThreeSistersPuzzleRationalAgentsEnvironmentSensors(percepts)Actuators(actions)AgentFunctionAgentProgramPerformanceMeasuresRationalBehaviorDependson:Agent'sperformancemeasureAgent'spriorknowledgePossibleperceptsandactionsAgent'sperceptsequenceRationalAgentDefinition"Foreachpossibleperceptsequence,arationalagentselectsanactionthatisexpectedtomaximizeitsperformancemeasure,giventheevidenceprovidedbytheperceptsequenceandanypriorknowledgetheagenthas.
"TaskEnvironmentsPEASdescription&properties:Fully/PartiallyObservableDeterministic,Stochastic,StrategicEpisodic,SequentialStatic,Dynamic,Semi-dynamicDiscrete,ContinuousSingleagent,MultiagentCompetitive,CooperativeProblem-solvingagentsAdefinition:Problem-solvingagentsaregoalbasedagentsthatdecidewhattodobasedonanactionsequenceleadingtoagoalstate.
Problem-solvingstepsProblem-formulation(actions&states)Goal-formulation(states)Search(actionsequences)ExecutesolutionWell-definedproblemsInitialstateActionsetTransitionmodel:RESULT(s,a)GoaltestPathcostSolution/optimalsolutionExampleproblemsVacuumworldTic-tac-toe8-puzzle8-queensproblemSearchtreesRootcorrespondswithinitialstateVacuumstatespacevs.
searchtreeSearchalgorithmsiteratethroughgoaltestingandexpandingastateuntilgoalfoundOrderofstateexpansioniscritical!
Searchnodedatastructuren.
STATEn.
PARENT-NODEn.
ACTIONn.
PATH-COSTStatesareNOTsearchnodes!
FrontierFrontier=SetofleafnodesImplementedasaqueuewithops:EMPTY(queue)POP(queue)INSERT(element,queue)Queuetypes:FIFO,LIFO(stack),andpriorityqueueProblem-solvingperformanceCompletenessOptimalityTimecomplexitySpacecomplexityComplexityinAIb–branchingfactord–depthofshallowestgoalnodem–maxpathlengthinstatespaceTimecomplexity:#generatednodesSpacecomplexity:max#nodesstoredSearchcost:time+spacecomplexityTotalcost:search+pathcostTreeSearchBreadthFirstTreeSearch(BFTS)UniformCostTreeSearch(UCTS)Depth-FirstTreeSearch(DFTS)Depth-LimitedTreeSearch(DLTS)Iterative-DeepeningDepth-FirstTreeSearch(ID-DFTS)Examplestatespace#1BreadthFirstTreeSearch(BFTS)Frontier:FIFOqueueComplete:ifbanddarefiniteOptimal:ifpath-costisnon-decreasingfunctionofdepthTimecomplexity:O(b^d)Spacecomplexity:O(b^d)UniformCostTreeSearch(UCTS)Frontier:priorityqueueorderedbyg(n)DepthFirstTreeSearch(DFTS)Frontier:LIFOqueue(a.
k.
a.
stack)Complete:noOptimal:noTimecomplexity:O(bm)Spacecomplexity:O(bm)BacktrackingversionofDFTShasaspacecomplexityof:O(m)Depth-LimitedTreeSearch(DLTS)Frontier:LIFOqueue(a.
k.
a.
stack)Complete:notwhenl=βPruneiffail-lowforMin-playerPruneiffail-highforMax-playerDLMw/Alpha-BetaPruningTimeComplexityWorst-case:O(bd)Best-case:O(bd/2)[Knuth&Moore,1975]Average-case:O(b3d/4)MoveOrderingHeuristicsKnowledgebasedKillerMove:thelastmoveatagivendepththatcausedAB-pruningorhadbestminimaxvalueHistoryTableExamplegametreeExamplegametreeSearchDepthHeuristicsTimebased/StatebasedHorizonEffect:thephenomenonofdecidingonanon-optimalprincipalvariantbecauseanultimatelyunavoidabledamagingmoveseemstobeavoidedbyblockingittillpassedthesearchdepthSingularExtensions/QuiescenceSearchTimePerMoveConstantPercentageofremainingtimeStatedependentHybridQuiescenceSearchWhensearchdepthreached,computequiescencestateevaluationheuristicIfstatequiescent,thenproceedasusual;otherwiseincreasesearchdepthifquiescencesearchdepthnotyetreachedCallformat:QSDLM(root,depth,QSdepth),QSABDLM(root,depth,QSdepth,α,β),etc.
QSgametreeEx.
1QSgametreeEx.
2ForwardpruningBeamSearch(nbestmoves)ProbCut(forwardpruningversionofalpha-betapruning)TranspositionTables(1)HashtableofpreviouslycalculatedstateevaluationheuristicvaluesSpeedupisparticularlyhugeforiterativedeepeningsearchalgorithms!
GoodforchessbecauseoftenrepeatedstatesinsamesearchTranspositionTables(2)Datastructure:HashtableindexedbypositionElement:StateevaluationheuristicvalueSearchdepthofstoredvalueHashkeyofposition(toeliminatecollisions)(optional)BestmovefrompositionTranspositionTables(3)ZobristhashkeyGenerate3d-arrayofrandom64-bitnumbers(piecetype,locationandcolor)Startwitha64-bithashkeyinitializedto0Loopthroughcurrentposition,XOR'inghashkeywithZobristvalueofeachpiecefound(note:onceakeyhasbeenfound,useanincrementalapporachthatXOR'sthe"from"locationandthe"to"locationtomoveapiece)MTD(f)MTDf(root,guess,depth){lower=-∞;upper=∞;do{beta=guess+(guess==lower);guess=ABMaxV(root,depth,beta-1,beta);if(guess
)Ridges,plateaus,andshouldersRandomsearchandlocalsearchSteepest-AscentHill-ClimbingGreedyAlgorithm-makeslocallyoptimalchoicesExample8queensproblemhas88≈17MstatesSAHCfindsglobaloptimumfor14%ofinstancesinonaverage4steps(3stepswhenstuck)SAHCw/upto100consecutivesidewaysmoves,findsglobaloptimumfor94%ofinstancesinonaverage21steps(64stepswhenstuck)StochasticHill-ClimbingChoosesatrandomfromamonguphillmovesProbabilityofselectioncanvarywiththesteepnessoftheuphillmoveOnaverageslowerconvergence,butalsolesschanceofprematureconvergenceMoreLocalSearchAlgorithmsFirst-choicehill-climbingRandom-restarthill-climbingSimulatedAnnealingPopulationBasedLocalSearchDeterministiclocalbeamsearchStochasticlocalbeamsearchEvolutionaryAlgorithmsParticleSwarmOptimizationAntColonyOptimizationParticleSwarmOptimizationPSOisastochasticpopulation-basedoptimizationtechniquewhichassignsvelocitiestopopulationmembersencodingtrialsolutionsPSOupdaterules:PSOdemo:http://www.
borgelt.
net//psopt.
htmlAntColonyOptimizationPopulationbasedPheromonetrailandstigmergeticcommunicationShortestpathsearchingStochasticmovesOnlineSearchOfflinesearchvs.
onlinesearchInterleavingcomputation&actionExplorationproblems,safelyexplorableAgentshaveaccessto:ACTIONS(s)c(s,a,s')GOAL-TEST(s)OnlineSearchOptimalityCR–CompetitiveRatioTAPC–TotalActualPathCostC*-OptimalPathCostBestcase:CR=1Worstcase:CR=∞OnlineSearchAlgorithmsOnline-DFS-AgentRandomWalkLearningReal-TimeA*(LRTA*)OnlineSearchExampleGraph1OnlineSearchExampleGraph2OnlineSearchExampleGraph3AIcoursesatS&TCS345ComputationalRoboticManipulation(SP2012)CS347IntroductiontoArtificialIntelligence(SP2012)CS348EvolutionaryComputing(FS2011)CS434DataMining&KnowledgeDiscovery(FS2011)CS447AdvancedTopicsinAI(SP2013)CS448AdvancedEvolutionaryComputing(SP2012)CpE358ComputationalIntelligence(FS2011)SysEng378IntrotoNeuralNetworks&Applications
- nodegraphsearch相关文档
- resultsgraphsearch
- reciprocatedgraphsearch
- memorygraphsearch
- graphgraphsearch
- swappedgraphsearch
- annotategraphsearch
Virtono：圣何塞VPS七五折月付2.2欧元起,免费双倍内存
Virtono是一家成立于2014年的国外VPS主机商，提供VPS和服务器租用等产品，商家支持PayPal、信用卡、支付宝等国内外付款方式，可选数据中心共7个：罗马尼亚2个，美国3个(圣何塞、达拉斯、迈阿密)，英国和德国各1个。目前，商家针对美国圣何塞机房VPS提供75折优惠码，同时，下单后在LET回复订单号还能获得双倍内存的升级。下面以圣何塞为例，分享几款VPS主机配置信息。Cloud VPSC...
#推荐# cmivps：全场7折，香港不限流量VPS，支持Windows系统
cmivps香港VPS带来了3个新消息：（1）双向流量改为单向流量，相当于流量间接扩大一倍；（2）Hong Kong 2T、Hong Kong 3T、Hong Kong 无限流量，这三款VPS开始支持Windows系统，如果需要中文版Windows系统请下单付款完成之后发ticket要求官方更改即可；（3）全场7折年付、8折月付优惠，优惠码有效期一个月！官方网站：https://www.cmivp...
宝塔面板企业版和专业版618年中活动 永久授权仅1888元+
我们一般的站长或者企业服务器配置WEB环境会用到免费版本的宝塔面板。但是如果我们需要较多的付费插件扩展，或者是有需要企业功能应用的，短期来说我们可能选择按件按月付费的比较好，但是如果我们长期使用的话，有些网友认为选择宝塔面板企业版或者专业版是比较划算的。这样在年中大促618的时候，我们也可以看到宝塔面板也有发布促销活动。企业版年付899元，专业版永久授权1888元起步。对于有需要的网友来说，还是值...
graphsearch为你推荐
-
Sicherheitsserverhostschrome支持ipad支持ipad支持ipad请仔细阅读在本报告尾部的重要法律声明eaccelerator使用apmsevr中eAccelerator显示NO是什么问题勒索病毒win7补丁怎么删除 防勒索病毒 打的补丁ms17-010win10华为 slatl10是什么型号迅雷下载速度为什么现在迅雷下载的速度比原来慢得多？win7还原系统win7怎么初始化系统？系统还原？