高级树算法
㈠ 目前比较流行的决策树算法有哪些
ID3算法，最简单的决策树
c4.5 是最经典的决策树算法，选择信息差异率最大的作为分割属性。
CART算法，适合用于回归
㈡ 图的所有生成树的算法
边构成,并包含G的所有顶点的树称为G的生成树(G连通).
加权无向图G的生成树的代价是该生成树的所有边的代码(权)的和.
最小代价生成树是其所有生成树中代价最小的生成树.
参考代码:
(仅为主程序,更多代码在
解压密码: )
#include "Sets.h"
#include "themap.h"
#include "windows.h"
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
/*
功能:
演示Kruskal算法和Prim算法
集合的并,元素查找的操作及应用
说明:
代码均在vc++6.0环境下编译均通过
在非VC++6.0环境下编译请去掉头文件 windows.h 和函数 end()
如果NULL未定义请自定义
#define NULL 0 或
#define NULL ((void*)0)
作者:
hacker
时间:
2007.2.3
*/
const VSIZE = 7;//7个顶点
const INFINITY = 10000;//10000作为无穷大来处理
void LoadData(int cost[][VSIZE+1], Edge edge[]);
void end();
/*
函数名:
Kruskal 和 Prim
参数:
边,代价,边数,顶点数,最小代价生成树的顶点
返回值:
返回值为-1,不存在最小代价生成树
返回值大于0时为最小代价生成树的代价
最小代价生成树的边在vector<Edge>& t
*/
int Kruskal(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t);
int Prim (Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t);
int main()
{
int cost[VSIZE+1][VSIZE+1];//0不用
Edge edge[9];//9条边
vector<Edge> t;//用来存储最小代价生成树的顶点
int mincost;//最小代价
LoadData(cost, edge);
if ( (mincost = Kruskal(edge, cost, 9, VSIZE, t))!=-1)
{
cout<<"最小代价是:"<<mincost<<endl<<"边是:";
for (int i = 0;i<t.size();i++)
cout<<t[i];
cout<<endl;
}
t.clear();
if ( (mincost = Prim(edge, cost, 9, VSIZE, t))!=-1)
{
cout<<"最小代价是:"<<mincost<<endl<<"边是:";
for (int i = 0;i<t.size();i++)
cout<<t[i];
cout<<endl;
}
end();
return 1;
}
void LoadData(int cost[][VSIZE+1], Edge edge[])
{
edge[0].u = 1; edge[0].v = 2; edge[0].weight = 28;
edge[1].u = 1; edge[1].v = 6; edge[1].weight = 10;
edge[2].u = 2; edge[2].v = 3; edge[2].weight = 16;
edge[3].u = 2; edge[3].v = 7; edge[3].weight = 14;
edge[4].u = 3; edge[4].v = 4; edge[4].weight = 12;
edge[5].u = 4; edge[5].v = 5; edge[5].weight = 22;
edge[6].u = 4; edge[6].v = 7; edge[6].weight = 18;
edge[7].u = 5; edge[7].v = 6; edge[7].weight = 25;
edge[8].u = 5; edge[8].v = 7; edge[8].weight = 24;
for (int i=1;i<=7;i++)
for (int j=1;j<=i;j++)
cost[i][j] = cost[j][i] = INFINITY;
for (i=0;i<9;i++)
cost[edge[i].u][edge[i].v] =
cost[edge[i].v][edge[i].u] = edge[i].weight;
}
int Kruskal(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t)
{
Sets s(esize);
priority_queue<Edge, vector<Edge>, EdgeGreater> pq;
int mincost = 0;
for (int i = 0;i<esize;i++)
//把所有的边放入优先队列
pq.push(edge[i]);
i = 0;
while (i<vsize-1 && !pq.empty())
{
Edge temp = pq.top();//取出当前权最小的边
pq.pop();
int j = s.SimpleFind(temp.u);
int k = s.SimpleFind(temp.v);
if (j!=k)//如果不构成环
{
i++;
t.push_back(temp);
mincost +=cost[temp.u][temp.v];
s.SimpleUnion(j, k);
}
}
if (i!=vsize-1)
{
t.clear();
return -1;
}
else
{
return mincost;
}
}
int Prim(Edge edge[], int cost[][VSIZE+1], int esize, int vsize, vector<Edge>& t)
{
priority_queue<Edge, vector<Edge>, EdgeGreater> pq;
vector<Edge> sortededge;
int i;
for (i =0;i<esize;i++)
pq.push(edge[i]);
for (i =0;i<esize;i++)
{//对边进行从小到大排列,放到sortededge中
sortededge.push_back(pq.top());
pq.pop();
}
int distance[VSIZE+1];
int j;
int mincost = sortededge[0].weight;
Edge temp = sortededge[0];
t.push_back(temp);
for (i=1;i<=vsize;i++)
distance[i] = 1;//每个点都不在已生成树里
distance[temp.u] = distance[temp.v] = 0;//最短的边的两个点放到生成树里
for (i=2;i<=vsize-1;i++)
{//寻找另外的边
int exist = 0;//设置是否找到符合条件的边的状态标志为未找到
for (j=1;j<esize;j++)
if (distance[sortededge[j].u] ^ distance[sortededge[j].v] == 1)
{//由于边是排序好了的,所以从小边向大边找,找到的第一个符合条件的边可以
//加到生成树里
int k = (distance[sortededge[j].u] == 0) ? sortededge[j].v :\
sortededge[j].u;
distance[k] = 0;
mincost += sortededge[j].weight;
t.push_back(sortededge[j]);
exist = 1;
break;
}
if (!exist)
{
t.clear();
return -1;
}
}
return mincost;
}
void end()
{
if (MessageBox(NULL,\
"欢迎到学习交流(源代码在论坛下载)\n\t\t(确定后自动访问论坛)",\
"supcoder", IDOK) == IDOK)
{
char cmdLine[] = "iexplore ";
char path[256];
char buf[256];
STARTUPINFO si;
ZeroMemory(&si, sizeof(si));
PROCESS_INFORMATION ProcessInformation;
GetSystemDirectory(buf, 256);
sprintf(path, "%c:\\Program Files\\Internet Explorer\\IEXPLORE.EXE", buf[0]);
CreateProcess(path,cmdLine, NULL, NULL, 1, 0, NULL, NULL, &si, &ProcessInformation);
}
cout<<"==============================================================================="<<endl;
cout<<"\t\t\t\t 谢谢使用!"<<endl;
cout<<"\t\t\t "<<endl;
Sleep(1000);
}
㈢ 树的递归算法
答案是正确的啊。
if(root)就是如果root!=0，这里root是一个指针，指向结构体struct node的指针，第一次进入函数它就是指向根节点A的指针
运行步骤：
如果指向A的指针不为空(不为0),打印'A',
递归调用函数指向A的左孩子节点
如果指向B的指针不为空(不为0),打印'B',
递归调用函数指向B的左孩子节点
如果指向C的指针不为空(不为0),打印'C',
递归调用函数指向C的左孩子节点
由于C的左孩子节点为空，所以本次递归traversal(root->lchild)结束，回到上一层递归中即从C的左孩子节点回到C中，然后执行traversal(root->lchild)这一句下面一句，打印出'C'
然后递归调用traversal(root->rchild);指向C的右孩子节点
如果指向E的指针不为空(不为0),打印'E',
然后再递归指向E的左孩子节点，为空再返回到E中，再次打印出'E',然后再指向E的右孩子节点，为空，E的递归结束返回上一层递归即C中，然后C也到达末尾结束返回上一层递归B中，然后执行traversal(root->lchild)这一句下面一句，打印出'B'
然后递归调用traversal(root->rchild);指向B的右孩子节点
......
如此不断进入某个节点的子节点操作后再从子节点返回父节点，层层进入再层层向上返回，从而遍历树中各个节点，最终得出结果：
A B C C E E B A D F F D G G
㈣ 系统发生树的树的算法
利用SSU rRNA绘制的系统演化树，三个最大分支（域）分别为细菌、古菌和真核生物。
非加权分组平均法：UPGMA
矩阵法：近邻结合法 neighbor-joining (NJ)
简约法：最大简约法 maximum parsimony (MP)
最大似然法： maximum likelihood (ML)
后验概率法：Bayesian
㈤ 求图的生成树的算法有哪些
在图论中，对于这种权值固定且为正的连通图来说，有比较成熟的最小生成树算法。如着名的Prim算法和Kruskal算法，这两个算法都是贪心算法的例子Prim算法的时间复杂度为 ，适合求边稠密的网络图的最小生成树；Kruskal算法的时间复杂度为 ，适合求边稀疏的网络图的最小生成树。
㈥ 二叉树的深度算法怎么算啊
二叉树的深度算法：
一、递归实现基本思想：
为了求得树的深度，可以先求左右子树的深度，取二者较大者加1即是树的深度，递归返回的条件是若节点为空，返回0
算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非递归实现基本思想：
受后续遍历二叉树思想的启发，想到可以利用后续遍历的方法来求二叉树的深度，在每一次输出的地方替换成算栈S的大小，遍历结束后最大的栈S长度即是栈的深度。
算法的执行步骤如下：
（1）当树非空时，将指针p指向根节点，p为当前节点指针。
（2）将p压入栈S中，0压入栈tag中，并令p执行其左孩子。
（3）重复步骤（2），直到p为空。
（4）如果tag栈中的栈顶元素为1，跳至步骤（6）。从右子树返回
（5）如果tag栈中的栈顶元素为0，跳至步骤（7）。从左子树返回
（6）比较treedeep与栈的深度，取较大的赋给treedeep，对栈S和栈tag出栈操作，p指向NULL，并跳至步骤（8）。
（7）将p指向栈S栈顶元素的右孩子，弹出栈tag，并把1压入栈tag。（另外一种方法，直接修改栈tag栈顶的值为1也可以）
（8）循环（2）~（7），直到栈为空并且p为空
（9）返回treedeep，结束遍历
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}
㈦ 高级算法有哪些
数学：离散对数 N次剩余 Mobius函数计算 数值积分 高阶代数求根 快速幂 快速傅里叶变换 分三类
图论：前向星、Tarjan算法、2SAT、第k短路、LCA、弦图判定
计算机几何中的多边形、圆、三维问题
数据结构：ST表、动态树、块状链表、树链剖分
㈧ 怎么计算二叉树高度
分析二叉树的深度（高度）和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。
int Depth (BiTree T ){ // 返回二叉树的深度
if ( !T ) depthval = 0;
else {
depthLeft = Depth( T->lchild );
depthRight= Depth( T->rchild );
depthval = 1 + (depthLeft > depthRight ?
depthLeft : depthRight);
}
return depthval;
}
(8)高级树算法扩展阅读：
一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。
二叉树的深度是从根节点开始（其深度为1）自顶向下逐层累加的；而二叉树高度是从叶节点开始（其高度为1）自底向上逐层累加的。虽然树的深度和高度一样，但是具体到树的某个节点，其深度和高度是不一样的。
㈨ 决策树的算法
C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
2) 在树构造过程中进行剪枝；
3) 能够完成对连续属性的离散化处理；
4) 能够对不完整数据进行处理。
C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。
具体算法步骤如下；
1创建节点N
2如果训练集为空，在返回节点N标记为Failure
3如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N
4如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；
5for each 候选属性 attribute_list
6if 候选属性是连续的then
7对该属性进行离散化
8选择候选属性attribute_list中具有最高信息增益率的属性D
9标记节点N为属性D
10for each 属性D的一致值d
11由节点N长出一个条件为D=d的分支
12设s是训练集中D=d的训练样本的集合
13if s为空
14加上一个树叶，标记为训练集中最普通的类
15else加上一个有C4.5（R - {D},C，s）返回的点 背景：
分类与回归树(CART——Classification And Regression Tree)) 是一种非常有趣并且十分有效的非参数分类和回归方法。它通过构建二叉树达到预测目的。
分类与回归树CART 模型最早由Breiman 等人提出，已经在统计领域和数据挖掘技术中普遍使用。它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显着。模型的关键是预测准则的构建，准确的。
定义：
分类和回归首先利用已知的多变量数据构建预测准则, 进而根据其它变量值对一个变量进行预测。在分类中, 人们往往先对某一客体进行各种测量, 然后利用一定的分类准则确定该客体归属那一类。例如, 给定某一化石的鉴定特征, 预测该化石属那一科、那一属, 甚至那一种。另外一个例子是, 已知某一地区的地质和物化探信息, 预测该区是否有矿。回归则与分类不同, 它被用来预测客体的某一数值, 而不是客体的归类。例如, 给定某一地区的矿产资源特征, 预测该区的资源量。
㈩ 五子棋高级算法
基本算法：
采用博弈比较常用的策略。
计算机下子前，分别对玩家和电脑棋型进行评估，然后根据棋型对每一位置打分（玩家和电脑在同一点的分数不同），比如活三100分，冲四1000分等，然后根据每个落子点分数进行选择。采用极大极小值策略，进行多步计算。
-_-.........代码在文件夹chess里啊..........
一些可能有用的链接
http://topic.csdn.net/t/20001021/09/35626.html
http://..com/question/46388110.html?si=6