Tree Structure是一个数据结构,也是一个计算结构。

树结构是计算机科学与技术领域最重要的结构!甚至在更广泛的领域也是最重要的结构。

 
 


 
 


 
 


 
 

Hamilton circuit problem 哈密顿回路问题

 
 




 
 

 
 


 
 

广度优先搜索


广度优先搜索的基本数据结构是一个能容纳所有扩展结点的队列

 
 

8数码问题

 
 


 
 


 
 

深度优先搜索(depth first search)

总是选择最深的结点展开。

已知集合S={7,5,1,2,10},确定是否存在元素和等于9的子集S`

深度优先搜索,可以将搜索结点压栈,回溯时出stack


 
 

 
 

爬山法


 
 


 
 

Hill climbing不是很有效,因为爬山法找的仅仅是局部最优解,如果最优解离得比较远,那么爬山法就找不到最优解。

为了解决这个问题,可以用退火算法,也可以用下面介绍的最佳优先搜索策略。


 
 

上面的八数码问题,如果选第2分支,那么可以得到更好的解。

局部最优解不是全局最优解


 
 

 
 

最佳优先搜索策略 Best-First search strategy

 
 



 
 


 
 

启发函数结果是:4 4 5 5

选择一个最小的 4 深度扩展:5 6 4 5 5

选择最小的 4 深度扩展:5 6 4 6 5 5

再选择最小的 4 深度扩展:5 6 4 6 5 5

再选择最小的4深度扩展,就得到了最终结果

 
 


 
 

分支界限策略(Branch and bound strategy)

 
 


 
 

首先选择用爬山法找出一个解,那么这个解就是上界,最优解一定小于或 这个上界,对其他分支就可以根据求得的解来剪枝

 
 


a扩展后又三个结点,b、c、d,a到b的代价最小,选择b,然后扩展b,发现b到f的代价最小,选择f,f扩展后得到目标值,

那么爬山法得到的一个解就是1+3+1=5,该问题的上届是5,大于5就可以剪枝

 
 

branch and bound strategy可以避免穷举搜索这个解空间。

这个策略由两个重要机制组成,一个机制是产生分支,另一个机制是产生一个界限以至于能终止许多分支

分支界限策略在平均情况下是有效的,但是在最坏情况下仍会产生一颗非常大的树。

最坏情况:与穷举法相同

平均情况:比穷举法好,常用平均性来度量

 
 

 
 

 
 

分支界限策略解决人员分配问题

用branch and bound 方法求解上界

 
 

分支界限策略解决旅行商优化问题


 
 

分支界限策略解决0/1背包问题


 
 


 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 




0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注