排序方式: 共有4条查询结果,搜索用时 15 毫秒
1
1.
Computational Optimization and Applications - It has been shown that a global minimizer of a smooth determinant of a matrix function corresponds to the largest cycle of a graph. When it exists,... 相似文献
2.
Pouya Baniasadi Vladimir Ejov Jerzy A. Filar Michael Haythorpe Serguei Rossomakhine 《Mathematical Programming Computation》2014,6(1):55-75
We present a polynomial complexity, deterministic, heuristic for solving the Hamiltonian cycle problem (HCP) in an undirected graph of order $n$ . Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that the heuristic is successful even in cases where such cycles are extremely rare, and it also performs very well on all HCP instances of large graphs listed on the TSPLIB web page. The heuristic owes its name to a visualisation of its iterations. All vertices of the graph are placed on a given circle in some order. The graph’s edges are classified as either snakes or ladders, with snakes forming arcs of the circle and ladders forming its chords. The heuristic strives to place exactly $n$ snakes on the circle, thereby forming a Hamiltonian cycle. The Snakes and Ladders Heuristic uses transformations inspired by $k$ -opt algorithms such as the, now classical, Lin–Kernighan heuristic to reorder the vertices on the circle in order to transform some ladders into snakes and vice versa. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time if no improvement is made in $n^3$ major iterations. 相似文献
3.
In this paper, we propose a new hybrid algorithm for the Hamiltonian cycle problem by synthesizing the Cross Entropy method
and Markov decision processes. In particular, this new algorithm assigns a random length to each arc and alters the Hamiltonian
cycle problem to the travelling salesman problem. Thus, there is now a probability corresponding to each arc that denotes
the probability of the event “this arc is located on the shortest tour.” Those probabilities are then updated as in cross
entropy method and used to set a suitable linear programming model. If the solution of the latter yields any tour, the graph
is Hamiltonian. Numerical results reveal that when the size of graph is small, say less than 50 nodes, there is a high chance
the algorithm will be terminated in its cross entropy component by simply generating a Hamiltonian cycle, randomly. However,
for larger graphs, in most of the tests the algorithm terminated in its optimization component (by solving the proposed linear
program). 相似文献
4.
We present an algorithm to find the determinant and its first and second derivatives of a rank-one corrected generator matrix of a doubly stochastic Markov chain. The motivation arises from the fact that the global minimiser of this determinant solves the Hamiltonian cycle problem. It is essential for algorithms that find global minimisers to evaluate both first and second derivatives at every iteration. Potentially the computation of these derivatives could require an overwhelming amount of work since for the Hessian N 2 cofactors are required. We show how the doubly stochastic structure and the properties of the objective may be exploited to calculate all cofactors from a single LU decomposition. 相似文献
1