- 1、本文档共26页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第2节 最短路径与选址问题 对于许多地理问题,当它们被抽象为图论意义下的网络图时,问题的核心就变成了网络图上的优化计算问题。其中,最为常见的是关于路径和顶点的优选计算问题。 在路径的优选计算问题中,最常见的是最短路径问题;而在顶点的优选计算问题中,最为常见的是中心点和中位点选址问题。 一、最短路径问题 “纯距离”意义上的最短路径 例如,需要运送一批物资从一个城市到另一个城市,选择什么样的运输路线距离最短? “经济距离”意义上的最短路径 例如,某公司在10大港口C1,C2,…,C10设有货栈,从Ci到Cj之间的直接航运价格,是由市场动态决定的。如果两个港口之间无直接通航路线,则通过第三个港口转运。那么,各个港口之间最廉价的货运线路是什么? “时间”意义上的最短路径 例如,某家经营公司有一批货物急需从一个城市运往另一个城市,那么,在由公路、铁路、河流航运、航空运输等4种运输方式和各个运输线路所构成的交通网络中,究竟选择怎样的运输路线最节省时间? (二)最短路径的算法 标号法 1959年E.W.Dijkstar 提出的标号法是最短路径问题最好的求解方法 。 标号法优点 不仅可以求出起点到终点的最短路径及其长度,而且可以求出起点到其他任何一个顶点的最短路径及其长度;同时适用于求解有向图或无向图上的最短路径问题。. 标号法具体计算步骤 ① 如果刚刚得到P标号的点是vi,那么,对于所有这样的点 将其T标号修改为:min[T(vj),P(vi)+wij]。 ② 若G中没有T标号,则停止。否则,把点 的T标号修改为P标号,然后再转入①。 其中, 满足 二、选址问题 选址问题,是现代地理学研究的主要问题之一。选址问题涉及人类生产、生活、文化、娱乐等各个方面。 选址问题的数学模型取决于两个方面的条件 :可供选址的范围、条件;怎样判定选址的质量。 本节的讨论仅限于选址的范围是一个地理网络,而且选址位置位于网络图的某一个或几个顶点上。 对这样的选址问题,根据其选址的质量判据,可以将其归纳为求网络图的中心点与中位点两类问题。 (一)中心点选址问题 (二)中位点选址问题 中位点选址问题的质量判据 使最佳选址位置所在的顶点到网络图中其他各个顶点的最短路径距离的总和(或者以各个顶点的载荷加权求和)达到最小。 中位点选址问题的数学描述 设G=(V,E)是一个简单连通赋权无向图,连接两个顶点的边的权值为该两顶点之间的距离;对于每一个顶点vi(i=1,2,…,n),有一个正的负荷a(vi),而且它与其他各顶点之间的最短路径长度为di1,di2,…,din。那么,中位点选址问题,就是求图G的中位点 ,使得 * * 最短路径问题 选址问题 (一)最短路径的含义 以上3类问题,都可以抽象为同一类问题,即赋权图上的最短路径问题。 不同意义下的距离都可以被抽象为网络图中边的权值。 权——这种权值既可以代表“纯距离 ”,又可以代表“经济距离 ”,也可以代表“时间距离 ”。 标号法的基本思想 设G是一个赋权有向图,即对于图中的每一条边,都赋予了一个权值。在图G中指定两个顶点,确定为起点和终点,不妨设v1为起点,vk为终点。 首先从v1开始,给每一个顶点标一个数,称为标 号。这些标号,又进一步区分为T标号和P标号两种类型。其中,每一个顶点的T标号表示从起点v1到该点的最短路径长度的上界,这种标号为临时标号;P标号表示从v1到该点的最短路长度,这种标号为固定标号。 在最短路径计算过程中,对于已经得到P标号的顶点,不再改变其标号;对于凡是没有标上P标号的顶点,先给它一个T标号;算法的每一步就是把顶点的T标号逐步修改,将其变为P标号。 那么,最多经过k-1步,就可以求得到从起点v1到每一个顶点的最短路径及其长度。 开始,先给v1标上P标号P(v1)= 0,其余各点标上T标号T(vj)=+∞(j≠1)。 例1:在图10.2.1所示的赋权有向图中,每一个顶点vi(i=1,2,…,n)代表一个城镇;每一条边代表相应两个城镇之间的交通线,其长度用边旁的数字表示。试求城镇v1到v7之间的最短路径。 图10.2.1 赋权有向交通网络图 解:首先给v1标上P标号P(v1)=0,表示从v1到v1的最短路径为
您可能关注的文档
- 花卉繁殖修剪技术.doc
- 传递爱心的优秀精选作文.docx
- 18.1-利用勾股定求解最短路线--.ppt
- 病理课实习大体标本--组织损伤.ppt
- 大连中远物流绩效管理手册.docx
- 第六个关键期.doc
- 临沂最专业电脑办公培训.ppt
- 高二物理电势差.pdf
- 封面设计PPT模板下.pdf
- 临沂电脑培训班office办公软件学习大纲.pptx
- 2024年光伏全球巡礼中国篇:供需失衡,何时出清.pdf
- 2024年服务消费行业分析报告:服务消费的时代交响,不畏浮云遮望眼,迭代发展进行时.pdf
- 2024年电子行业分析报告:Scaling+law依然有效,自研AI芯片后劲十足.pdf
- 2024年艾融软件分析报告:深耕金融IT领域,收购优质资产打开市场空间.pdf
- 2023年AIGC行业分析报告:GPT-4v如何实现强大多模态,从文生图到图生文.pdf
- 2023年电力辅助服务行业分析报告:重塑价值.pdf
- 2023年亚朵分析报告:体验驱动,中高端国民品牌.pdf
- 2023年钠离子电池行业分析报告:突破关键资源瓶颈,性能优势显著.pdf
- 2023年甲骨文分析报告:战略拐点已过,基本面回归上行趋势.pdf
- 2024年智能汽车行业分析报告:FSD入华在即,关注汽车数据闭环服务商.pdf
最近下载
- 肩关节磁共振诊断.ppt VIP
- 2024年7月6日江苏省泰州市(姜堰区、高港区)、兴化市、泰兴市事业单位考试《综合能力素质》笔试试题(含答案).pdf VIP
- 《“核心素养”视域下小学语文习作单元主题教学策略的研究》课题研究方案.doc
- 北碚区及15个街镇土地利用总体规划(2006-2020年)调整方案.doc
- 【语文】人教部编版语文八年级上册:古诗文理解性默写(完整版).pdf VIP
- 煤化工工艺学完整版电子教案全套教学课件汇总.pptx
- 磁共振成像原理及功能磁共振演示文稿.ppt VIP
- 中职《幼儿心理学》课程教学课件-项目二任务3 感知觉规律的运用.pptx VIP
- Hasselblad哈苏H6中文说明书.pdf
- (人教2024版)一年级数学上册《数学游戏》单元复习讲义.docx
文档评论(0)