排序方式: 共有10条查询结果,搜索用时 15 毫秒
1
1.
《国际计算机数学杂志》2012,89(3-4):207-220
The number of internal stability or independence number of an undirected graph has many important applications. Computationally it belongs to the class of intractable problems known as NP-Hard. In this paper we develop a tree search algorithm to determine the ndependence number of an undirected graph. Extensive computational experience on 2400 randomly generated graphs ranging from 20% to 90% densities and from 50 to 200 vertice has shown that the proposed algorithm is very effective. 相似文献
2.
David Rutten 《Architectural Design》2013,83(2):132-135
A graduate in architecture and urbanism from TU Delft, David Rutten works with software company Robert McNeel & Associates (RMN). The developer of Grasshopper®, he was recently awarded the ACADIA 2012 award for innovative research. The Galapagos plug-in, which Rutten has developed for Grasshopper®, implements two generic solvers (one using a genetic algorithm and one using a simulated annealing algorithm). A generic solver will find a solution to a problem that can be expressed in a mathematical way; however, as he explains here, while these solutions may not be exact, they will be very good. 相似文献
3.
粮库PWSN部署中NP-Hard问题的研究 总被引:1,自引:1,他引:0
以无线传感器网络在粮库中的应用为例,将传感器节点部署中出现未覆盖区域问题归属为NP-Hard 问题.结合近似算法、Bidding协议、Voronoi diagrams等方法,对粮库PwsN部署中的NP-Hard问题进行了较深入的研究,对解决粮库无线传感器网络的覆盖问题提出了新思路. 相似文献
4.
5.
TSP问题是一个典型的组合优化问题,并且也是一个NP难题,其可能的路径总数与城市数目n成指数型增长,一般很难精确地求出其最优解。这里对BP问题提出了一种改进的遗传算法,通过对遗传算法的评估函数、交叉和变异方法以及参数选择等方面的分析和修改,构造了一种自适应函数以及交叉、变异方法。通过对CHN144的测试,实验结果证明此处提出的方法能更有效的求解TSP问题。 相似文献
6.
Sensor network localization problem is to determine the position of the sensor nodes in a network given pairwise distance measurements. Such problem can be formulated as a quartic polynomial minimization via the least squares method. This paper presents a canonical duality theory for solving this challenging problem. It is shown that the nonconvex minimization problem can be reformulated as a concave maximization dual problem over a convex set in a symmetrical matrix space, and hence can be solved efficiently by combining a general (linear or quadratic) perturbation technique with existing optimization techniques. Applications are illustrated by solving some relatively large-scale problems. Our results show that the general sensor network localization problem is not NP-hard unless its canonical dual problem has no solution in its positive definite domain. Fundamental ideas for solving general NP-hard problems are discussed. 相似文献
7.
一类弱集合覆盖问题的近似算法 总被引:3,自引:1,他引:3
在近似算法领域,集合覆盖(Set Cover)是研究的比较早和比较透彻的问题之一.该文提出了一类与集合覆盖很相似的问题:集合击中和弱集合b-覆盖,并且给出了解决它们的近似算法,还证明了它们的不可近似性. 相似文献
8.
9.
宋晓晨 《黑龙江工程学院学报》2007,21(3):36-40
集合覆盖问题是一个典型的NP难题,在实际中有着广泛的应用.提出一种求解该问题的改进遗传算法,通过对种群中染色体进行启发式改进和遗传参数的选取,求得最优解. 相似文献
10.
利用对偶理论,将求解双层线性规划问题转化为求解一个与之等价的单层问题,通过求解一系列线性规划问题,提出了一种求解双层线性规划局部最优解的算法,并举例说明了算法的求解过程。 相似文献
1