• 欢迎加“百元导航”为主页,windows8风格,0.3s极速加载
  • 王柏元的博客专用搜索引擎:极客人,就用“极客搜”!
  •    1年前 (2015-12-06)  算法语言 |   抢沙发  60 
    文章评分 1 次,平均分 5.0

    回溯法通过深度优先遍历的策略遍历解空间树,其实现过程是:从根节点出发搜索它的所有孩子树或者孩子结点,对于每个结点判断其是否满足约束条件和判定函数,如果满足则进入此结点同样以此结点搜索它的子结点。拥有子节点的结点称之为活节点,当搜索至到没有活节点时则返回原父节点继续寻找活节点,以此类推,直到回溯算法搜索完解空间树。

    回溯法由于是遍历完解决问题的所有可能解,所以称它是解决问题的万能算法,只要正确构建了解空间树,通过回溯遍历解空间树即可。回溯算法可以解出解决问题的所有可能解,而在实际解决一些最优解问题时我们可以通过剪枝函数剪掉比中间结果比已求得最优解还差的子树。

    无向图的m着色问题的m的最小值求解

     

     

     

    除特别注明外,本站所有文章均为王柏元的博客原创,为了尊重作者的劳动成果,转载请注明出处http://wangbaiyuan.cn/backtracking-method-undirected-graph-node-color-color-number-at-least.html,如果你觉得这篇文章对你有用,可以点击文章下面的“赞助作者”打赏作者!

    关于
    记录生活,镌刻心路;泼洒文墨,分享技术!王柏元的博客致力于IT经验交流,并原创翻译引进外文文章,打开IT国际化视野

    发表评论

    格式

    暂无评论

    登录

    忘记密码 ?

    您也可以使用第三方帐号快捷登录

    切换登录

    注册