MinExpectTimes.cpp

#define ALGORITHMLIB __declspec(dllexport)
#include "..\..\DataStruct\Array\DynArray.h"
#include "MinExpectTimes.h"

double CalculateMinExpectTimes(
	const double* pArr_,
	int nS_,
	int nE_)
{
	// 问题：
	// 给定 k1,k2,...,kn个数值
	// 满足k1< k2 < ... < kn
	// 给定
	// d0 代表所有小于 k1的数值
	// dn 代表所有大于kn的数值
	// di 代表所有大于ki且小于k(i+1)的数值
	// 已经知道
	// 一次搜索输入中，输入值为
	// ki的概率为pi
	// di的概率为qi

	// 问，我们该如何组织k1,k2,...,kn这n个元素所构成的二叉搜索树
	// 来达到一次给定输入下预期搜索中节点比较次数最少的效果。

	// 问题初步分析：
	// 1. 给定n个有序元素k1 < k2 < ... < kn
	// 若将该n个元素用二叉搜索树存储，则，对应的二叉搜索树具有多种可能
	// 2. 搜索中对于不在二叉搜索树元素集合中的元素，我们总是在比较到了二叉搜索树的叶子节点后，
	// 才能确定该元素不存在，此时的比较次数我们可以记为 比较到对应叶子节点的比较次数 + 1
	// 3. 对于二叉搜索树中存在的元素，一次搜索需要比较的次数，等于二叉搜索树中此元素的树高。
	// 我们规定根节点树高为1
	// 孩子节点树高 = 父亲节点树高 + 1

	// 对于要求解的问题
	// 我们的输入是
	// n个概率值，代表的是 我们有序集合n个元素每个元素在一次搜索中出现的频率
	// n+1个概率值，代表的是 不在我们有序集合n个元素的n+1个可能区间中一次搜索时的概率

	// 确立一棵二叉树首先要确立根节点
	// 对于一棵给定的二叉树，期望是已知的
	// 树的期望 = 所有树中非叶子节点树高 * 该节点对应概率 + 所有非树中节点【叶子节点】树高 * 该节点对应概率
	// = 左子树所有节点树高 * 该节点对应概率 + 右子树所有节点树高 * 该节点对应概率 + 根节点树高 * 根节点概率
	// = 左子树的期望 + 左子树所有节点概率 + 右子树期望 + 右子树所有节点概率 + 根节点树高 * 根节点概率
	// = 左子树的期望 + 右子树的期望 + 树中所有节点概率

	// 假设对于给定一棵树是最优二叉树，即该树下执行一次搜索预期比较次数最少
	// 可以证明该树的左子树，右子树也是最优二叉树
	// 我们对树分析，其根节点可能为k1,...,kn中任意一个
	// 我们有
	// 最优二叉树 = 
	// {
	//		根节点为k1 + 左最优二叉树 + 右最优二叉树,
	//		...
	//		根节点为kn + 左最优二叉树 + 右最优二叉树,
	//	}
	int _nSize = nE_ - nS_;
	if (_nSize == 1)
	{
		return *(pArr_ + nS_);
	}

	if (_nSize == 0)
	{
		return 0.0;
	}
	
	if (_nSize % 2 == 0)
	{
		throw "Input error";
	}

	double _nSum = 0.0;
	for (int _i = 0; _i < _nSize; _i++)
	{
		_nSum += *(pArr_ + _i + nS_);
	}

	double _nMinExpect = _nSum
		+ CalculateMinExpectTimes(pArr_, nS_, nS_ + 1)
		+ CalculateMinExpectTimes(pArr_, nS_ + 2, nE_);
	for (int _i = 3; _i < _nSize; _i = _i + 2)
	{
		double _nExpect = _nSum
			+ CalculateMinExpectTimes(pArr_, nS_, nS_ + _i)
			+ CalculateMinExpectTimes(pArr_, nS_ + _i + 1, nE_);
		if (_nExpect < _nMinExpect)
		{
			_nMinExpect = _nExpect;
		}
	}

	return _nMinExpect;
}

// 算法输入：
// 一个数组起始地址
// 一个区间【首元素位置，尾后元素位置】

// 区间内元素为我们要求解的构成最优二叉树的叶子节点，非叶子节点元素及其被搜索到的概率
// 返回值：
// 区间内元素按最优二叉树组织下，一次搜索预期比较次数

// 算法正确性证明：
// 分治采用数学归纳法证明
// 即预先假定算法正确

// 规模足够小时，
// 即树中节点和非节点元素个数小于等于1，二叉树唯一，立即求解。得到唯一解，同时也是最优解。

// 规模为 nS_, nE_时，
// 依据数学归纳法，所有比此规模更小的规模，算法均可正确求解。
// 对规模 nS_, nE_
// 当我们选定此规模下根节点时，
// 便将规模 nS_, nE_划分为两个更小的规模
// 算法在两个较小规模下，可以正确求解。
// 且规模 nS_, nE_和两个较小规模存在以下关系
// 规模 nS_, nE_的解 = 两个较小规模解的和 + nS_到nE_所有概率之和

// 对规模 nS_, nE_的所有可能根节点划分
// 我们依次求取每种划分下的最优解，
// 从所有划分中，选取最优解最优的。
// 则，我们将得到 nS_, nE_规模下，最优的解。
// 综合，我们的算法对于任何给定的规模，总是可以求出该规模下的最优解。