《城市网络模型与算法》课程教学大纲

1、城市网络模型与算法教学大纲 一、课程基本信息1课程代码：211018002课程中文名称：城市网络模型与算法 课程英文名称：Urban Network Models and Algorithms3面向对象：地理信息科学系大三本科生4开课学院（课部）、系（中心、室）：信息工程学院地理信息科学系5总学时数：32讲课学时数：20，实验学时数：126学分数：2 7授课语种：中文，考试语种：中文 8教材： 二、课程内容简介课程内容包括三大部分：网络和优化方法的基础知识；介绍网络的概念、存储；运筹学和最优化方法。城市网络模型。介绍城市网络应用、常见网络建模方法、市政公用网络和交通网络模型。网络分析算法。讨论

2、用于网络分析的算法策略，详细讲解最短路径算法，介绍高级网络分析问题。三、课程的地位、作用和教学目标现实世界中网状设施（如通信网、自来水管网、电力网、交通网等）迅速增多并日见复杂，对其实施计算机管理和分析的呼声越来越急迫。网络是地理信息系统（GIS）中一类独特的数据实体，它由若干线性实体通过结点连结而成。网络分析是空间分析的一个重要方面，是依据网络拓扑关系（线性实体之间，线性实体与结点之间，结点与结点之间的连结、连通关系），并通过考察网络元素的空间、属性数据，对网络的性能特征进行多方面的分析计算。本课程讨论运用于城市信息化领域的网络模型及网络分析算法，在数据结构和算法基本知识的基础上，深入介绍网

3、络的概念、构成和存储，讨论城市网络模型化方法及其在公用设施、城市交通等领域的应用，讲解常规网络分析算法。通过这门课的学习，学生能对城市地理信息系统中的网络模型、网络分析、网络应用具有全面的理解，能够正确运用GIS工具中的网络分析模块解决实际问题，也能针对实际需求设计简单的网络优化算法，为解决大型复杂网络优化问题打下较为坚实的基础。四、与本课程相联系的其他课程地理信息系统导论、交通地理学五、教学基本要求1.掌握网络的概念、存储、建模及其城市应用；2.掌握网络分析的算法思想，深入理解路径求解算法。3.了解关阀搜索、服务区域、资源分配、区位配置等高级网络分析问题。六、考核方式与评价结构比例本课程为考

4、查课程，平时成绩占总评成绩的40%，结课研究论文占总评成绩的60%。平时成绩包括考勤、课堂互动、作业等七、教学参考资料 书籍：Minieka E. Optimization algorithms for network and graphs. Marcel Dekker,Inc.,1978.中译本：李家滢，赵关旗译。网络和图的最优化算法。北京：中国铁道出版社，1984。ESRI. Network Analysis. Guide .Redlands,USA:Environmental Systems Research Institute，1995.王朝瑞。图论。北京：北京工业学院出版社，1986

5、。297308Thomas H. Cormen, Charles E. Leiserson, HYPERLINK /wiki/Ronald_L._Rivest o Ronald L. Rivest Ronald L. Rivest, and HYPERLINK /wiki/Clifford_Stein o Clifford Stein Clifford Stein. HYPERLINK /wiki/Introduction_to_Algorithms o Introduction to Algorithms Introduction to Algorithms, Second Edition.

6、 MIT Press and McGraw-Hill, 2001. Miller, H.J., Shaw, S.L., Geographic Information Systems for Transportation: Principles and Applications, Oxford University Press,2001.论文：Dijkstra E. W. A Note on Two Problems in Connexion with Graphs. Numer. Math., 1:269-271, 1959.Gallo G. and Pallottino S., Shorte

7、st Path Algorithms. Annals of Operations Research (13), 3-79.1988.曾文，徐世文。地理信息系统中的常规网络分析功能及相关算法。地球科学。1998，23(4)：355-356曾文,张德津,2002. MAPGIS管网开发平台的设计. 地球科学, 2002, 27 (3) :250 - 254.八、教学进度与内容安排教学内容学时安排第一部分 基础知识6第1章 网络的概念及其存储2第2章 运筹学和最优化方法2第3章 最优化方法的数据结构基础2第二部分 城市网络模型10第4章 城市网络应用概述2第5章 常见网络模型化方法2第6章 市政公用设施网络3第7章 交通网络模型3第三部分 网络分析算法16第8章 算法基础6 8.1 贪婪算法和分治法2 8.2 元搜索算法2 8.3 遗传算法和神经网；最短路径算法络2第9章 最短路径算法8 14.1 经典最短路径算