考试网 >> IT认证 >> 等级 >> 等级动态 >> 常用算法设计方法3

发布时间：2006-07-25 12:02     点击：

       在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。

【问题】       组合问题

    问题描述：找出从自然数1、2、……、n中任取r个数的所有组合。

    例如n=5，r=3的所有组合为：  

（1）1、2、3              （2）1、2、4              （3）1、2、5

              （4）1、3、4              （5）1、3、5              （6）1、4、5

              （7）2、3、4              （8）2、3、5              （9）2、4、5

              （10）3、4、5

则该问题的状态空间为：

E={（x1，x2，x3）∣xi∈S ，i=1，2，3 }     其中：S={1，2，3，4，5}

约束集为：    x1<x2<x3

       显然该约束集具有完备性。

问题的状态空间树T：

⊙                ⊙           ⊙       ⊙   ⊙

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。