从根基点出发探索解空间树

从根基点出发探索解空间树

在所有解决问题的解算室树中，根据深度优先搜索战略，深入挖掘解决方案的结构树。若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。贪心法它适用于解一些组合数较大的问题。根据当前已有的信息就做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。换言之,贪心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。1绘画中的问题分类1.1主导快速搜索回溯法是一种系统地搜索问题解的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。用回溯法解题的一般步骤:(1)描述解的形式,定义一个解空间,它包含问题的所有解。(2)构造状态空间树。(3)构造约束函数(用于杀死节点)。1.2整体最优解的选择贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对一些问题它能产生整体最优解或者是整体最优解的近似解。贪心算法没有固定的算法框架,算法设计的关键是贪婪策略的选择。一定要注意,选择的贪婪策略要具有无后向性,即某阶段状态一旦确定以后,不受这个状态以后的策略影响,也就是说某个状态以后的过程不会影响以前的状态,只与当前状态有关,也称为这种特性为无后效性。因此,适应用贪婪策略解决的问题类型较少,对所采用的贪婪策略一定要仔细分析其是否满足无后效性。图的着色问题是由地图的着色问题引申而来的:用m种颜色为地图着色,使得地图上的每一个区域着一种颜色,且相邻区域颜色不同。2处理问题如果把每一个区域收缩为一个顶点,把相邻两个区域用一条边相连接,就可以把一个区域图抽象为一个平面图。2.1主导点的提取回溯法有“通用解题法”之称,是一种比穷举“聪明”的搜索技术,在搜索过程中动态地产生问题的解空间,系统地搜索问题的所有解。当搜索到解空间树的任一结点时,判断该结点是否包含问题的解。如果该结点肯定不包含,则“见壁回头”,跳过以该结点为根的子树的搜索,逐层向其祖先结点回溯,可大大缩减无效操作,提高搜索效率。因此,结合具体案例的实际设计合适的回溯点是应用回溯法的关键所在。值得注意的是,递归具有回溯的功能,很多问题应用递归回溯可探索出问题的所有解。2.2较明显的同位分配算法贪心算法的思想是首先用第一种颜色对图中尽可能多的顶点着色,然后用第二种颜色对余下的顶点中尽可能多的顶点着色;如此等等,直到把所有的顶点都着完色。当用一种新颜色对余下的顶点着色时,我们采取下列步骤:(1)选取某个未着色的顶点,并且用新颜色对它着色。(2)扫描所有未着色的顶点集,对其中的每个顶点,确定它是否与已着新颜色的任何顶点相邻。若不相邻,则用新颜色对它着色。首先把所有顶点的颜色初始化为0,然后依次为每个顶点着色。如果其中i个顶点已经着色,并且相邻两个顶点的颜色都不一样,就称当前的着色是有效的局部着色;否则,就称为无效的着色。如果由根节点到当前节点路径上的着色,对应于一个有效着色,并且路径的长度小于n,那么相应的着色是有效的局部着色。这时,就从当前节点出发,继续探索它的儿子节点,并把儿子结点标记为当前结点。在另一方面,如果在相应路径上搜索不到有效的着色,就把当前结点标记为死结点,并把控制转移去搜索对应于另一种颜色的兄弟结点。如果对所有m个兄弟结点,都搜索不到一种有效的着色,就回溯到它的父亲结点,并把父亲结点标记为死结点,转移去搜索父亲结点的兄弟结点。这种搜索过程一直进行,直到根结点变为死结点,或者搜索路径长度等于n,并找到了一个有效的着色为止。图的m色优化问题:给定无向连通图G,为图G的各顶点着色,使图中任2邻接点着不同颜色,问最少需要几种颜色。所需的最少颜色的数目m称为该图的色数。4chpowell法在一个平面或球面上的任何地图能够只用4种颜色来着色使得相邻的国家在地图上着有不同颜色,任意图的着色,采用的是WelchPowell法。这次实验主要解决了一个问题,那就是图着色问题,用两种不同的方法来解决,分别用回溯法及贪心法。用回溯法求图着色的时候,固定了