0

假设我们有 9 个点。每个人只能参观一次。路径，例如从左上角到右下角，也是允许的。谁能提供一种算法来计算屏幕锁定模式的最长路径？

4

5 回答 5

1

您需要先提供距离指标。
让我们假设以下内容：
- 水平或垂直移动可以长 1 一步或 2 两步。
- 对角线，一步长度为 1.41（2 的平方根，勾股定理）或两步长度为 2.83（8 的平方根）。
- 就像国际象棋中的骑士一样，您的长度为 2.24（5 的平方根）

所以现在你需要找到这个可能步骤的最大总和。如果您使用上面提到的“最佳优先搜索”，那将很麻烦，因为最长的路径并不总是选择第一个最佳选项。
对于下图：
123
456
789
一个选项是 519467382，其长度约为 17.7
因此尝试计算上述所有选项可能更安全，但您也可以记住，由于对称性，您需要计算长度仅用于起始节点 1、2 和 5。其他节点将给出相同的结果，因此无需计算....

于 2014-11-17T18:07:11.670 回答
0

It is similar to the travelling salesman problem (TSP), but instead of the shortest path you look for the longest one, and the path is not closed.

For the 9 points case I wouldn't be afraid of just trying all possible paths since there are just 9! = 362880 of them. And this number could potentially be reduced since 3 by 3 regular grid is highly symmetrical.

Another approach (since the path is not closed) could be doing a best-first search from a node with "best" being the one that has the longest path so far. You'll do this from each node remembering the longest path of them all. But this is just a quick thought and I have no proof this would actually work.

于 2014-11-17T10:13:52.817 回答
0

我手动计算，我得到的最长的是 561943728，长度为 17.76（两个最近点之间的距离为 1 个单位）。如果有人能打败这个然后展示你的模式！

于 2020-05-11T14:19:00.530 回答
0

基本上是一个 TSP 问题，经过一些修改，不允许跨过未访问过的点。

3x3 很容易被暴力破解。对于稍微大一点的问题，修改后的 TSP 动态规划算法也可以在 {O(2^n*n^2)} 时间内工作。

https://repl.it/@farteryhr/AndroidLockscreen#index.js

3x3：17.779271744364845

591643728
573461928
591827346
537281946
573829164
519283764
537649182
519467382

4x4：45.679014611640504（0123456789abcdef）

92d6c3875e1f4b0a
68793c2d5e1f4b0a
92d6c3875b4f1e0a
68793c2d5b4f1e0a
a1e5f0b46d2c7839
5b4a0f1e6d2c7839
a1e5f0b4687c2d39
5b4a0f1e687c2d39
a4b5f0e19783d2c6
5e1a0f4b9783d2c6
a4b5f0e192d387c6
5e1a0f4b92d387c6
9786c3d2a4b0e1f5
6d293c78a4b0e1f5
9786c3d2a1e0b4f5
6d293c78a1e0b4f5

5x5: 91.8712723085273 (0123456789abcdefghijklmno)

ci6o0j5dbea9f8g4k3m1n7l2h
cg8k4f9bdae5j6i0o1m3l7n2h
ci6o0n1h7m2l3g8k4fe5jb9ad
c8g4k3l7h2m1n6i0o5ef9bjad
cg8k4l3h7m2n1i6o0ja9fd5eb
c6i0o1n7h2m3l8g4k9aj5dfeb
c8g4k9fdbeaj5i6o0n2l3h1m7
c6i0o5jbdaef9g8k4l2n1h3m7
于 2020-07-31T14:07:33.380 回答
-1

最长的路径是 567 348 192，大约是 18.428

至少有 8 种这样的模式，另一种是 567 381 932（遍历长度 18.428）。在这些图案周围放置一个镜像，你会从一个这样的图案中得到 4 个图案。

于 2016-11-10T11:21:14.563 回答