交通指挥灯问题求解(穷举法和贪心算法)


问题描述:一个具有五条通路的交叉路口,当允许某些通路上的车辆在交叉路口通行时,必须对其他通路上的车辆加以限制,不许同时在交叉路口通行,以免发生碰撞。那么,如何建立一个模型来求出最少需要几种颜色的信号灯来控制通行?

这道题我们可以使用穷举法和贪心算法两种方法来解决。

1. 穷举法

#include <stdio.h>
#include <stdlib.h>

int e[13][13] = {
    {0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0},
    {0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0},
    {0, 0, 0, 0, 0, 1, 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, 1, 1, 0, 0, 1, 1, 0},
    {1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0},
    {1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0},
    {1, 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, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

int v[13] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};

void hs(int k, int c)
{
    int i, j;
    //从第k个灯开始尝试添加

    //递归出口
    if (k == 13)
    {
        printf("\n最少用灯%d个,方案:", c);
        for (i = 0; i < 13; ++i)
            printf("%d ", v[i]);
        getchar();
        exit(1);
    }

    for (i = 0; i < c; ++i)
    {
        //给第k个灯试验所有灯的颜色
        v[k] = i;
        int ok = 1;
        for (j = 0; j < k; ++j)
        {
            if (v[j] == v[k] && e[j][k] == 1)
            { //有冲突
                ok = 0;
                break;
            }
        }
        if (ok)
            hs(k + 1, c);
    }
}

int main()
{
    int c;
    for (c = 2; c < 13; ++c)
    {
        //试探c个灯,检查是否能得到答案
        hs(0, c);
    }
    printf("End!\n");
    return 0;
}

输出结果:

2. 贪心算法

#include <stdio.h>

int e[13][13] = {
    {0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0},
    {0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0},
    {0, 0, 0, 0, 0, 1, 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, 1, 1, 0, 0, 1, 1, 0},
    {1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0},
    {1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0},
    {1, 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, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

int v[13] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};

int main()
{
    int cnt_color = 1;
    int i, j;
    for (i = 0; i < 13; ++i) //一层循环,找到未涂色的点
    {
        int flag = 1;
        if (v[i] == -1)
        {
            v[i] = cnt_color;
            printf("第%d种颜色节点:%d ", cnt_color, i);
            for (j = 1; j < 13; ++j) //二层循环,找到与i不冲突且未着色的顶点
            {
                if (v[j] == -1 && e[i][j] == 0)
                {
                    for (int h = 0; h < 13; ++h) //三层循环,确定j与其他同色的点不冲突
                        if (e[j][h] == 1 && v[h] == cnt_color)
                        {
                            flag = 0;
                            break;
                        }
                    if (flag == 1)
                    {
                        v[j] = cnt_color;
                        printf("%d ", j);
                    }
                }
            }
            cnt_color++;
            printf("\n");
        }
    }
    printf("总共%d种颜色\n", cnt_color - 1);
    return 0;
}

输出结果:


文章作者: 恰醋
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 恰醋 !
评论
 上一篇
二路归并排序 二路归并排序
设计二路归并排序的原理就是将一个数组分成两个数组,分别对两个数组进行排序,最后将两个数组合为一个数组完成排序。在这个过程中,涉及到了“分治算法”,使用了递归。
2020-03-08
下一篇 
计算机组成原理绪论 计算机组成原理绪论
1. 一些概念 主机:CPU+MM(主存或内存) CPU:中央处理器。包括运算器和控制器。 主存:存放正在运行的程序和数据,可随机存取 存储单元:可以存放机器字并具有特定存储地址的存储单位 存储元件:存储一位二进制信息的物理元件 存储字:一
  目录