上周在巴塞罗那TechEd的代码堵塞期间，Witalij Rudnicki向我扔了手套，开始挑战使用HANA的图形功能来解决"骑士之旅"问题。

这个问题最好概括如下："在棋盘上找到一个骑士棋子的连续移动，这样骑士就可以访问每一个方格正好一次"。

图论

我们可以建模棋盘就像一个以正方形为顶点，以所有可能的移动为边的图。

通过使用这种抽象，问题实际上归结为更一般的哈密顿路径问题的一个特例，它基本上是搜索一条路径，该路径恰好遍历一个图的所有顶点一次。

图形引擎

HANA具有处理图形的内置支持。到目前为止，它有以下主要特点：

存储和表示图形（基本上你需要一个顶点和一个边表，然后你可以用它们创建一个所谓的"工作区"）。在图上运行一些简单的算法（邻域、最短路径、连通组件等）。基于openCypher查询语言执行查询。使用专用GraphScript语言编写存储过程。

为了解决这个问题，我将存储过程与图形表示一起使用。

棋盘

第一步是将棋盘生成为图形。我们将标记从1到8的行和从A到H的列：

为了存储图形，手机自助建站，我将数据模型定义为：

我不想手动定义板，所以我编写了一个基于输入大小为我生成它的过程：

创建过程后，我可以简单地调用它来填充我的表：

WebIDE有一个内置的图形查看器提供了一个非常好的象棋棋盘可视化：

最后，我定义了一个表类型来表示路径：

天真的方法

我想到的第一个想法是尝试通过回溯来解决它。我决定不这样做，因为它太慢了。

香草回溯具有指数渐近时间复杂度。在我们的图中，每个节点可能有8个邻居，我们必须找到一条64节点的长路径，因此需要（略少于）8^64个步骤来完成整个算法。

当然，如果我们在找到第一个解时停止，速度会更快，但我还是决定一定有更好的解决办法

贪心算法

想了一会儿，我决定应该可以用一个贪婪的算法和一个合适的启发式选择来找到一个解决方案。在与GraphScript语言进行了一点斗争之后，我编写了以下程序：

不幸的是，这种方法失败得很惨，结果很平庸：

在我看来，这个问题就像一旦板的下半部分几乎满了，骑士就进入了死胡同。为了防止这种情况发生，我尝试了另一种启发式方法：总是尽可能靠近棋盘的中心。

我设想骑士会围绕棋盘的中心旋转。我没有意识到的是，这种方法基本上会切断董事会的一个角落，导致骑士被困在一个角落：

看到我的启发式不起作用，我决定读一点关于这个主题的文献。

沃恩斯多夫规则

来源：松鼠，道格拉斯，和保罗《骑士之旅的沃恩斯多夫规则算法》（1996）

读了几篇论文后，我发现我非常接近一个正确的解决方案。我搜索的启发式方法是总是选择下一个节点作为度最小的节点。也就是说，我们选择一个节点，它有最小数量的未访问邻居。

基本上，这将产生与上图完全相反的结果：首先访问板的边缘，然后访问中心：

我终于得到了一个解决方案！但我不喜欢这种启发式的是，当我们必须决定下一个节点时，有两个节点的得分完全相同，大数据问题，我们总是取第一个节点。在文献中，他们通常随机抽取一个，但GraphScript中没有随机函数。

有时这种启发式可能无法产生结果（虽然我从未遇到过这种情况），所以我想进一步改进。

波尔的平局突破

来源：波尔，Ira寻找汉密尔顿路径和骑士之旅的一种方法。"（1967）。

打破联系的一种可能方法是在候选节点上重复应用选择机制。因为我无法使用GraphScript编写递归调用，所以我决定采用单级中断：

首先根据Warnsdorff规则查找所有候选节点。如果只有一个候选者，请选择该候选者。否则，计算每个候选对象的最小邻接度并选择值最小的邻接度。在这一点上，数据无价，我们可以再次达到平局，所以我们只选择第一个（这将通过递归解决-除了完全对称的安排）。

运行它似乎产生了预期的结果：

我仍然不喜欢这个解决方案，因为即使是非对称的安排，我们仍然必须采取随机选择（由于缺乏递归）

Roth的平局突破

来源：Ganzfried，Sam."骑士之旅的一个简单算法"（2004）。

平局突破的另一个想法是根据与电路板中心的距离从候选节点中选择（取与中心距离最大的节点）：

令人惊讶的是，在同一个起点上运行这个程序产生的结果与波尔的平局（大多数时候）是一样的。

Bloopers

我不想给人一个错误的印象，让人们认为一切都很顺利。我实际上遇到了一些错误和限制，企业信息化应用系统，这让我浪费了几个小时的时间：