查找一系列间隔中最有效的分组 [英] Find the most efficient grouping of a series of intervals

问题描述

我有一个应用程序，其中有一系列不重叠的固定宽度间隔，每个间隔都有一个给定的键.每个间隔具有相同的宽度，并且可能存在连续的间隔.本质上，我希望以这样的方式对时间间隔和键进行分组，以使单独的时间间隔最小化.这可以通过合并具有相同键的连续间隔或寻找匹配的间隔并将它们与多个键组合为单个间隔来完成.我当前的算法尝试了以上两种方法，并观察到这导致了最小数量的间隔，但是我觉得必须有一种更聪明的方法来解决问题.任何建议将不胜感激！

I have an application where I have a series of non overlapping fixed width intervals, each of which have a given key. Each interval has the same width, and there may be contiguous intervals. Essentially I want to group the intervals and keys in such a way that I minimize the amount of separate intervals. This could be done by merging contiguous intervals with the same key or looking for matching intervals and combining them into single intervals with multiple keys. My current algorithm tries the above two approaches and sees which results in the smallest number of intervals, but I feel like there must be a smarter way of approaching the problem. Any advice would be much appreciated!

例如:

| ----- | | ----- |键为k1的时间间隔(连续)

|-----| |-----| intervals with key k1 (contiguous)

| ----- |键为k2的时间间隔

|-----| interval with key k2

| ----- |键为k3的时间间隔

|-----| interval with key k3

在此问题中，可以将密钥为k1的间隔合并为一个连续的间隔，从而得到3个而不是四个总间隔.或者，可以将每个键k1，k2和k3的第一个间隔与键k1，k2和k3组合为一个间隔，从而得到一个间隔加上k1中的第二个剩余间隔.

In this problem the intervals with key k1 could be merged to a single contiguous interval, resulting in 3 instead of four total intervals. Or the first interval for each key k1, k2 and k3 could be combined to one interval with keys k1, k2 and k3, resulting in one interval plus the second remaining interval in k1.

最坏的情况是间隔大约70,000.

Worst case would be something like 70,000 intervals.

推荐答案

一个好的近似解的想法.由于固定宽度输入数据的间隔可以表示为位掩码，其中一个(X)轴上有间隔，而另一个(Y)轴上有键.对于您这样的数据:

An idea for good approximation solution. Since intervals of fixed width input data can be represent as bitmask with intervals on one (X) axis and keys on other (Y) axis. For you data like:

k3  1  0
k2  1  0
k1  1  1
   i1 i2

问题类似于分区直线多边形问题.有一个很好的答案，涵盖了

Problem is similar to partitioning rectilinear polygon problem. There is a very good answer that covers the topic.

这不是确切的问题，因为在这种情况下，键的顺序并不重要，在示例中可以看到:

This is not exact problem since in this case order of keys is not important, what can be seen in example:

k3  1  1
k2  1  0
k1  1  1
   i1 i2

分区将产生3个矩形的查找结果，解应为2.

Partitioning will produce find result with 3 rectangles, and solution should be 2.

对此(也是近似值)的简单解决方案是进行输出后处理，并以相同的间隔连接矩形.这将有助于对按键进行重新排序的预处理，以使具有相似覆盖"的按键更近或更近.

Simple solution to this (also approximation) is to make output post-processing and join rectangles on same intervals. Here will help pre-processing that reorders keys so that keys with similar 'covering' are nearer or neighbours.

更复杂的解决方案是(我不是100％可行的)是使用算法中的想法对直线多边形进行分区.想法是:

More complex solution is (for which I am not 100% it works) is to use idea from algorithm for partitioning rectilinear polygons. Idea is to:

• 采取所有可能的分割方式(绳索)
• 使用线作为顶点和线相交的边来创建图形，
• 找到最大(编码)独立集.

在原始情况下，每个内部(270度)角在两个方向上产生两条线.由于按键顺序并不重要，我认为Z线应贯穿整个几何形状".这意味着电线是:

In original case, each inner (270deg) corner produces two cords in two directions. Since key ordering is not important, I think that Z cords should go through whole 'geometry'. That means cords are:

• 一个键继续间隔(X方向)
• 间隔结束(Z方向，经过整个几何图形).

这篇关于查找一系列间隔中最有效的分组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！