在以下方面,段树,间隔树,二进制索引树和范围树之间有什么区别:
请不要只给出定义.
有人知道interval treeC++中的任何好的实现吗？
显然,模板驱动的东西,更好的类似boost风格.
另一个问题 - 如果有人测试过,在std::vector实践中,基于分类的基本区间树实现是否可以击败通用区间树(使用O(lg)操作)？
这是一个关于某个复杂问题的算法问题.基础是这样的:
一种基于可用时隙和预留时隙的调度系统.插槽有一定的标准,我们称之为标签.如果可用插槽的标签集是保留插槽的超集,则预留与这些标签的可用插槽匹配.
作为一个具体示例,请采用以下方案:
11:00 12:00 13:00
+--------+
| A, B |
+--------+
+--------+
| C, D |
+--------+
11:00至12:30预订标签的时间之间A,并B可以进行,时间为12:00至13:30 C和D可用,并有大约12点的重叠至12:30.
11:00 12:00 13:00
+--------+
| A, B |
+--------+
+--------+
| C, D |
+--------+
xxxxxx
x A x
xxxxxx
这里A已经预订了,因此在11:15-ish和12:00-ish之间没有其他预订A或B可以预订.
这就是简单的想法.可用插槽没有特定限制:
系统中唯一需要遵守的规则是:
澄清一下:当有两个可用的插槽同时使用标签时A,那么A可以在那时进行两次预订,但不能再进行.
我有一个改进的间隔树实现的工作; 作为快速概述:
给定大小为n的数组,对于从1到n的每个k,找到大小为k的连续子阵列的最大和.
这个问题有一个明显的解决方案,时间复杂度为O(N 2)和O(1)空间.Lua代码:
array = {7, 1, 3, 1, 4, 5, 1, 3, 6}
n = #array
function maxArray(k)
ksum = 0
for i = 1, k do
ksum = ksum + array[i]
end
max_ksum = ksum
for i = k + 1, n do
add_index = i
sub_index = i - k
ksum = ksum + array[add_index] - array[sub_index]
max_ksum = math.max(ksum, max_ksum)
end
return max_ksum
end
for k = 1, n do
print(k, maxArray(k))
end …arrays algorithm dynamic-programming interval-tree data-structures
我正在寻找一种类似于CLR中的红黑区间树的区间树算法,但它默认支持合并区间,因此从不存在任何重叠区间.
换句话说,如果您有一个包含两个区间[2,3]和[5,6]的树,并且您添加了区间[4,4],则结果将是仅包含一个区间[2,6]的树.
谢谢
更新:我正在考虑的用例是计算传递闭包.间隔集用于存储后继集,因为它们被发现非常紧凑.但是,如果你将区间集表示为链表,我发现在某些情况下它们会变得非常大,因此找到插入点所需的时间也是如此.因此我对间隔树感兴趣.还有很多将一棵树与另一棵树合并(即一组OR操作) - 如果两棵树都很大,那么使用两棵树的顺序走路而不是每个间隔的重复插入来创建新树可能更好.
给定一个时间间隔列表,我需要找到最大非重叠间隔的集合.
例如,
如果我们有以下间隔:
[0600, 0830], [0800, 0900], [0900, 1100], [0900, 1130],
[1030, 1400], [1230, 1400]
另外,时间必须在该范围内[0000, 2400].
最大非重叠间隔集是[0600, 0830], [0900, 1130], [1230, 1400].
我知道最大设定包装是NP-Complete.我想确认我的问题(包含仅包含开始和结束时间的间隔)是否也是NP-Complete.
如果是这样,有没有办法在指数时间内找到最佳解决方案,但有更智能的预处理和修剪数据.或者如果有一个相对容易实现的固定参数易处理算法.我不想去寻找近似算法.
我正在寻找一个稳定的实现R树与支持无限尺寸(20左右就足够了)的最后几天.我只找到了这个http://sourceforge.net/projects/jsi/,但它们只支持2个维度.
另一个选项是区间树的多维实现.
也许我完全错误地使用了R-Tree或Intervall-tree来解决我的问题,所以我简单地说明了问题,你可以把你的想法发给我.
我需要解决的问题是某种最近邻搜索.我有一套天线和房间,每个天线有一个整数间隔.例如天线1,最小-92,最大-85.实际上它可以表示为房间 - >天线组 - >天线间隔.这个想法是每个房间在天线的尺寸上跨越R树中的一个盒子,并且在每个维度上跨越间隔.
如果我得到N-Antennas的查询和每个天线的值,那么我可以将信息表示为房间中的查询点并检索"最接近"点的房间.
希望你对问题和我的想法有所了解.
给定一组间隔:{1-4,6-7,10-12}添加一个新的间隔:(9,11),以便最终解决方案'合并':输出:{1-4,6-7, 9-12}.合并可能发生在双方(低和高范围).
我看到这个问题在多个地方得到了解答,有人甚至建议使用Interval Tress,但没有解释他们究竟会如何使用它.我所知道的唯一解决方案是按照开始时间的升序排列间隔并迭代它们并尝试合适地合并它们.
如果有人可以帮助我理解我们如何在这个用例中使用区间树,那就太棒了!
[我一直在关注CLRS书中的间隔树,但是他们没有谈论合并,他们所谈论的只是插入和搜索.]
我从这里下载了一个C#区间树集合类类http://intervaltree.codeplex.com/SourceControl/list/changesets - >右侧 - >下载.
但是我无法在我的Microsoft Visual C#2010 Express(也运行C#XNA)上打开整个项目,因为
此版本的应用程序不支持解决方案文件夹
另外,我只想在我自己的seprate项目中单独使用该类.
我试图复制三个重要的看似文件Interval.cs,IntervalNode.cs并IntervalTree.cs进入我的项目,但这产生了编译错误
没有导入器可以处理此文件类型
我还尝试将三个文件的内容复制并粘贴到我的项目中,将它们封装到自己的命名空间中,并且有很多代码.我不得不稍微重新安排一些使用,但遇到了可能需要PowerCollections .dll和.pcb文件作为using Wintellect.PowerCollections;原因的问题
找不到类型或命名空间名称'Wintellect'(您是否缺少using指令或程序集引用？)
我不知道如何继续,或者如果我正在做正确的事情,如何让这个班级工作.
我试图找到一个有效的C++间隔树实现(很可能基于红黑树)没有病毒或限制性许可证.任何指向干净的轻量级独立实现的指针？对于我想到的用例,一开始就知道了一组区间(可能会有一百万个),我希望能够快速获得一个与给定区间重叠的区间列表.因此,一旦构建的树将不会改变 - 只需要快速查询.