图论——支撑树图论——支撑树图论——支撑树

  • q1_808451
    了解作者
  • 40.8KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-06-15 01:58
    上传日期
图论——支撑树图论——支撑树图论——支撑树图论——支撑树图论——支撑树图论——支撑树图论——支撑树图论——支撑树图论——支撑树图论——支撑树图论——支撑树图论——支撑树图论——支撑树图论——支撑树图论——支撑树
图论_支撑树.rar
  • 图论_支撑树
  • 最小生成树(prim+mapped_heap邻接表形式).txt
    1.5KB
  • 最优比率生成树例子.txt
    2.5KB
  • 复件 最小树形图(网上找的).txt
    2.7KB
  • 最优比率生成树.txt
    7.3KB
  • 最小生成树(prim+binary_heap邻接表形式).txt
    1.1KB
  • 最小树形图(邻接阵形式).txt
    1.5KB
  • 3164最小树形图例子.cpp
    2.1KB
  • 最小生成树(kruskal正向表形式).txt
    1.4KB
  • 网上最小树形图.cpp
    3.7KB
  • 最小生成树(kruskal邻接表形式).txt
    1.4KB
  • 最小生成树(prim邻接阵形式).txt
    1KB
  • 最小生成树(prim+mapped_heap正向表形式).txt
    1.5KB
  • 最小树形图(网上找的).txt
    6.4KB
  • 1639——Picnic Planning.doc
    55KB
  • 1689.cpp
    1.1KB
  • 无向图的环.txt
    1.7KB
  • pascal转的c(有向图无向图的环).txt
    1KB
  • 判断有向图的环.doc
    37KB
  • 16792.cpp
    2.5KB
  • 16892.cpp
    1.1KB
  • 1679.cpp
    1.8KB
  • 有向图判断环并找出来.txt
    1.3KB
  • 16893.cpp
    929B
  • 最小生成树(prim+binary_heap正向表形式).txt
    1.1KB
内容介绍
已知一个完全图,每条边有两个参数(dis和c),求一棵生成树,使(∑xi×ci)/(∑xi×disi)最小,其中xi当第i条边包含在生成树中时为1,否则为0。 迭代法: 假设rate为当前比率,以ci-rate×disi作为各边的权重,使用Prim算法构造最小生成树,再对该最小生成树求(∑xi×ci)/(∑xi×disi)更新rate,可证明rate可收敛且收敛值即为所求。 二分法: 在一个精度范围内(以1e-6为例),二分查找[0,maxRate]之间的值rate,使(z=∑xi×ci-rate×∑xi×disi)==0,可证明该值即为所求。其中xi为以ci-rate×disi作为各边权重时,使用Prim算法所构造的最小生成树。在二分搜索过程中若z>0,则将区间上移(low=mid+1),否则将区间下移(high=mid-1)。 使用迭代法,以0作为初始迭代比率:188MS 使用二分法,固定查找范围为[0,31],精度为1e-6:1422MS(不知二分法大家都有什么优化,分享一下吧^_^) 下面介绍一下该题目的解题思路及相关证明: 1、问题转化: 给定一个rate,z(rate)=∑xi×ci-rate*∑xi×disi,xi为一棵生成树使(∑xi×ci-rate*∑xi×disi)的值最小(下面会介绍求此生成树的方 法),则rate=(∑xi×ci-z(rate))/( ∑xi×disi),令rateNex=(∑xi×ci)/( ∑xi×disi)。 若z(rate)>0,则肯定不存在一棵生成树使rate=(∑yi×ci)/( ∑yi×disi),即rate值无效,且有rateNex >rate; 若z(rate)<0,则我们可得到一个有效比率rateNex,且rateNex<rate; 若z(rate)==0,则rateNex==rate,且rate有效。 因此,如果有且仅有一个rate使z(rate)==0,又由题目所求的最小比率的存在性(有限节点的完全图其生成树只有有限个)可知,该rate值即为所求。 下面证明其存在性和唯一性: 存在性:对于题目所求的最小比率rateMin,由上面的分析必有z(rateMin)=0,又由该最小比率的存在性可知,至少存在一个有效的比率rate使z(rate)=0; 唯一性:只要证明z(rate)函数的单调性即可: 对于两个比率rate1<rate2, z(rate1)-z(rate2)= (∑xi×ci-rate1*∑xi×disi)-(∑yi×ci-rate2*∑yi×disi) <=(∑yi×ci-rate1*∑yi×disi)-(∑yi×ci-rate2*∑yi×disi) /*由z(rate)的定义,xi为一棵生 成树使(∑xi×ci-rate*∑xi×disi)的值最小,故有z(rate1)= (∑xi×ci-rate1*∑xi×disi)<= (∑yi×ci-rate1*∑yi×disi)*/ =(rate2-rate1)* ∑yi×disi>0 因此,z(rate)为单调递减函数。从而也就证明了满足z(rate)==0的比率rate的唯一性。 由上面的分析,我们就将问题转化为求解比率rate使z(rate)==0。 2、求解:有两种方法对该问题进行求解:迭代法和二分法。 A、迭代法:由上面的分析可知: 当 z(rate)>0时,rate值无效,而rateNex有效且z(rateNex)<=0; 当z(rate)<0时,rateNex<rate,又z(rate)为单调递减函数,故0>=z(rateNex)>z(rate)。 故迭代过程向z(rate)==0收敛,又由有限节点的完全图其生成树只有有限个可知迭代次数必为有限值。 B、二分法:在定出一个搜索范围和精度之后(以[0,MAXRATE]为例),我们就可以使用二分法进行搜索:对于当前的搜索区间[low,high],mid=(low+high)/2,根据z(mid)的值及z(rate)的增减性,对搜索区间进行更新: 若z(mid)>0,上调区间,使low=mid+1; 若z(mid)<0,下调区间,使high=mid-1; 从而在经过有限次搜索之后便能找到所求比率。 3、求解生成树xi使(∑xi×ci-rate*∑xi×disi)的值最小的方法: ∑xi×ci-rate*∑xi×disi=∑xi(ci+rate×disi),从而问题转化为以ci+rate×disi为边的权重,求解最小生成树,对于完全图,可使用 prim算法,其复杂度只与节点数有关。 Source Code Problem: 2728 User: jlw686 Memory: 248K Time: 188MS Language: C++ Result: Accepted * Source Code #include <cmath> #include <iostream> #include <vector> #include <assert.h rel='nofollow' onclick='return false;'> using namespace std; //N (2 <= N <= 1000) #define min(a,b) ((a)<(b)?(a):(b)) struct Point3D { Point3D() { x=y=z=0; } void set(int _x,int _y,int _z) { x=_x;y=_y;z=_z; } double len(const Point3D& pt) const { int dx=x-pt.x; int dy=y-pt.y; return sqrt((double)(dx*dx+dy*dy)); } int cost(const Point3D& pt) const { return abs(z-pt.z); } int x,y,z; }; struct Edge { Edge(int _pt1,int _pt2) { pt1=_pt1;pt2=_pt2; } int pt1,pt2; }; const int MAXN=1001; const int INF=0xfffff; int N; Point3D vil[MAXN]; //用于Prim算法 double dLowCost[MAXN];//外面某村庄到closet中的各村庄的最小值 int nToIdx[MAXN];//最小消耗所对应的村庄 char closet[MAXN]={0};//已选进来的村庄 vector<Edge> vecEdge;//建立的边 inline double GetCost(double dRate,const Point3D& pt1,const Point3D& pt2) { return pt1.cost(pt2)-dRate*pt1.len(pt2); } //返回下一个要加入的节点下标 int RefLowCost(int id,double dRate) { double dMinCost=INF; int nMinIdx=-1; for (int i=0;i<N;i++) { if(!closet) { double dCost=GetCost(dRate,vil[id],vil); if(dCost<dLowCost) { dLowCost=dCost; nToIdx=id; } if (dLowCost<dMinCost) { dMinCost=dLowCost; nMinIdx=i; } } } return nMinIdx; } void Prim(double dRate) { int i; ////////////////////////////////////////////////////////////////////////// //初始化 vecEdge.clear(); memset(closet,0,sizeof(closet)); for (i=1;i<N;i++) { dLowCost=INF; nToIdx=-1; } ////////////////////////////////////////////////////////////////////////// closet[0]=1; int nMinIdx=0; for (i=1;i<N;i++) { int nNex=RefLowCost(nMinIdx,dRate); closet[nNex]=1; vecEdge.push_back(Edge(nToIdx[nNex],nNex)); nMinIdx=nNex; } } ////////////////////////////////////////////////////////////////////////// //迭代法 double GetRate() { double dC=0,dL=0; for (int i=0;i<vecEdge.size();i++) { dC+=vil[vecEdge.pt1].cost(vil[vecEdge.pt2]); dL+=vil[vecEdge.pt1].len(vil[vecEdge.pt2]); } return dC/dL; } double ItSolve() { double dNexRate=0; double dRate; do { dRate=dNexRate; Prim(dRate); dNexRate=GetRate(); }while(fabs(dRate-dNexRate)>1e-6); return dRate; } ////////////////////////////////////////////////////////////////////////// //二分法 double GetZ(double dRate) { double z=0; for (int i=0;i<vecEdge.size();i++) z+=GetCost(dRate,vil[vecEdge.pt1],vil[vecEdge.pt2]); return z; } double BiSolve() { double dRate=31; int nExp=1e6; int low=0,high=(int)(dRate*nExp); double z; while (low<high) { int mid=((high+low)>>1); dRate=mid*1.0e-6; Prim(dRate); z=GetZ(dRate); if (fabs(z)<1.0e-6) break; else if(z>0) low=mid+1; else high=mid-1; } return dRate; } ////////////////////////////////////////////////////////////////////////// int main(int argc, char* argv[]) { vecEdge.reserve(999); while (scanf("%d",&N)&&N) { for (int i=0;i<N;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); vil.set(x,y,z); } printf("%.3lf\n",ItSolve()); } return 0; }
评论
    相关推荐
    • 图论代码示例
      图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
    • 图论相关知识
      包含了两边我手头上的图论图书:《图论与网络流理论》、《图论
    • 图论练习题
      图论建模题,程序设计竞赛资料。适用于NOIP,NOI,IOI等选手。
    • 图论基础教程
      在下载频道的搜索中没有搜索到图论的相关书籍,所以上传图论基础教程。
    • 图论工具箱
      由斯坦福大学开发的图论工具箱,包含各种图论分析程序,简洁高效
    • 图论的讲义
      图论的入门级别的讲义,适合初学者
    • 图论复习资料
      关于图论基本考点几套试题 和复习资料 共10套
    • 2017图论讲义
      是学生学习图论的基础,其中包含了所有的图论的基本概念,是一本非常好用和实用的教材,图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形...
    • 图论小软件
      图论,利用它可以很好的解决一系列的图论问题,可以试试
    • 图论模型学
      图论模型学经典英文原版教材 MIT教材 适用于Biological and Computational Learning 其内容涵盖范围非常广:HMM,Statical Method,EM,Kalman Filter,Markov Property etc