算法设计 动态规划 最优二叉搜索树

Sekiro

C/C++算法设计

发布于：2021年1月4日

次浏览

字数：293字

时长：1分钟

0  

本文是算法设计基于动规算法的问题“最优二叉搜索树”的实现。

一、问题

最优二叉搜索树问题：

给定一个n个不同关键字已排序的序列 ：

K=<k1,k2,…,kn> (k1<k2<…<kn)，

我们希望用这些关键字构造一棵二叉搜索树。对每个关键字ki，都有一个概率bi表示其搜索频率。有些要搜索的值可能不在K中，因此我们还有n+1个“伪关键字”d0,d1,d2…dn表示不在K中的值。d0表示所有小于k1的值， dn 表示所有大于kn的值，对i=1,2,…,n−1，伪关键字di表示所有在ki和ki+1之间的值。对每个伪关键字di，也都有一个概率ai表示对应的搜索频率。

二、环境

电脑硬件配置：

• 处理器：Intel i7 7700HQ

• 显卡：NVIDIA GeForce GTX 1050 Ti

• 内存：16GB

软件：

• 编程语言：C++

• IDE：Microsoft Visual Studio 2019

• Windows SDK版本：10.0

• 平台工具集：Visual Studio 2019（v142）

三、项目地址

本项目的源码、可执行程序均已经存放于我的Github，欢迎下载查看：

相关文章

算法设计 分治 最接近点对本文是算法设计基于分治算法的问题“最接近点对”的实现。C++工程项目 JobShop本文是计算机导论的程序设计实战项目，实现单词消除游戏，具体项目及要求请点击查看。C++工程项目 travel本文是数据结构课程设计项目，实现类似“携程”旅行模拟，具体项目及要求请点击查看。C++工程项目 单词消除游戏本文是C++面向对象的程序设计实战项目，实现单词消除游戏，具体项目及要求请点击查看。

本文为博主「Sekiro」的原创文章

内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://666wxy666.github.io/2021/01/04/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-%E6%9C%80%E4%BC%98%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/

更新于：2023年1月14日

C++

算法设计

动态规划