动态规划练习题-最优二分查找树

2019-09-12 admin

问题描述: 最优二叉查找树: 给定n个互异的关键字组成的序列K=<k1,k2,…,kn>,且关键字有序(k1<k2<…<kn),我们想从这些关键字中构造一棵二叉查找树。对每个关键字ki,一次搜索搜索到的概率为pi。可能有一些搜索的值不在K内,因此还有n+1个“虚拟键”d0,d1,…,dn,他们代表不在K内的值。具体:d0代表所有小于k1的值,dn代表所有大于kn的值。而对于i = 1,2,…,n-1,虚拟键di代表所有位于ki和ki+1之间的值。对于每个虚拟键,一次搜索对应于di的概率为qi。要使得查找一个节点的期望代价(代价可以定义为:比如从根节点到目标节点的路径上节点数目)最小,就需要建立一棵最优二叉查找树。 举例说明: n=5的关键字集合以及如下的搜索概率,构造二叉搜索树。 clipboard.png

clipboard.png

期望搜索代价的计算公式: clipboard.png 下图中图a显示了给定上面的概率分布pi、qi,生成的两个二叉查找树的例子。图b就是在这种情况下一棵最优二叉查找树。

clipboard.png

输入: p序列:表示对每个关键字ki,一次搜索搜索到的概率为pi; q序列:表示对每个虚拟键di,一次搜索搜索到的概率为qi。

输出: 关键字和虚拟键的中序遍历结果

思路:

1 拆分子问题

2 计算

3 代码

4 时间复杂度

[转载]原文链接:https://segmentfault.com/a/1190000020375034

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-74993.html

文章标题:动态规划练习题-最优二分查找树

相关文章
jquery实现动态改变div宽度和高度
完整代码: &lt;!DOCTYPE html PUBLIC &quot;-&#x2F;&#x2F;W3C&#x2F;&#x2F;DTD XHTML 1.0 Transitional&#x2F;&#x2F;EN&quot; &quot;ht...
2017-03-23
Bootstrap jquery.twbsPagination.js动态页码分页实例代码
Bootstrap风格的分页控件自适应的: 参考网址:分页参考文档 1.风格样式: 2.首先引入js文件jQuery.twbsPagination.js &lt;span style=&quot;font-size:14px;&quot;...
2017-03-16
JavaScript动态添加style节点的方法
本文实例讲述了JavaScript动态添加style节点的方法。分享给大家供大家参考。具体如下: var css = &#x27;h1 { background: red; }&#x27;, head = document.getEleme...
2017-03-24
JS使用ajax从xml文件动态获取数据显示的方法
本文实例讲述了JS使用ajax从xml文件动态获取数据显示的方法。分享给大家供大家参考。具体分析如下: 下面的JS代码通过ajax检索xml文件的内容动态展示到网页,真个页面无刷新 &lt;!DOCTYPE html&gt; &lt;htm...
2017-03-21
javascript动态创建链接的方法
本文实例讲述了javascript动态创建链接的方法。分享给大家供大家参考。具体分析如下: 动态创建链接示例: &lt;html xmlns=&quot;http:&#x2F;&#x2F;www.w3.org&#x2F;1999&#x2F;...
2017-03-23
利用js查找数组中指定元素并返回该元素的所有索引示例
前言 这篇文章主要给大家介绍的是利用js查找数组中指定元素并返回该元素的所有索引的相关资料,文中给出了详细的示例代码,下面话不多说,来看看详细的代码示例吧。 示例代码 &#x2F;&#x2F;在数组中查找所有出现的x,并返回一个包含匹配索引...
2017-04-01
javascript实现动态导入js与css等静态资源文件的方法
本文实例讲述了javascript实现动态导入js与css等静态资源文件的方法。分享给大家供大家参考。具体实现方法如下: &#x2F;** * 动态导入静态资源文件js&#x2F;css *&#x2F; var $import = fu...
2017-03-27
javascript实现Table间隔色以及选择高亮(和动态切换数据)的方法
本文实例讲述了javascript实现Table间隔色以及选择高亮(和动态切换数据)的方法。分享给大家供大家参考。具体实现方法如下: &lt;!DOCTYPE html PUBLIC &quot;-&#x2F;&#x2F;W3C&#x2F;...
2017-03-23
vue 解决addRoutes动态添加路由后,刷新失效问题
你是电,你是光,你是最美的太阳🌞 前言 某些场景下我们需要利用addRoutes动态添加路由,但是刷新后就会失效,前段时间项目里刚好遇到了这个应用场景,所以就花时间研究了一下,做下分享跟记录,说的不对的地方,请大家指正。 **应用场...
2018-06-30
javascript实现dom动态创建省市纵向列表菜单的方法
本文实例讲述了javascript实现dom动态创建省市纵向列表菜单的方法。分享给大家供大家参考。具体实现方法如下: &lt;!DOCTYPE html PUBLIC &quot;-&#x2F;&#x2F;W3C&#x2F;&#x2F;DT...
2017-03-23
回到顶部