排序方式: 共有38条查询结果,搜索用时 62 毫秒
1.
设G=(V,E)是一个无向连通图,每一条边e和每个顶点v都有一个非负的权重l(e)和w(v);传统的p-median是指在顶点集合中选出p个顶点,使得其它顶点到这p个顶点的赋权距离和最小。该文考虑带有某些约束的这类问题,要求所选出的p个顶点是连通的,也即由这p个顶点所导出的子图是连通的,称为连通p-median问题。该文给出了3-cactus图上的连通p-median问题的一个O(pn)的算法。 相似文献
2.
无线传感器网络是一种自组织网络,其自组织性以及节点能量受限的特点,使得如何设计路由协议以达到既保证数据传输的完整性又最大限度延长网络寿命变得至关重要。该文提出了一种新的路由机制来延长网络寿命,适合于静态的网络。最后通过模拟仿真说明了改进的路由协议比LEACH协议在延长网络寿命上有很大的改进。 相似文献
3.
最快路是在最短的时间内把信息从源发送到目的端的路.该文采用标签设定算法,通过修改原网络,得到一个新网络,使得新网络中快速路的子路也是快速路.该文使用动态规划的方法,给出了所有顶点对之间最快路的算法. 相似文献
4.
网络选址问题是研究在给定的网络中,如何放置设施,使得总的花费最小.其反问题可描述为:若设施在网络中的位置已经确定,如何在给定的费用约束下改进网络中的参数,使得在改进后的网络中,距设施最远的节点到设施的距离最小.该文对树网络结构下此类问题的算法做出改进,得到了O(n2)的算法. 相似文献
5.
陈光亭 《杭州电子科技大学学报》2001,21(1):1-6
本文首先提出一种有向网络中点对间加权约束的最小用连接问题,当点对数为1时即为约束最短路问题,因此这是一个NP-C问题,本文设法在原有网络基础上构造出一个新的2维网络,然后利用约束最短路问题的算法给出一个点对数为2时的多项式时间近似方案(PTAS)。 相似文献
6.
研究了一类单台机上带有库存约束的排序问题,目标函数是极小化加权完工时间总和。针对问题,首先证明了问题是NP-困难的,接着给出贪婪算法,证明了该算法的最坏情况界是无穷大,但随机试验表明算法的平均性能是令人满意的。 相似文献
7.
不可靠网络上最可靠广播源问题是网络可靠性问题的一种。该文讨论了星形网络中最可靠广播源问题与最可靠双广播源问题,并针对这两个问题分别给出了两个多项式时间算法。 相似文献
8.
该文针对路由协议在实际中的应用及存在的问题,进一步提出了带惩罚函数的最短路由协议。分析对比证明PSPRP算法与一般最短路由算法相比,具有能量均衡且低延时的特点,实验表明,该算法能使网络均衡,从而有效的延长网络寿命,获得更好的性能。 相似文献
9.
该文首次讨论了三维空间中无线传感器双层网络上中继器放置问题。在一定的假设条件下,运用区域划分的思想,对单覆盖单连通、双覆盖双连通问题进行研究,设计了近似算法,并给出常数性能比,扩展了三维空间中无线传感器网络的研究领域,为无线传感器网络的进一步研究提供了重要思想。 相似文献
10.