共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
Differential A* 总被引:1,自引:0,他引:1
A* graph search effectively computes the optimal solution path from start nodes to goal nodes in a graph, using a heuristic function. In some applications, the graph may change slightly in the course of its use and the solution path then needs to be updated. Very often, the new solution will differ only slightly from the old. Rather than perform the full A* on the new graph, we compute the necessary OPEN nodes from which the revised solution can be obtained by A*. In this "Differential A*" algorithm, the graph topology, transition costs, or start/goals may change simultaneously. We develop the algorithm and discuss when it gives an improvement over simply reapplying A*. We briefly discuss an application to robot path planning in configuration space, where such graph changes naturally arise. 相似文献
3.
In recent years, various heuristic optimization methods have been developed. Many of these methods are inspired by swarm behaviors in nature, such as particle swarm optimization (PSO), firefly algorithm (FA) and cuckoo optimization algorithm (COA). Recently introduced COA, has proven its excellent capabilities, such as faster convergence and better global minimum achievement. In this paper a new approach for solving graph coloring problem based on COA was presented. Since COA at first was presented for solving continuous optimization problems, in this paper we use the COA for the graph coloring problem, we need a discrete COA. Hence, to apply COA to discrete search space, the standard arithmetic operators such as addition, subtraction and multiplication existent in COA migration operator based on the distance's theory needs to be redefined in the discrete space. Redefinition of the concept of the difference between the two habitats as the list of differential movements, COA is equipped with a means of solving the discrete nature of the non-permutation. A set of graph coloring benchmark problems are solved and its performance is compared with some well-known heuristic search methods. The obtained results confirm the high performance of the proposed method. 相似文献
4.
Some of the current best conformant probabilistic planners focus on finding a fixed length plan with maximal probability. While these approaches can find optimal solutions, they often do not scale for large problems or plan lengths. As has been shown in classical planning, heuristic search outperforms bounded length search (especially when an appropriate plan length is not given a priori). The problem with applying heuristic search in probabilistic planning is that effective heuristics are as yet lacking.In this work, we apply heuristic search to conformant probabilistic planning by adapting planning graph heuristics developed for non-deterministic planning. We evaluate a straight-forward application of these planning graph techniques, which amounts to exactly computing a distribution over many relaxed planning graphs (one planning graph for each joint outcome of uncertain actions at each time step). Computing this distribution is costly, so we apply Sequential Monte Carlo (SMC) to approximate it. One important issue that we explore in this work is how to automatically determine the number of samples required for effective heuristic computation. We empirically demonstrate on several domains how our efficient, but sometimes suboptimal, approach enables our planner to solve much larger problems than an existing optimal bounded length probabilistic planner and still find reasonable quality solutions. 相似文献
5.
Misra Rajiv Mandal Chittaranjan 《Parallel and Distributed Systems, IEEE Transactions on》2010,21(3):292-302
A minimum connected dominating set (MCDS) is used as virtual backbone for efficient routing and broadcasting in ad hoc sensor networks. The minimum CDS problem is NP-complete even in unit disk graphs. Many heuristics-based distributed approximation algorithms for MCDS problems are reported and the best known performance ratio has (4.8+ln 5). We propose a new heuristic called collaborative cover using two principles: 1) domatic number of a connected graph is at least two and 2) optimal substructure defined as subset of independent dominator preferably with a common connector. We obtain a partial Steiner tree during the construction of the independent set (dominators). A final postprocessing step identifies the Steiner nodes in the formation of Steiner tree for the independent set of G. We show that our collaborative cover heuristics are better than degree-based heuristics in identifying independent set and Steiner tree. While our distributed approximation CDS algorithm achieves the performance ratio of (4.8+ln 5){rm opt} + 1.2, where {rm opt} is the size of any optimal CDS, we also show that the collaborative cover heuristic is able to give a marginally better bound when the distribution of sensor nodes is uniform permitting identification of the optimal substructures. We show that the message complexity of our algorithm is O(nDelta^{2} ), Delta being the maximum degree of a node in graph and the time complexity is O(n). 相似文献
6.
An Adaptive Partitioning Scheme for Sleep Scheduling and Topology Control in Wireless Sensor Networks 总被引:1,自引:0,他引:1
Ding Yong Wang Chen Xiao Li 《Parallel and Distributed Systems, IEEE Transactions on》2009,20(9):1352-1365
This paper presents an adaptive partitioning scheme of sensor networks for node scheduling and topology control with the aim of reducing energy consumption. Our scheme partitions sensors into groups such that a connected backbone network can be maintained by keeping only one arbitrary node from each group in active status while putting others to sleep. Unlike previous approaches that partition nodes geographically, our scheme is based on the measured connectivity between pairwise nodes and does not depend on nodes' locations. In this paper, we formulate node scheduling with topology control as a constrained optimal graph partition problem, which is NP-hard, and propose a Connectivity-based Partition Approach (CPA), which is a distributed heuristic algorithm, to approximate a good solution. We also propose a probability-based CPA algorithm to further save energy. CPA can ensure K-vertex connectivity of the backbone network, which achieves the trade-off between saving energy and preserving network quality. Moreover, simulation results show that CPA outperforms other approaches in complex environments where the ideal radio propagation model does not hold. 相似文献
7.
Most of the recent heuristics for the graph coloring problem start from an infeasible k-coloring (adjacent vertices may have the same color) and try to make the solution feasible through a sequence of color exchanges. In contrast, our approach (called FOO-PARTIALCOL), which is based on tabu search, considers feasible but partial solutions and tries to increase the size of the current partial solution. A solution consists of k disjoint stable sets (and, therefore, is a feasible, partial k-coloring) and a set of uncolored vertices. We introduce a reactive tabu tenure which substantially enhances the performance of both our heuristic as well as the classical tabu algorithm (called TABUCOL) proposed by Hertz and de Werra [Using tabu search techniques for graph coloring, Computing 1987;39:345–51]. We will report numerical results on different benchmark graphs and we will observe that FOO-PARTIALCOL, though very simple, outperforms TABUCOL on some instances, provides very competitive results on a set of benchmark graphs which are known to be difficult, and outperforms the best-known methods on the graph flat300_28_0. For this graph, FOO-PARTIALCOL finds an optimal coloring with 28 colors. The best coloring achieved to date uses 31 colors. Algorithms very close to TABUCOL are still used as intensification procedures in the best coloring methods, which are evolutionary heuristics. FOO-PARTIALCOL could then be a powerful alternative. In conclusion FOO-PARTIALCOL is one of the most efficient simple local search coloring methods yet available. 相似文献
8.
9.
Caetano TS Caelli T Schuurmans D Barone DA 《IEEE transactions on pattern analysis and machine intelligence》2006,28(10):1646-1663
This paper describes a novel solution to the rigid point pattern matching problem in Euclidean spaces of any dimension. Although we assume rigid motion, jitter is allowed. We present a noniterative, polynomial time algorithm that is guaranteed to find an optimal solution for the noiseless case. First, we model point pattern matching as a weighted graph matching problem, where weights correspond to Euclidean distances between nodes. We then formulate graph matching as a problem of finding a maximum probability configuration in a graphical model. By using graph rigidity arguments, we prove that a sparse graphical model yields equivalent results to the fully connected model in the noiseless case. This allows us to obtain an algorithm that runs in polynomial time and is provably optimal for exact matching between noiseless point sets. For inexact matching, we can still apply the same algorithm to find approximately optimal solutions. Experimental results obtained by our approach show improvements in accuracy over current methods, particularly when matching patterns of different sizes. 相似文献
10.
Planning graphs have been shown to be a rich source of heuristic information for many kinds of planners. In many cases, planners must compute a planning graph for each element of a set of states, and the naive technique enumerates the graphs individually. This is equivalent to solving a multiple-source shortest path problem by iterating a single-source algorithm over each source.We introduce a data-structure, the state agnostic planning graph, that directly solves the multiple-source problem for the relaxation introduced by planning graphs. The technique can also be characterized as exploiting the overlap present in sets of planning graphs. For the purpose of exposition, we first present the technique in deterministic (classical) planning to capture a set of planning graphs used in forward chaining search. A more prominent application of this technique is in conformant and conditional planning (i.e., search in belief state space), where each search node utilizes a set of planning graphs; an optimization to exploit state overlap between belief states collapses the set of sets of planning graphs to a single set. We describe another extension in conformant probabilistic planning that reuses planning graph samples of probabilistic action outcomes across search nodes to otherwise curb the inherent prediction cost associated with handling probabilistic actions. Finally, we show how to extract a state agnostic relaxed plan that implicitly solves the relaxed planning problem in each of the planning graphs represented by the state agnostic planning graph and reduces each heuristic evaluation to counting the relevant actions in the state agnostic relaxed plan. Our experimental evaluation (using many existing International Planning Competition problems from classical and non-deterministic conformant tracks) quantifies each of these performance boosts, and demonstrates that heuristic belief state space progression planning using our technique is competitive with the state of the art. 相似文献
11.
基于蜂窝结构的混合无线传感器网络(HWSN)覆盖优化算法HWSNBCS存在移动节点平均移动距离较大的问题,为此,提出一种改进的HWSN覆盖优化算法IHWSNBCS。寻找移动传感器节点初始位置与通过HWSNBCS算法得出的候选目标位置之间的最优匹配,将移动节点移动距离之和最小化问题转化为二分图最优匹配问题,利用带权二分图匹配算法KM寻找该匹配问题的最优解,从而得到移动节点最终的目标位置,并实现对HWSNBCS算法移动节点平均移动距离的进一步优化。实验结果表明,IHWSNBCS算法在取得与HWSNBCS算法相同网络覆盖率的前提下,移动节点的平均移动距离减少幅度达到38.87%~43.28%,单个移动节点的最大移动距离减少幅度达到22.65%~66.58%,降低了系统因重新部署移动传感器节点所产生的能耗以及单个传感器节点因能量耗尽而失效的概率,从而延长了网络生命周期,同时,IHWSNBCS的ΔCov-Dist性能指标为HWSNBCS算法的1.64~1.76倍,表明移动节点移动相同距离时IHWSNBCS算法的网络覆盖率提升更大。 相似文献
12.
We consider a hybrid TDMA/CDMA wireless sensor network (WSN) and quantitatively investigate the energy efficiency obtained by combining adaptive power/rate control with time-domain scheduling. The energy efficiency improvement is carried out with respect to interfering-cluster scheduling, intra-cluster node scheduling, and transmission powers and times (durations) control (PTC) for individual nodes. The interfering-cluster scheduling is formulated as a vertex-coloring problem, which can be solved efficiently using existing numerical algorithms in graph theory. For the node scheduling problem, we present a heuristic algorithm, which iteratively searches for the best schedule in such a way that the energy consumption keeps decreasing after every iteration. Compared with the exponentially complicated exhaustive search algorithm, this heuristic algorithm has polynomial computing complexity and can provide optimal solutions in the most simulated cases. For the transmission power/time control, two simplified PTC schemes, namely, PTC-UT and PTC-USG, are proposed and studied based on our previous optimization work PTC-IPT. We show that PTC-UT and PTC-USG provide comparable energy efficiency to PTC-IPT at only half of its complexity. Numerical examples are used to validate our findings. 相似文献
13.
14.
Graph classification has been showing critical importance in a wide variety of applications, e.g. drug activity predictions
and toxicology analysis. Current research on graph classification focuses on single-label settings. However, in many applications,
each graph data can be assigned with a set of multiple labels simultaneously. Extracting good features using multiple labels
of the graphs becomes an important step before graph classification. In this paper, we study the problem of multi-label feature
selection for graph classification and propose a novel solution, called gMLC, to efficiently search for optimal subgraph features
for graph objects with multiple labels. Different from existing feature selection methods in vector spaces that assume the
feature set is given, we perform multi-label feature selection for graph data in a progressive way together with the subgraph
feature mining process. We derive an evaluation criterion to estimate the dependence between subgraph features and multiple
labels of graphs. Then, a branch-and-bound algorithm is proposed to efficiently search for optimal subgraph features by judiciously
pruning the subgraph search space using multiple labels. Empirical studies demonstrate that our feature selection approach
can effectively boost multi-label graph classification performances and is more efficient by pruning the subgraph search space
using multiple labels. 相似文献
15.
We consider a monthly crew scheduling problem with preferential bidding in the airline industry. We propose a new methodology based on a graph coloring model and a tabu search algorithm for determining if the problem contains at least one feasible solution. We then show how to combine the proposed approach with a heuristic sequential scheduling method that uses column generation and branch-and-bound techniques. 相似文献
16.
17.
Bi-objective graph coloring problem (BOGCP) is a generalized version in which the number of colors used to color the vertices of a graph and the corresponding penalty which incurs due to coloring the end-points of an edge with the same color are simultaneously minimized. In this paper, we have analyzed the graph density, the interconnection between high degree nodes of a graph, the rank exponent of the standard benchmark input graph instances and observed that the characterization of graph instances affects on the behavioral quality of the solution sets generated by existing heuristics across the entire range of the obtained Pareto fronts. We have used multi-objective evolutionary algorithm (MOEA) to obtain improved quality solution sets with the problem specific knowledge as well as with the embedded heuristics knowledge. To establish this fact for BOGCP, hybridization approach is used to construct recombination operators and mutation operators and it is observed from empirical results that the embedded problem specific knowledge in evolutionary operators helps to improve the quality of solution sets across the entire Pareto front; the nature of problem specific knowledge differentiates the quality of solution sets. 相似文献
18.
在分区内存体系结构中,如何尽可能少地插入片选指令是研究的热点。根据该问题的特点,构建了片选优化的图划分模型,并在该模型的基础上,提出了一种二阶段启发式搜索算法求解该问题。该算法首先根据节点自身的大小与图中分区大小快速获得一个初始可行解,然后在该可行解基础上利用节点之间边的权值和分区之间的权值作为启发式参数,搜索更优的解。通过对MiBench用例集和实际嵌入式系统的测试,验证了该模型及相应启发式算法的有效性,相对于VPAB算法,平均优化率达到37.99%,略优于成熟的商用编译器PICC,大幅度减少了片选指令的数量。 相似文献
19.
Imtiaz AhmadAuthor Vitae 《Computers & Electrical Engineering》2003,29(2):327-356
To minimize the area of the combinational circuit, required to realize a finite state machine (FSM), an efficient assignment of states of the FSM to a set of binary codes is required. As to find an optimal state assignment is NP-hard, therefore heuristic approaches have been taken. One approach generates an adjacency graph from the FSM model and then tries to embed the adjacency graph onto a hypercube with an objective to minimize the cost of mapping. However, hypercube embedding itself is an NP-complete problem. In this paper we present a solution to the hypercube embedding problem by designing a new technique, designated as HARD, that is a hybrid combination of non-linear programming method and a local search. We have transformed our problem from discrete space to continuous space and have applied logarithmic barrier function method, that in turn uses gradient projection approach to minimize the objective function. Each iteration of the gradient projection method produces a valid solution. Local search is performed around solution to improve its quality by using a Kernighan-Lin style algorithm. Two distributed algorithms for the HARD, have also been designed and implemented on network of workstations under message passing interface, to speed up the search. We have carried out a large number of experiments to determine the efficiency of the HARD in terms of solution quality over many other techniques, and have obtained very promising results. 相似文献
20.
This paper introduces a tabu search heuristic for a production scheduling problem with sequence-dependent and time-dependent
setup times on a single machine. The problem consists in scheduling a set of dependent jobs, where the transition between
two jobs comprises an unrestricted setup that can be performed at any time, and a restricted setup that must be performed
outside of a given time interval which repeats daily in the same position. The setup time between two jobs is thus a function
of the completion time of the first job. The tabu search heuristic relies on shift and swap moves, and a surrogate objective
function is used to speed-up the neighborhood evaluation. Computational experiments show that the proposed heuristic consistently
finds better solutions in less computation time than a recent branch-and-cut algorithm. Furthermore, on instances where the
branch-and-cut algorithm cannot find the optimal solution, the heuristic always identifies a better solution. 相似文献