计算所有双调路径
我正在尝试计算给定点集的所有双调路径。
给定N点。
我的猜测是有 O(n!) 条可能的路径。
推理
从起始位置开始，您有 n 个点可供选择。从那里你有 n-1 点，然后是 n-2 点......这似乎等于 n！。
这个推理正确吗？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以使用古老的动态规划来解决它。
令 Count(top,bottom) 为不完整游览的数量，使得 top 是最右边的顶行点，bottom 是最右边的点，并且 top 和bottom 左边的所有点都已经在路径中。
现在，Count(i,j) = Count(k,j) 其中 k={i-1}U{l: l
这是 O(n^3) 复杂度。
如果您想枚举所有双调路径，则与 Count 一起还可以跟踪所有路径。在更新步骤中适当附加路径。但这需要大量内存。如果您不想使用大量内存，请使用递归（同样的想法。对点进行排序。在每个递归点，要么将新点放在顶叉或底叉上，然后检查是否有任何交叉）
You can solve it with good old dynamic programming.
Let Count(top,bottom) be the number of incomplete tours such that top is the rightmost top row point and bottom is the rightmost point and all the points left of top are bottom are already in the trail.
Now, Count(i,j) = Count(k,j) where k={i-1}U{l: l
This is O(n^3) complexity.
If you want to enumerate all the bitonic trails, along with Count also keep track of all the paths. In the update step append path appropriately. This would require a lot of memory though. If you don't want to use lot of memory use recursion (same idea. sort the points. At every recursion point either put the new point is top fork or the bottom fork and check if there are any crossings)