1

I'm trying to calculate all bitonic paths for a given set of points.

Given N points.

My guess is there are O(n!) possible paths.

Reasoning

You have n points you can choose from your starting location. From there you have n-1 points, then n-2 points...which seems to equal n!.

Is this reasoning correct?

4

1 回答 1

1

您可以使用良好的旧动态编程来解决它。

让 Count(top,bottom) 是不完整的旅行的数量，使得 top 是最右边的顶行点，bottom 是最右边的点，并且 top 左侧是 bottom 的所有点都已经在路径中。

现在，Count(i,j) = Count(k,j) 其中 k={i-1}U{l: l

这是 O(n^3) 复杂度。

如果要枚举所有双音轨迹，Count 还可以跟踪所有路径。在更新步骤中适当地附加路径。不过，这将需要大量内存。如果您不想使用大量内存，请使用递归（同样的想法。对点进行排序。在每个递归点处，将新点放在上叉或下叉并检查是否有任何交叉点）

于 2012-02-16T18:37:22.910 回答