多叉路口信号灯设置问题的建模与求解策略.doc

摘要：我国是一个人口大国，道路交通堵塞问题一直困扰着我们，怎样在一定时间内实现多岔路口交通的最大流通量成为一个值得研究的问题。本文将讨论怎样把实际的多叉路口点着色信号灯设置问题转化为平面图和非平面图的点着色问题，并分析、比较、运用四色原理（只适用于平面图）和多种颜色的着色方案（也适用于非平面图），从而实现更贴合实际的交通情况并实现路口的最大效率流通。

关键词：着色   四色原理   平面图 

目录

摘要

Abstract

1绪论-1

1.1研究背景-1

1.2研究思路与方法-2

1.2.1研究思路-2

1.2.2研究方法-2

1.3开发工具和环境-3

1.3.1代码实现的开发环境-3

1.3.2图形显示的开发工具-3

2多叉路口信号灯设置问题的数学建模-3

2.1常见的多叉路口-3

2.2数据模型建立-6

2.2.1图及数据结构表示-9

2.2.2着色问题-10

3多叉路口信号灯设置问题的算法实现与分析-11

3.1快速排序法-11

3.1.1 算法思想-11

3.1.2算法实现-13

3.1.3运行测试与分析-15

3.2干扰矩阵算法-16

3.2.1算法思想-16

3.2.2算法实现-17

3.2.3运行测试与分析-19

3.3点的着色算法-21

3.3.1算法思想-21

3.3.2算法实现-23

3.3.3运行测试与分析-24

4总结与展望-28

4.1研究结论-28

4.2建议与对策-28

4.3研究中遇到的问题-30

致谢-32

参考文献-33