首页 > Python资料 博客日记
最优二叉搜索树 C#实现
2024-03-07 10:00:05Python资料围观108次
最优二叉搜索树 C#实现
介绍一下
上一篇博文搞半天挺烧脑,没搞清楚继续… 主要是练习动态规划算法。最关键的一个是这个最优二叉搜索树能干啥。我认为如果数据稳定,统计出概率来,用最优二叉树保存,以后搜索应该是效率比较高的。还有一个是通过一通研究这个算法,折磨半天自己,加深理解,动态规划是真的难。
dp表项 一个是概率之和的理解,一个是dp状态转义表的理解。
概率之和递推公式
if (j < i)//看条件判定 没有任何数值的树概率就是间隙的概率
dp[i, j].weight = probs[2 * j];
else//递推 数值之前的概率 + 数值概率 + 数值和之后的间隙概率
dp[i, j].weight = dp[i, j - 1].weight + probs[2 * j - 1] + probs[2 * j];
状态转移递推公式
//赋值一个比较大的数字,可以知道,搜索长度最大不会超过数组长度
dp[h, l].path = datas.Count;
for (int k = h; k <= l; k++)
{
//通过getpath函数兼容索引后面小于前面的情况,节省空间。
float path = GetPath(h, k - 1, dp) + GetPath(k + 1, l, dp) + dp[h, l].weight;
if (dp[h, l].path > path)
{
//冒泡比较 记录最小搜索路长和树的根,以便于创建树
dp[h, l].path = path;
dp[h, l].root = k;
}
}
根据转移表递归创建搜索树
主要是CreateBSTNode函数
开始大于结束直接返回空,没有树结点
开始等于结束返回单一结点
开始小于结束,进入递归
程序数据和结果
List<int> lst = new List<int> { 10, 20, 30, 40, 50, 60 };
//间隙 数值 间隙 数值 ... 间隙
List<float> fls = new List<float> { 0.05f, 0.05f, 0.1f, 0.1f, 0.05f, 0.05f, 0.05f, 0.1f, 0.05f, 0.2f, 0.1f,0.01f,0.09f };
//创建最优二叉搜索树,准备绘制
bTree = BSTree.CreateOPSTree(lst, fls);
程序核心代码
dp表项
public struct Item
{
//概率之和[权重]
public float weight;
//最短平均路长[状态转移表]
public float path;
//根节点
public int root;
}
构建搜索树代码
private static float GetPath(int h, int l, Item[,] items)
{
if (h > l)
{
return 0.0f;
}
else
{
return items[h, l].path;
}
}
/// <summary>
/// 根据dp转移表构建树
/// </summary>
/// <param name="h">开始</param>
/// <param name="l">结束</param>
/// <param name="dps">转移表</param>
/// <param name="datas">树结点数据</param>
/// <returns></returns>
private static BSTree CreateBSTNode(int h, int l, Item[,] dps, List<int> datas)
{
//开始大于结束
if (h > l)
{
return null;
}
//开始等于结束
if (h == l)
{
return new BSTree(datas[dps[h,l].root - 1]);
}
else//开始小于结束 进入递归
{
BSTree bSTree = new BSTree(datas[dps[h, l].root - 1]);
bSTree.lChild = CreateBSTNode(h, dps[h,l].root-1,dps, datas);
bSTree.rChild = CreateBSTNode(dps[h, l].root + 1, l, dps, datas);
return bSTree;
}
}
public static BSTree CreateOPSTree(List<int> datas, List<float> probs)
{
Item[,] dp = new Item[datas.Count + 1, datas.Count + 1];
//赋值概率
for (int i = 1; i <= datas.Count; i++)
{
for (int j = i - 1; j <= datas.Count; j++)
{
if (j < i)
dp[i, j].weight = probs[2 * j];
else
dp[i, j].weight = dp[i, j - 1].weight + probs[2 * j - 1] + probs[2 * j];
}
}
//赋值dp转移表
for (int len = 1; len <= datas.Count; len++)
{
for (int h = 1, l= len; h <= datas.Count && l<= datas.Count; h++, l++)
{
dp[h, l].path = datas.Count;
for (int k = h; k <= l; k++)
{
float path = GetPath(h, k - 1, dp) + GetPath(k + 1, l, dp) + dp[h, l].weight;
if (dp[h, l].path > path)
{
dp[h, l].path = path;
dp[h, l].root = k;
}
}
}
}
return CreateBSTNode(1, datas.Count, dp,datas);
}
参考
B站张老师视频
虽然写完了,如果不参考代码,其实只有思路,还是撸不出来的…
标签:
相关文章
最新发布
- 【Python系列】SQLAlchemy 基本介绍
- 【Python】selenium 的EC.presence_of_element_located 和 EC.element_to_be_clickable 的区别
- 从零到一!超详细Pycharm安装教程(图解+详细步骤)
- python json jsonl 的用法
- 【Python篇】深度探索NumPy(下篇):从科学计算到机器学习的高效实战技巧
- boto3:Python连接S3对象存储并进行文件操作(上传、下载、删除)
- 全网最适合入门的面向对象编程教程:50 Python函数方法与接口-接口和抽象基类
- Python pycryptodome类库使用学习总结
- import torch 报错:WinError 126
- 如何在Java中实现邮件发送功能?
点击排行
- 版本匹配指南:Numpy版本和Python版本的对应关系
- Python 可视化 web 神器:streamlit、Gradio、dash、nicegui;低代码 Python Web 框架:PyWebIO
- 版本匹配指南:PyTorch版本、torchvision 版本和Python版本的对应关系
- 相关性分析——Pearson相关系数+热力图(附data和Python完整代码)
- Could not build wheels for llama-cpp-python, which is required to install pyproject.toml-based proj
- Python pyinstaller打包exe最完整教程
- Anaconda版本和Python版本对应关系(持续更新...)
- Python与PyTorch的版本对应