6

我正在尝试解决哈密顿路径问题的略微修改版本。它的修改在于将起点和终点提供给我们，而不是确定解决方案是否存在，我们想要找到解决方案的数量（可能是 0）。

该图以二维数组的形式提供给我们，节点是数组的元素。此外，我们只能水平或垂直移动，不能沿对角线移动。不用说，我们不能从一个城市去两个城市，因为要这样做，我们需要访问一个城市两次。

我写了一个蛮力解决方案，在每个节点上尝试所有 4 个（边缘节点为 3 个或 2 个）可能的移动，然后计算解决方案的数量（当它达到目标并且也看到所有其他节点时），但是它在中等大小的输入（比如 7x7 数组）上运行了荒谬的时间。

我也想过使用双向搜索，因为我们知道目标，但这并没有真正帮助，因为我们不仅希望边缘相遇，我们还希望确保所有节点都已被访问。此外，当两个边缘之间的所有节点都用尽时，它们可能会以无法连接的方式结束。

我觉得有一些我不知道的东西让我只有一个蛮力解决方案。我知道问题本身是 NP 完全的，但我想知道是否对蛮力有任何改进。有人可以提出其他建议吗？

- 编辑 -

我提到使用双向搜索并没有真正的帮助，我想澄清我为什么这么认为。考虑一个 2x3 图形，左上角和右下角节点分别是起点和目标。让双向搜索的边缘从起点向右移动，从目标向左移动。在 2 次移动之后，所有节点都会被访问，但无法加入边缘，因为我们只能从一个节点向一个方向前进。但是，正如大卫在下面的回答中指出的那样，可以通过一些修改使算法工作。

4

6 回答 6

3

根据Wolfram Alpha的说法，

...确定给定一般图是否具有哈密顿路径的唯一已知方法是进行详尽搜索

我相信您会希望首先找到一条汉密尔顿路径，然后将其拆分为两条路径，使分割点尽可能清晰地将两条路径分开。然后你可以在子图中找到排列（当然还有递归！）

我不知道确切的算法，但我会从这种分而治之的方法开始。

于 2011-03-16T23:51:51.177 回答
1

您仍然可以使用双向搜索，只需在搜索中添加一个约束，这样以前看到的节点就不会成为搜索的候选对象。

您可以采取的另一种适合并行解决方案的方法是将搜索分解为更小的搜索。

例如，尝试通过解决以下问题来解决您的原始问题：

对于每个节点 n，它不是开始或结束节点，找到从开始到 n (set1) 和从 n 到结束 (set2) 的所有路径。

找到set1and后set2，您可以丢弃它们的叉积的所有元素，这些元素具有除 node 之外的公共节点n。

于 2011-03-16T23:51:01.610 回答
1

有人在https://mathoverflow.net/questions/36368/efficient-way-to-count-hamiltonian-paths-in-a-grid-graph-for-a-given在 Math Overflow 上问了一个与您非常相似的问题-pair-of-vert和（1）他们没有得到大量“这是如何有效地做到这一点”的回应（这可能意味着没有简单的方法），（2）Mathematica 显然需要 5 个小时来计算7x7 网格上对角之间的路径，因此您可能没有做错任何事情，并且 (3) 答案中有一些有趣的指针。

于 2011-03-16T23:56:25.180 回答
0

在 7x7 数组（即总共 7*7=49 个节点）上，使用 O(n!) 算法或 O(2^n*n^2) 算法都将花费太多时间。

考虑到这个特定图的特殊特性（例如，每个节点最多有 4 条边），也许有一些方法可以加快这个速度，但是快速解决方案似乎不太可能（除非有人偶然发现了哈密顿路径问题本身的多项式时间算法）。

于 2011-03-17T05:57:41.257 回答
0

它可以使用带有位掩码的 DP 来解决，我猜 n 的值最多为 20 或更多。创建一个 2d dp 表。dp[i][j] 表示您在第 i 个顶点上的情况的答案，j 存储有关已访问顶点的信息。这是一个 C++ 代码。

使用的宏：

#define    oncnt    __builtin_popcount
typedef    vector<int>   vi;

外部主要：

vi ad[21];
 int n,m;

 int dp[20][(1<<19)+1];

int sol(int i,int mask)
{
    //cout<<i+1<<" "<<oncnt(mask)<<"\n";

    if(i==n-1)
    return 1;

    if(mask&(1<<i))
    return 0;

    int &x=dp[i][mask];
    if(x!=-1)
    return x;

    x=0;

    for(int j=0;j<ad[i].size();j++)
    {
        int k=ad[i][j];
        if(mask&(1<<k))
        continue;
        if(k==n-1&&oncnt(mask)!=n-2)
        continue;
        if(k!=n-1&&oncnt(mask)==n-2)
        continue;
// The above two pruning statements are necessary.
        x=madd(x,sol(k,mask|(1<<i)));

    }

    return x;

}

内部主要：

cin>>n>>m;

for(int i=0;i<=n-1;i++)
 {
    for(int j=0;j<=(1<<(n-1));j++)
    dp[i][j]=-1;
 }


int a,b;
for(int i=1;i<=m;i++)
{
    cin>>a>>b;
    a--;
    b--;
    ad[a].pb(b);
}


 cout<<sol(0,0);
于 2020-06-15T09:44:17.533 回答
0

我发现这种方法非常快，并且我能够将其推广到六边形网格上：https ://hal.archives-ouvertes.fr/hal-00172308/document 。诀窍是通过网格推动边界，同时跟踪可能的路径。我的实现在几秒钟​​内处理了 20x20 的网格。

于 2021-01-15T15:10:09.167 回答