动态规划 与非网.ppt

通信网规划理论 第二章 电信网规划的基础知识 第二章 电信网规划的基础知识 第一节 图论基础知识 第二节 随机服务系统及其在电信中的应用 第三节 业务预测的基本方法 第四节 流量预测的基本方法 第五节 电信网规划中的评价准则 第六节 电信网规划中的财务经济评价指标及经济分析方法 第七节 多目标方法及其应用 第八节 智能算法及其应用 电信网规划的过程： 本章目的 通过本章介绍的一些定量分析方法，掌握电信网规划的一般方法。为进一步的进行实际的规划工作奠定基础。 本章的内容涉及： 图论 经济计量学 预测学 智能理论 第一节 图论基础知识 主要应用领域： 传输网络 电路理论 编码理论 可靠性理论 集成电路设计及计算机领域 第一节 图论基础知识 网络规划简介 网络中各最短连接方法 电信网中局、站间最短路的算法 网络流及其算法 电信网的可靠性 2.1.1 网 络 规 划 简 介 网络规划与图 网络规划问题的例子 图与网路分析 2.1.1 网络规划简介 ——网络规划问题的例子 2.1.1 网络规划简介 ——图与网路分析 图与网路的基本概念 图与网路 节点 (Vertex) 物理实体、事物、概念 一般用 vi 表示 边 (Edge) 节点间的连线，表示有关系 一般用 eij 表示 图 (Graph) 节点和边的集合 一般用 G(V,E) 表示 点集 V={v1,v2,…, vn} 边集E={eij } 无向图与有向图 弧 边 关联边 相邻(adjacent)节点 链(link) 圈(loop) 无向图与有向图 有向图中，由节点指向外的弧的数目称为正次数，记为 d+，指向该节点的弧的数目称为负次数，记为 d– 次数为 0 的点称为孤立点(isolated vertex) ，次数为 1 的点称为悬挂点(pendant vertex) 图中奇点的个数总是偶数个 走过图中所有边且每条边仅走一次的闭行走称为欧拉回路 偶图一定存在欧拉回路(一笔画定理) 无向图中，若任意两点间至少存在一条路径，则称为连通图(connected graph)，否则为非连通图( discon-nected graph)；非连通图中的每个连通子图称为成分 (component) 2.1.2 网络中各端点的最短连接方法 最小生成树算法 最小生成树 多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图 图的生成树 树 T 是连通图 G 的生成树(spanning tree)，若 T 是 G的子图且包含图 G 的所有的节点 最小生成树（最小部分树） 例2.1.2 通信网规划中通信线路的连接问题 某一地区有若干个主要城市，现准备修建信息高速公路把这些城市连接起来， 使得从其中任何一个城市都可以经信息高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市之间修建信息高速公路的成本，那么应如何决定在哪些城市间修建信息高速公路，使得总成本最小？ 显然，这要求在已知边长度的网路图中找最小生成树 最小生成树的算法： 选所剩最小的边加入边集 T Kruskal 算法： 任两点之间有且只有一条路径的图称为树(tree)，记为T 树的性质： 最少边的连通子图，树中必不存在回路 任何树必存在次数为 1 的点 具有 n 个节点的树 T 的边恰好为 n?1 条，反之，任何有n 个节点， n?1 条边的连通图必是一棵树 如何找到一棵生成树 深探法(depth first search)：任选一点标记为 0 点开始有哪些信誉好的足球投注网站，选一条未标记的边走到下一点，该点标记为 1，将走过的边标记；假设已标记到 i 点，总是从必威体育精装版标记的点向下有哪些信誉好的足球投注网站，若从 i 点无法向下标记，即与 i 点相关联的边都已标记或相邻节点都已标记，则退回到 i ?1 点继续有哪些信誉好的足球投注网站，直到所有点都被标记 广探法(breadth first search)：是一种有层级结构的有哪些信誉好的足球投注网站，一般得到的是树形图 将图中所有边按权值从小到大排列 是否和前面加入 的边构成回路 T 中是否有 n?1 条边 将边加入图中 N N T 是最小生成树 Y 舍去该边 Y 定理 指定图中任一点vi，如果 vj 是距 vi 最近的相邻节点，则关联边 eij 必在某个最小生成树中。 推论 将网路中的节点划分为两个不相交的集合V1和V2，V2=V?V1，则V1和V2间权值最小的边必定在某个最小生成树中。 * * 制作人：孙青华 对业务量、发展动向、趋势和前景等进行预测 提出电信网发展规划 实施规划方案 规划评价 规划调整 优化方案 确定规划目标 2.1.1 网 络 规 划 简 介 网络：电信网络、计算机网络、运输服务网络、 能源和物质分派网络、人际关系网络等等。 网络规划