论文部分内容阅读
本文主要解决的是这样的问题:在有向赋权网络中寻找一个有向的信息网络（即存在一个信息存储点，从它发出的信息能够到达其他所有的顶点），并用已知的材料来构建这个信息网络，如何构建使得所用材料最省。
对于这个问题，本文将其分解成两个部分。第一个部分:现有一个赋权网络N=（V,A;w;s），其中w: A→ R+是弧上的长度函数，s是赋权网络N上的一个固定信息存储点。从这个信息点发出的信息，能够传递到V中所有其他顶点，按照这样的传递方式构成赋权网络N上的一个信息网络N。接着用一种长度为L的材料来构建这个信息网络N，即用这种材料来连接信息网络N上的弧，目标是所使用的材料根数达到最少。第二个部分:在第一个部分的基础上，对V中的每个顶点vi求一次这样的信息网络Ni，然后再构建信息网络Ni得到不同的材料根数，取最小的材料根数作为该问题的解，其对应的信息网络Ni就是该问题要找的信息网络。本文主要对该问题给出了一个2-近似算法和一个7/4-渐进近似算法，并进行了程序实现。
本文主要由以下四部分构成:
在第一章中，给出问题提出的背景以及目前一些成果和进展;
在第二章中，叙述一些本文要用到的预备知识;
在第三章中，给出最小支撑树形图问题和装箱问题及相关算法;
在第四章中，讨论信息网络的构建问题，并设计算法进行求解。