Loading...
墨滴

公子宇

2021/12/12  阅读:44  主题:自定义主题1

管道铺设施工的最佳方案问题

管道铺设施工的最佳方案问题

一、问题描述

(1) 实验题目

需要在某个城市n个居民小区之间铺设煤气管道,则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道,但由于地理环境不同,所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小,这个问题即为求无向网的最小生成树。

(2) 基本要求

在可能假设的m条管道中,选取n-1条管道,使得既能连通n个小区,又能使总投资最小。每条管道的费用以网中该边的权值形式给出,网的存储采用邻接表的结构。

(3) 测试数据

使用下图给出的无线网数据作为程序的输入,求出最佳铺设方案。右侧是给出的参考解。

二、需求分析

(1) 程序所能达到的基本可能

  1. 本程序用来求出一个无线网的最小生成树
  2. 程序运行后显示提示信息,引导用户输入无线图的各个边以及各个边的权值
  3. 用户输入之后,程序自动输出最小生成树

(2) 输入和输出的形式

  1. 输入数据:从键盘或文件读入上图中的无向网,以顶点对(i, j)的形式输出最小生成树的边。
  2. 输出数据:最小生成树的各个边、这些边的权值以及总的权值。

三、概要设计

(1) 边类型定义

typedef struct edge{
    int pnt1;
    int pnt2;
    float weight;
}Edge;

(2) 模块定义

// qsort函数中使用,使edges结构体中的边按照权值大小升序排序
int compar(const void* a, const void* b);
// kruskal算法寻找最小生成树edges 存储用户输入的图的各个边,minTree 用于记录组成最小生成树的各个边
void KruskalMinTree(Edge edges[], Edge minTree[]);
// 将最小生成树minTree输出
void output(Edge minTree[]);

(3) 主程序调用关系

  1. 变量声明

    i, an, edges[ENUM], minTree[VERNUM - 1]

  2. 循环获取无向图的边和权值

  3. 调用void KruskalMinTree(Edge edges[], Edge minTree[]);,获得最小生成树

  4. 调用void output(Edge minTree[]);,输出最小生成树

四、详细设计

(1) 预定义和边类型定义

#define ENUM 15   // 图中边的数量
#define VERNUM 9   // 图中顶点的数量

// 构建表示边的结构体
typedef struct edge{
    int pnt1;
    int pnt2; // 一条边有 2 个顶点
    float weight; // 边的权值
}Edge;

(2) compar模块

该模块是为了在qsort函数中使用,使edges结构体中的边按照权值大小升序排序

int compar(const void* a, const void* b)
{
    return ((Edge*)a)->weight - ((Edge*)b)->weight;
}

(3) 寻找最小生成树模块

void KruskalMinTree(Edge edges[], Edge minTree[]);

  1. 定义变量

    int i, pnt1, pnt2, elem, k;

    int num = 0;

  2. 为每一个顶点配备一个id

    int book[VERNUM];

    for(i = 0; i < VERNUM; i++) book[i] = i;

    初始状态下,每个顶点的id都不相同

  3. 根据权值,对所有边进行升序排序

    调用内置函数void qsort(...);

  4. 循环遍历所有的边

    1. 找到当前边的两个顶点在book数组中的位置下标

    2. 判断这两个顶点的id值是否相同

      如果顶点位置存在且顶点的id不同,说明不在一个集合中,不会产生回路。

      若不同,则执行以下步骤:

      1. 记录该边,作为最小生成树的组成部分
      2. 将新加入生成树的顶点id全部改为一样的
      3. 如果选择的边的数量和顶点数相差1,证明最小生成树已经形成,退出循环

(4) 输出最小生成树模块

void output(Edge minTree[]);

  1. 前置准备

    int i;

    float cost = 0;

  2. 循环输出最小生成树的边与权重

  3. 打印总权重

五、调试分析

(1) 算法编写思路

程序将无向图和最小生成树均看作是边typedef struct edge{...}Edge;的数组,而该数据结构包含三个属性:端点1,端点2,权值。之后再通过Kruskal算法来找出最小生成树。之后将最小生成树输出。

(2) 算法的时空分析

  1. 寻找最小生成树模块void KruskalMinTree(Edge edges[], Edge minTree[]);先是循环输入n次配置id,之后又循环遍历n条边,之后记录入最小生成树的时候,又循环输入n次,统一id值,所以时间复杂度为O(n^2^)。
  2. 输出最小生成树模块void output(Edge minTree[]);,循环n次输出最小生成树的边,运算次数为n,时间复杂度为O(n)。

六、使用说明

程序运行之后用户按提示先输入两个端点,再输入这两个端点形成的边的权值,输入完毕之后,程序自动打印最小生成树的各个边以及边的权值,最后输出总权值。

七、调试结果

连续多组测试样例

Please enter an edge(1 of 15)
 - Two endpoints(like a,b): a,b
 - Weighting: 32.8
--------------------------------

每一次循环都会打印提示,以下简略化

 - Two endpoints(like a,b): a,c 
 - Weighting: 44.6
 - Two endpoints(like a,b): a,h 
 - Weighting: 12.1
 - Two endpoints(like a,b): a,i 
 - Weighting: 18.2
 - Two endpoints(like a,b): b,c 
 - Weighting: 5.9
 - Two endpoints(like a,b): c,d 
 - Weighting: 21.3
 - Two endpoints(like a,b): c,e
 - Weighting: 41.1
 - Two endpoints(like a,b): c,g
 - Weighting: 56.4
 - Two endpoints(like a,b): d,e
 - Weighting: 67.3
 - Two endpoints(like a,b): d,f
 - Weighting: 98.7
 - Two endpoints(like a,b): e,f
 - Weighting: 85.6
 - Two endpoints(like a,b): e,g
 - Weighting: 10.5
 - Two endpoints(like a,b): f,i
 - Weighting: 79.2
 - Two endpoints(like a,b): g,h
 - Weighting: 52.5
 - Two endpoints(like a,b): h,i
 - Weighting: 8.7

最终输出

The minimum tree:
 - b-c  Weighting: 5.90
 - h-i  Weighting: 8.70
 - e-g  Weighting: 10.50
 - a-h  Weighting: 12.10
 - c-d  Weighting: 21.30
 - a-b  Weighting: 32.80
 - c-e  Weighting: 41.10
 - f-i  Weighting: 79.20
 - Total weight: 211.60

八、遇到的问题和解决方法

(1) 生成的图存在闭合区域

  • 描述

    程序输出的最小生成树之中出现了闭合的回路,不能称为树了

  • 解决方法

    之所以会出现闭合的回路,是因为在生成树的时候,我是先对各个边按照权值进行排序,之后再逐个提取最小的边。在这个过程中,如果最短的几个边的端点恰好互相一致,就会形成回路。所以,在提取最短边之前,我对每个端点进行标记,为每个点配置了id值。一旦选择了一条边,就将这条边两个端点的id值设为一致。只有两端点id值不同的边才能被选择。

(2) 获取字符输入问题

  • 描述

    在获取字符输入的时候,因为缓存空间的问题,会出现输入跳过的现象(和停车场管理问题中的类似)

  • 解决办法

    将端点输入和权值输入分开,对端点输入,使用字符串整体输入scanf("%s",edpnt);,之后再进行edges[i].pnt1 = edpnt[0] - 'a' + 1;edges[i].pnt2 = edpnt[2] - 'a' + 1;。对权值输入,就是普通的浮点数输入。

九、实验收获与感想

  1. 这次实验与无向图有关,在图的建立过程中,我曾经尝试过使用邻接表和邻接矩阵来构建图,但之后的算法建立就十分困难,后来发现利用边的数组反而更合适。一种数据结构可以有几种实现方式,所以在编写程序的过程中,选择合适的实现方式是十分关键的。
  2. 通过这次实验,我接触到了Kruskal算法,这个算法用于在无向图中寻找最小生成树。

十、附录

源程序文件清单:

  • PipeLaying.c

公子宇

2021/12/12  阅读:44  主题:自定义主题1

作者介绍

公子宇