数据结构课设：多叉路口交通灯管理问题 |
您所在的位置：网站首页 › 红绿灯怎样设置才算合理的 › 数据结构课设：多叉路口交通灯管理问题 |
数据结构课设：多叉路口交通灯管理问题
|
题目描述
通常，在十字交叉路口只需设红、绿两色的交通灯便可保持正常的交通秩序，而在多叉路口需设几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大流通。假设有一个如图(a)所示的五叉路口，其中C和E为单行道。在路口有13条可行的通路，其中有的可以同时通行，如A→B和E→C，而有的不能同时通行，如E→B和A→D。那么，在路口应如何设置交通灯进行车辆的管理呢？ 
问题转化为图着色问题
用最少的颜色对图着色对尽可能多的点着以相同的颜色让尽可能多的通道的车辆可以同时通行=>车流量最大 邻接矩阵按图里从左到右从上到下的顺序对13个顶点从0~12依次标号，然后按照两顶点之间有边相连值为1，无边相连值为0的规则，得到邻接矩阵，如下： 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 算法 算法1：回溯法（深度优先搜索）思路： 假设符合题意的最小颜色数是m则每一个顶点可以涂m种颜色，共m^13种可能（包括合理和不合理的涂色方案）采用深度优先搜索算法，找到合理的涂色方案，如果找不到则增加最小颜色数继续查找 该算法一定得到最优解，但时间复杂度高。 算法2：贪婪算法（Welch Powell算法） 将顶点按度数由大到小排列对未涂色的度数最大的顶点涂色，并将与该顶点不相连且满足条件的其它顶点涂以相同的颜色检查是否存在未涂色的顶点，若有，换一种颜色，重复2），否则，结束算法 该算法是启发式算法，时间复杂度低，但不一定得到最优解。 算法源码 算法1 #include using namespace std; //颜色类 class Color { public: Color(int n,int **a,int *x,int sum); bool ifOk(int node); void Dfs(int node); int n; //顶点数 int m; //可用颜色数 int **a; //邻接矩阵 int *x; //解向量 int sum; //可着色方案数 }; //构造函数 Color::Color(int n,int **a,int *x,int sum){ this->n=n; this->a=a; this->x=x; this->sum=sum; } //判断顶点node是否可以涂色 bool Color::ifOk(int node) { for (int i = 1; i n) { sum++; //输出该涂色方案 for (int i = 1; i |
【本文地址】
今日新闻 |
推荐新闻 |