网站设计服务,折扣卡网站建设,上海做网站大的公司有哪些,网站建设php有哪些最短路径 现实场景 1、一批货从北京到广州的的最快#xff0c;或最省钱的走法。 把路线中各城市当作图的顶点#xff0c;各城市之间的花费时间#xff0c;或金钱当作边的权重#xff0c;求两点之间的最短路径。 2、在城市群中建一个仓储基地#xff0c;建在什么位置可以… 最短路径 现实场景 1、一批货从北京到广州的的最快或最省钱的走法。 把路线中各城市当作图的顶点各城市之间的花费时间或金钱当作边的权重求两点之间的最短路径。 2、在城市群中建一个仓储基地建在什么位置可以让各个城市的送货速度都比较快。 同1把各城市间的送货速度当作边的权重求仓储基地到各城市间的最短路径。 算法 1、Dijkstra单源最短路径。 2、Floyd两点最短路径。 参考链接http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html 社区发现 现实场景 用于社交网络中的社区或话题发现基本特点是社区之间联系稀疏社区内部联系紧密。如给定新浪微博的用户关系数据找出其中的的社区以及核心节点。 算法 标签传播、主要特征向量、多层模块度、随机游走、边介数等几个系列算法。 各算法的优劣有一个评价体系即计算其 Modularity Measure(模块化度量值。 具体的算法介绍及Modularity Measure值计算可以参考这里http://blog.csdn.net/itplus/article/details/9286905 关于Fast Unfolding更详细的介绍可以参考这里http://blog.csdn.net/google19890102/article/details/48660239 网络评价 现实场景 现实中存在各种的网络社区聚集、好友关系、电力网、交通网等网络特点各不相同计算机科学上把这些现实网络划分为随机网络、小世界网络、规则网络、无标度网络等多种抽象的网络模型用网络模型去解释现实网络。并定义了一套可量化的标准特征来描述各种网络模型。 概念 1、平均路径长度。路径长度是指网络中任意两节点之间的最短路径。平均路径长度是指所有节点之间的平均最短距离。 2、网络直径。网络中所有节点之间的最大路径长度。 3、度分布。度是指网络结构中与某节点相连接的边的数目为该节点的度。社交网络中度数较多的节点通常是公众人物。 网络中各个的节点度的分布情况就为度分布如泊松分布、二项分布等。 4、介数。节点的介数指经过该节点的最短路径占整个网络所有最短路径的比例。如社交网络中的某些关键人物。 5、接近中心度。一个节点通过最短路径到达其它节点的难易程度。对于网络中的边缘节点其接近中心度会比较小。如偏远城市社交网络中的非主流人物。 6、Clustering coefficient聚集系数。主要衡量一个节点的邻节点之间的连接情况邻节点之间连接越多聚集系数越大。 7、网络密度。网络中节点固定情况下边数量越多则密度越大即节点之间联系更紧密。 8、互惠指数。即有向网络中的无向程度。 K-Core 现实场景 社交网络中有一批KOL存在他们的影响力远超普通大众。 算法 关于K-Core的详细解释及其算法实现可以参考这里网络节点度、H指数与核数之间的优美关系http://blog.sciencenet.cn/blog-3075-950475.html 二分图匹配 现实场景 1、通过数代人的努力你终于赶上了剩男剩女的大潮假设你是一位光荣的新世纪媒人在你的手上有N个剩男M个剩女每个人都可能对多名异性有好感请为他们两两配对最大程度减少剩男剩女个数。 2、有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少 算法 1、匈牙利算法 2、任务分配问题一般可以在多项式时间内转化成最大流量问题Maximum Flow Problem 匈牙利算法参考文章http://blog.csdn.net/dark_scope/article/details/8880547 二分图匹配问题转最大流问题的方法可参考这里 http://blog.csdn.net/caipeichao2/article/details/35306659 最小费用、最大流 现实场景 1、从城市A到城市B之间运输一批货物中间路过多个城市有多条路线可供选择两两城市之间的运输费用不等找出一条费用最小的路线。 2、把一批快递经由铁路由城市A运到城市B中间路过多个城市。在做任意两个城市间的铁路线上可运送的物资数量是有限的我们要考虑使铁路线承载量最大不让铁路资源闲置同时让快递运输时经过更多的城市以承揽更多快递业务。如果把铁路网上的车站看作是图的顶点两个车站间的铁路线看作是图的边把任意两城市间的铁路线上的允许最大运送量称为容量。这就是一个经典的求网络最大流问题。 概念 1、边权重的意义。不同场景下每条边的值有不同的意义问题1中边的权重为费用问题2中边的权重为剩余容量。 2、增广路径。在图中可能存在多条从源点到目标点的可行路径每一条都是一条增广路径。最小费用、最大流问题就是找到多条增广路径中满足最小费用、最大流条件的一条。 算法 1、最小费用问题可转化为求最短路径问题。 2、Edmond-Karp算法。 可参考文档http://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html 3、Ford-Fulkerson算法。 可参考文档http://www.cnblogs.com/kuangbin/archive/2011/07/26/2117636.html 最大连通子图 现实场景 1、计算机网络中的病毒通常会基于一种病毒存在多种变种病毒变种病毒与原病毒之间大部分代码相似。因此把两种病毒之间的函数调用关系用图表示出来分析其最大连通子图是否相似就可以判断是否变种病毒。 2、图像分割中寻找图像的最大连通域。 概念 最大连通子图。是指把图划分为N个子图后子图内所有节点相连子图间没有节点相连。这N个子图就是原图的最大连通子图。 欧拉回路 现实场景 1、七桥问题。 2、去北京动物园浏览能否设计一条这样的路线既可以游遍所有景点又不走重复路。 概念 1、欧拉回路。是指通过图无向图或有向图中所有边一次且仅一次行遍图中所有顶点的通路(回路)称为欧拉通路(回路)。 2、满足特定条件的图才能称为欧拉图。 算法 Fleury算法 哈密顿回路 现实场景 导游带团北京一日游遍需要设计一条路线可以走遍所有景点且只走一次。 概念 1、哈密顿回路。在一个图中由指定的起点前往指定的终点途中经过所有其他节点且只经过一次。 2、哈密顿回路并不一定存在。 3、属NP完全问题难以在有效时间内找到解决方案。 最小生成树 现实场景 1、在电路设计中常常需要把一些电子元件的插脚用电线连接起来。如果每根电线连接两个插脚把所有n个插脚连接起来只要用n-1根电线就可以了。在所有的连接方案中我们通常对电线总长度最小的连接方案感兴趣。 2、要在n个城市之间铺设光缆主要目标是要使这 n 个城市的任意两个之间都可以通信找出一条使用最短的光纤连通这些城市的铺设方法。 算法 1、Prim算法 2、Kruskal算法 拓扑排序 现实场景 1、一个大工程通常由多个任务组成这些子工程之间有的有依赖关系有的没有假设同时只能做一个任务请排出一个顺序来。 2、一个计算机专业的学生必须完成一系列课程才能毕业。如学习《数据结构》课程就必须安排在学完它的两门先修课程《离散数学》和《算法语言》之后。学习《高等数学》课程则可以随时安排因为它是基础课程没有先修课。 概念 1、有向无环图DAG。 2、AOV表示法。图的节点表示任务有向边表示先后顺序最终形成的是一个有向无环图才能进行拓扑排序。 算法 1、Kahn算法 2、DFS 关键路径 现实场景 一个工程如何优化任务的安排才能最大程度缩短工期 概念 1、在拓扑排序之后才能进行关键路径的优化。 2、AOE表示法。用图的节点表示任务有向边表示任务的先后顺序边的权重表示任务所花时间。 3、找到两个关键点进行优化完成整项工程至少需要多少时间哪些活动是影响工程进度的关键
