树搜寻算法与回溯算法(高价值)_第1页
树搜寻算法与回溯算法(高价值)_第2页
树搜寻算法与回溯算法(高价值)_第3页
树搜寻算法与回溯算法(高价值)_第4页
树搜寻算法与回溯算法(高价值)_第5页
已阅读5页,还剩48页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

树搜寻算法与回溯算法歧路亡羊与追本溯源1.1树搜寻算法基本概念树搜寻解题策略许多问题的寻找解答过程可以使用树(tree)来表达,这类问题也都可以建构出解答空间树(solutionspacetree)。要找到这些问题的解答,不管是可行解(feasiblesolution)或是最佳解(optimalsolution),就转变成一个树搜寻(treesearch)问题。3SlidingBlockPuzzleSource:/8-puzzle-game/4(n2-1)-拼图问题定义(n2-1)-拼图问题(puzzleproblem):给定一个n×n的方格(grid)(n≥3),随机挑选其中的(n2-1)个单格(cell)填入1到(n2-1)的数字,而留下一个空的单格,形成起始状态,而空的单格可以由相邻的上、下、左或右方单格移入其数字。(n2-1)-拼图问题讨论如何找出数字移入空格的方式,借以达成某个指定的填入数字目标状态。5(n2-1)-拼图问题范例8-拼图问题(8-puzzleproblem)68-拼图问题解答空间树的一部份7树搜寻算法有许多算法可以拜访(visit)与扩展(expand)一个解答空间树,包括:广度优先搜寻width-firstsearch深度优先搜寻depth-firstsearch登山搜寻hill-climbingsearch最佳优先搜寻best-firstsearch81.2广度优先搜寻算法广度优先搜寻算法WFS广度优先搜寻(Width-FirstSearch,WFS)算法,又称为Breadth-FirstSearch算法,会先将树中同一层的所有节点全部拜访(或检查)过之后,才拜访(或检查)下一层的节点。Q可以使用队列(queue)来实作。10广度优先搜寻算法(续)Algorithm广度优先搜寻算法Input:起始状态(或起始节点)与目标状态(或目标节点)Output:目标状态(或目标节点)对应的解答1:设定起始节点为解答空间树的根节点,标示根节点,并建立一个只包含启始节点的队列(queue)。2:拜访并检查队列的第一个元素(节点)是否为目标节点(goalnode)。若是,则输出目标节点所对应的解答并停止。3:移除队列中的第一个节点。若此节点可以扩展(expand)出未标示过的子节点,则标示这些节点,并将其加入队列的尾端。4:若队列为空,则回报无解答并停止。否则,跳至步骤2继续执行。11使用广度优先搜寻算法解决8-拼图问题121.3深度优先搜寻算法深度优先搜寻算法DFS深度优先搜寻(Depth-FirstSearch,DFS)算法总是先拜访最深的节点(deepestnode)。S可以使用堆栈(stack)来实作.14深度优先搜寻算法(续)Algorithm深度优先搜寻算法Input:起始状态(或起始节点)与目标状态(或目标节点)Output:目标状态(或目标节点)对应的解答1:设定起始节点为解答空间树的根节点,标示根节点,并建立一个只包含启始节点的堆栈(stack)。2:拜访并检查堆栈顶端的元素(节点)是否为目标节点(goalnode)。若是,则输出目标节点所对应的解答并停止。3:移除堆栈顶端的节点。若此节点可以扩展(expand)出未标示过的子节点,则标示这些节点,并将其一一加入堆栈的顶端。4:若堆栈为空,则回报无解答并停止。否则,跳至步骤2继续执行。15使用深度优先搜寻算法解决8-拼图问题16使用深度优先搜寻算法解决8-拼图问题(续)171.4登山搜寻算法登山搜寻算法登山搜寻(hill-climbingsearch)算法为深度优先搜寻算法的变形利用堆栈(stack)并配合评估函数(evaluationfunction)计算节点对应的优先级或到达目标节点的预估成本,以便优先拜访子节点中最佳的节点。不同的问题需要制定不同的评估函数19登山搜寻算法(续)以8-拼图问题为例说明如何制定评估函数:8-拼图问题之评估函数定义:填入的数字与目标状态所指定数字不同的单格总数。范例:评估函数值为2评估函数值为420登山搜寻算法(续)Algorithm登山搜寻算法Input:起始状态(或起始节点)与目标状态(或目标节点)Output:目标状态(或目标节点)对应的解答1:设定起始节点为解答空间树的根节点,标示根节点,并建立一个只包含启始节点的堆栈(stack)。2:拜访并检查堆栈顶端的元素(节点)是否为目标节点(goalnode)。若是,则输出目标节点所对应的解答并停止。3:移除堆栈顶端的节点。若此节点可以扩展(expand)出未标示过的子节点,则标示这些节点,并根据由评估函数所计算的优先级将其一一加入堆栈的顶端,优先级低的先加入。4:若堆栈为空,则回报无解答并停止。否则,跳至步骤2继续执行。21使用登山搜寻算法解决8-拼图问题221.5最佳优先搜寻算法最佳优先搜寻算法最佳优先搜寻(Best-FristSearch,BFS)算法结合深度优先搜寻算法与广度优先搜寻算法。从所有已被扩展出的节点中选出评估函数(evaluationfunction)估计为优先级最高的节点进行拜访。相对于仅具有区域(也就是仅限于某分支)最佳观点的登山搜寻算法,最佳优先搜寻算法具有全域最佳的观点。可以使用堆积(heap)或优先队列(priorityqueue)来实作。24最佳优先搜寻算法(续)Algorithm最佳优先搜寻算法Input:起始状态(或起始节点)与目标状态(或目标节点)Output:目标状态(或目标节点)对应的解答1:设定起始节点为解答空间树的根节点,标示根节点,并建立一个只包含启始节点一个元素的优先队列(priorityqueue)。2:拜访并检查优先队列中优先级最高的元素(节点)是否为目标节点(goalnode)。若是,则输出目标节点所对应的解答并停止。3:移除优先队列中优先级最高的节点。若此节点可以扩展(expand)出未标示过的子节点,则标示这些节点,并根据由评估函数所计算的优先级将其一一加入优先队列中。4:若优先队列为空,则回报无解答并停止。否则,跳至步骤2继续执行。25使用最佳优先搜寻算法解决8-拼图问题26使用最佳优先搜寻算法解决8-拼图问题(续)27适合用树搜寻算法解决的问题1(n2-1)-拼图问题2子集合加总问题3汉米尔顿回路问题4延伸:旅行销售员问题5比较:欧拉回路问题281.6子集合加总问题子集合加总问题定义子集合加总(sumofsubset)问题定义:給定一個整數集合S和一个整数m,问是否存在S的非空子集合T,使得子集合T中的整数总和为m。范例給定一個整數集合S={6,5,1,3,8},回答是否存在S的非空子集合T,使得子集合T中的整数总和为10。30使用深度优先搜寻算法解决子集合加总问题子集合加总问题:给定一个整数集合S={6,5,1,3,8},回答是否存在S的非空子集合T,使得子集合T中的整数总和为10。右方为使用深度优先搜寻算法解答上述子集合加总问题的解答空间树311.7汉米尔顿回路问题汉米尔顿威廉‧汉米尔顿爵士(SirWilliamRowanHamilton)(1805年8月4日–1865年9月2日)爱尔兰物理学家、天文学家、数学家。重新表述了牛顿力学,他的研究成果对量子力学的发展具有一定的影响。1859年,汉米尔顿发明一种环游世界的游戏,他将正十二面体的二十个顶点分别标上伦敦、巴黎、北京、东京、华盛顿等二十个大都市的名称,要求玩者从某个城市出发,沿着正十二面体的稜边通过每一个城市恰好一次,最后回到出发的城市。这延伸出汉米尔顿回路或汉米尔顿旅途问题。Source:/wiki/File:William_Rowan_Hamilton_portrait_oval_combined.png33正十二面体与汉米尔顿回路正十二面体正十二面体对应的平面图(graph)及其中的汉米尔顿回路汉米尔顿Source:/wiki/File:POV-Ray-Dodecahedron.svgAttribution:DTRCreativeCommonsAttribution-ShareAlike3.0UnportedSource:/wiki/File:Hamiltonian_path.svgAuthor:ChristophSommerCreativeCommonsAttribution-ShareAlike3.0Unported34汉米尔顿回路一个无向图(undirectedgraph)上的汉米尔顿回路(Hamiltoniancircuit)又称为汉米尔顿循环(Hamiltoniancycle)或汉米尔顿旅途(Hamiltoniantour),是一条由某个起始节点出发,经过每个节点恰好一次,且最后会回到起始节点的路径(path)。一个包含汉米尔顿回路的无向图称为汉米尔顿图(Hamiltoniangraph)。范例:以下无向图为汉米尔顿图,因为此图中具有汉米尔顿回路35汉米尔顿回路问题定义汉米尔顿回路(Hamiltoniancircuit)问题定义:决定一个无向图之中是否存在汉米尔顿回路的问题,称为汉米尔顿回路问题(Hamiltoniancircuitproblem)。这是是一个NPC问题,也就是非确定性多项式时间完全问题(non-deterministicpolynomialcompleteproblem,NP-completeproblem,NPCproblem)。我们在稍后的单元中再详细介绍NPC问题。36汉米尔顿回路问题范例给定的无向图解答左方给定的无向图是否存在汉米尔顿回路的解答空间树37汉米尔顿回路问题范例(续)给定的无向图以广度优先算法解答左方给定的无向图是否存在汉米尔顿回路的解答空间树38汉米尔顿回路问题范例(续)给定的无向图以深度优先算法解答左方给定的无向图是否存在汉米尔顿回路的解答空间树39延伸:旅行销售员问题TSP旅行销售员问题(TravelingSalespersonProblem,TSP):给定一个加权无向图,求出其中边加权总合最小或长度最短的汉米尔顿回路(Hamiltoniancircuitoftheminimumlength)。TSP是一个是一个NP-hard问题,也就是非确定性多项式时间困难问题(non-deterministicpolynomialhardproblem,NP-hardproblem)。我们在稍后的单元中再详细介绍NP-hard问题。40比较:欧拉回路问题欧拉路径(Eulerianpath)或欧拉链(Eulerianchain):无向图上的一条路径,经过每个边恰好一次。欧拉回路(Euleriancircuit):一个无向图上经过每个边恰好一次的回路。欧拉路径问题:找出无向图上欧拉路径的问题,是一个P问题,也就是多项式时间(polynomialproblem)问题。欧拉回路问题:找出无向图上欧拉回路的问题,是一个P问题。我们在稍后的单元中再介绍P问题。41欧拉李昂哈德·欧拉(LeonhardEuler,1707年4月15日-1783年9月18日)是一位瑞士数学家和物理学家。1736:解决柯尼斯堡七桥问题(一笔画问题),是最早运用图论(graphtheory)和拓扑学(topology)的典范。(FE+V=2)欧拉函数(n):小于n并且与n互质的自然数的个数。(与RSA公钥密码算法有关)欧拉公式:欧拉恒等式:欧拉-马歇罗尼常数Source:File:Leonhard_Euler.jpg42相关:柯尼斯堡七桥问题1735年时东普鲁士柯尼斯堡(今日俄罗斯加里宁格勒)市区跨越河的两岸,河中心有两个小岛,小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下,如何才能把这个地方所有的桥都走遍?Source:/wiki/File:Konigsberg_bridges.pngAuthor:BogdanGiuşcăCreativeCommonsAttribution-ShareAlike3.0UnportedSource:/wiki/File:7_bridges.svgSource:/wiki/File:K%C3%B6nigsberg_graph.svg43相关:一笔画问题如何能笔尖不离纸,一笔(不经过重复线段)画出给定的图形?范例:Source:File:Chuan2.JPGSource:File:K%C3%B6nigsberg_graph.svg441.8回溯算法回溯算法回溯(backtracking)算法与深度优先搜寻算法概念类似,但稍有不同:深度优先搜寻算法在解空间树上搭配使用堆栈以搜寻可行解。在找到可行解之前会以深度优先的方式遍访每一个未拜访过的节点,直到某一分支已经没有未拜访问过的节点,才退回该分支的父节点(分岔点),同样以深度优先的方式遍访其他分支的节点。回溯算法虽然在逻辑上隐含地用到解空间树,但是在思维上不一定提及解空间树,有时会以递回的方式来实现,以一个个的选择(choice)来找出可行解。在进行选择的时候,可以先选择较可能有好结果的部份(与hillclimbing概念类似),或是提早判断死端(deadend)(也就是确定不会产生可行解的状态)的出现以提早进行回溯退回先前的选择分岔点。46回溯算法范例:八后問題八后问题(eightqueenproblem):如何在一个8×8的西洋棋棋盘(checkboard)上放置8个不会互相攻击的皇后棋子。皇后棋子可以从上、下、左、右、左上、左下、右上、右下等八个方向攻击对方的棋子。因此,一个皇后棋子延伸出去的上、下、左、右、左上、左下、右上、右下的八个方向上都不能有其他皇后棋子。由数学家FranzNauck于1850年提出,大数学家高斯(Gauss)曾猜测此问题共有96个解,但后来经过证明,实际上只有92个形式解,而本质解(即去掉由某一个解经旋转或反射后得到的解)只有12个。47回溯算法范例:八后問題(续)123Backtracking4XXXXXXXXX48回溯算法范例:八后問題(续)一个4×4的西洋棋棋盘(checkboard)4个不会互相攻击皇后棋子的位置:49回溯算法范例:八后問題(续)AlgorithmPutQueen(i,n)Input:整数i、整数n//i(0≤i≤n-1)表示目前正放置编号为i(第i+1个)的皇后棋子Output:n个皇后棋子在n×n棋盘上不互相攻击之位置//编号为i的皇后棋子必定在第i列,因此我们只使用一维阵列q来记录皇后棋子位置0.globalqj←0//j代表行(column)编号,0≤j≤n-1whilej<ndoifi列j行可放置皇后棋子thenq[i]←j//编号为i的皇后放在第i列第j行上ifi=n-1then

//n个皇后棋子均已放置妥当打印n个皇后棋子位置//未继续递回呼叫elsePutQueen(i+1,n)//递回呼叫(recursivecall),类似DFS//此处代表印出后或递回呼叫后已return回来之处,以下执行j+1相当于在第i列进行回溯j←j+1//寻找下一个可能放置编号为i的皇后棋子的行位置return

//此处j已大于等于n,表示第i列已无适当位置可选,return则相当于回溯到第i-1列或结束(当i=0时)呼叫PutQueen(0,8)即可解出八后问题50Python#Programtosolvethen-Queenproblemn=8;q=[0]*n;sol_count=0def

ok(i,j):globalqforkinrange(i):ifq[k]==jorabs(q[k]-j)==abs(k-i):return

Falsereturn

Truedef

put_queen(i,n):globalq,sol_countj=0whilej<n:ifok(i,j):q[i]=j#q[i]=j表示第i列的皇后放在第j行ifi==n-1:sol_count+=1print(f"Solution{sol_count}:{q}")else:p

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论