We present a memetic algorithm (\maa) approach for finding a Hamiltonian
cycle in a Hamiltonian graph. The \ma is based on a proven approach to the
Asymmetric Travelling Salesman Problem (\atspp) that, in this contribution, is
boosted by the introduction of more powerful local searches. Our approach also
introduces a novel technique that sparsifies the input graph under
consideration for Hamiltonicity and dynamically augments it during the search.
Such a combined heuristic approach helps to prove Hamiltonicity by finding a
Hamiltonian cycle in less time. In addition, we also employ a recently
introduced polynomial-time reduction from the \hamcyc to the Symmetric \tsp,
which is based on computing the transitive closure of the graph. Although our
approach is a metaheuristic, i.e., it does not give a theoretical guarantee for
finding a Hamiltonian cycle, we have observed that the method is successful in
practice in verifying the Hamiltonicity of a larger number of instances from
the \textit{Flinder University Hamiltonian Cycle Problem Challenge Set}
(\fhcpsc), even for the graphs that have large treewidth. The experiments on
the \fhcpscc instances and a computational comparison with five recent
state-of-the-art baseline approaches show that the proposed method outperforms
those for the majority of the instances in the \fhcpsc.

我们提出了一种基于变异算法的方法，用于在 Hamilton 图中找到 Hamilton 循环。该方法基于解决非对称旅行推销员问题的已有方法，通过引入更强大的局部搜索进行优化。我们的方法还引入了一种策略，对所考虑的 Hamilton 图进行稀疏化处理，并在搜索过程中进行动态增加。这种综合的启发式方法有助于在较短时间内找到 Hamilton 循环以证明 Hamiltonicity。此外，我们还使用了最近提出的从 Hamilton 循环到对称旅行推销员问题的多项式时间归约方法，基于计算图的传递闭包。尽管我们的方法是元启发式算法，即不能给出找到 Hamilton 循环的理论保证，但我们观察到该方法在实践中成功验证了 Flinder 大学 Hamilton 循环问题挑战集（FHCPSC）中更多实例的 Hamiltonicity，即使对于具有大树宽的图形也是如此。在 FHCPSC 实例上的实验证明以及与最近的五种最先进的基准方法的计算比较表明，所提出的方法在 FHCPSC 的大多数实例中优于其他方法。

在哈密顿图中寻找哈密顿回路的记忆算法

A Memetic Algorithm To Find a Hamiltonian Cycle in a Hamiltonian Graph

Clustering aims to group unlabelled samples based on their similarities. It
has become a significant tool for the analysis of high-dimensional data.
However, most of the clustering methods merely generate pseudo labels and thus
are unable to simultaneously present the similarities between different
clusters and outliers. This paper proposes a new framework called
High-dimensional Clustering onto Hamiltonian Cycle (HCHC) to solve the above
problems. First, HCHC combines global structure with local structure in one
objective function for deep clustering, improving the labels as relative
probabilities, to mine the similarities between different clusters while
keeping the local structure in each cluster. Then, the anchors of different
clusters are sorted on the optimal Hamiltonian cycle generated by the cluster
similarities and mapped on the circumference of a circle. Finally, a sample
with a higher probability of a cluster will be mapped closer to the
corresponding anchor. In this way, our framework allows us to appreciate three
aspects visually and simultaneously - clusters (formed by samples with high
probabilities), cluster similarities (represented as circular distances), and
outliers (recognized as dots far away from all clusters). The experiments
illustrate the superiority of HCHC.

本文提出了一种新的聚类框架，结合全局结构和局部结构解决聚类算法中伪标签生成和异常点检测问题，扩展了传统聚类方法的应用领域。实验证明，该方法表现优异。

高维空间哈密顿圈聚类

High-dimensional Clustering onto Hamiltonian Cycle

We propose UTSP, an unsupervised learning (UL) framework for solving the
Travelling Salesman Problem (TSP). We train a Graph Neural Network (GNN) using
a surrogate loss. The GNN outputs a heat map representing the probability for
each edge to be part of the optimal path. We then apply local search to
generate our final prediction based on the heat map. Our loss function consists
of two parts: one pushes the model to find the shortest path and the other
serves as a surrogate for the constraint that the route should form a
Hamiltonian Cycle. Experimental results show that UTSP outperforms the existing
data-driven TSP heuristics. Our approach is parameter efficient as well as data
efficient: the model takes $\sim$ 10\% of the number of parameters and $\sim$
0.2\% of training samples compared with reinforcement learning or supervised
learning methods.

我们提出了 UTSP，这是一个用于解决旅行推销员问题（TSP）的无监督学习框架，使用基于图神经网络（GNN）的代理损失。该方法在参数效率和数据效率方面优于目前的数据驱动 TSP 启发式方法。