Задача про временные интервалы #576867

Добрый всем день. Есть следующая задача: Существует n временных интервалов. Необходимо разбить эти интервалы на минимально возможное количество m групп таким образом, чтобы в каждой группе была бы временная точка, принадлежащая одновременно всем интервалам из группы. Вопрос следующий - не существует ли общеизвестного алгоритма решения этой задачи? Стоит ли изобретать велосипед, или воспользоваться тем, что сделано до меня? Заранее спасибо.

два интервала: 0-10 и 11-20. разбей

Ну две группы будет.

и какая точка в каждой группе принадлежит всем интервалам?

В первой группе - любая, и во второй - любая. Читайте условие. :)

хватит задачи из матанализа постить, уже его все забыли

Да, замечу, что задача - исключительно прикладная :)

интервалы могут быть вообще непересекающиеся

непонятно условие, должны быть еще ограничения, иначе минимальное количество групп = 2: группа 1 = {все интервалы}, группа 2 = {все интервалы}

Совершенно верно. А вот здесь - неверно. Каждый из интервалов в группе должен иметь хотя бы одну общую точку со всеми остальными.

нуно найти наболее часто встречающиеся точки в интервалах, и от них плясать, ИМХО

Есть общеизвестный - полный перебор с отсечениями.

Вообще-то в этой задаче, минимальный набор групп получается, если просто добавлять по порядку в группы, если интервал пересекается. То есть не полный перебор, а однократный проход...

Как по условию задачи должны быть сгруппированы интералы 9-11, 10-13, 12-14? (1,2) или (2,3)?

нет, так даже если интервал персекается с одним он может пересекатся с большим-другим

(2;3)

А чем не устраивает (1,2)?

1234 *1 123  *2 578  *3 789  *4 87  *5 12345789 123__789 _____78 вычеркиваем оп максимальным вхождениям: 1) по семеркам *3*4*5 2) по восьмеркам неча уже вычеркивать 3) по единицам *1*2 вообщето дальше неча вычеркивать

перем начинт[100]; перем конинт[100]; перем колинт; Функция пересекается(а,б)    Если (начинт[а]<=начинт[б])и(конинт[а]>=начинт[б]) тогда        возврат 1;    иначеесли (начинт[а]>=начинт[б])и(начинт[а]<=конинт[б]) тогда            возврат 1;    иначе        возврат 0;    Конецесли;     Конецфункции     Процедура Сформировать   колинт=4;   начинт[1]=1;конинт[1]=10;   начинт[2]=2;конинт[2]=3;   начинт[3]=9;конинт[3]=12;   начинт[4]=8;конинт[4]=11;   начгруппы=1;           сообщить(""+1+" "+начинт[1]+"-"+конинт[1]);   Для а=2 по колинт цикл          Для б=начгруппы по а-1 цикл            Если пересекается(а,б)=0 тогда                  // начинаем новую группу                сообщить("-----");                  сообщить(""+а+" "+начинт[а]+"-"+конинт[а]);                начгруппы=а;                прервать;            КонецЕсли;            КонецЦикла;            Если начгруппы<а тогда            // продолжается старая группа            сообщить(""+а+" "+начинт[а]+"-"+конинт[а]);        Конецесли;       Конеццикла;     КонецПроцедуры

Пардон, возможны оба варианта)) Просмотрел. И оба будут верными.

какая разница какие группы, главное что их минимум две

Не понимаю о чем ты. Приведи пример.

Бред написал. В группу же нужно добирать до конца... Сейчас перепишу.

Ну ты предлагаешь добовлять в группу если есть пересечение, а интервал пожет персекаться с нескольками интервалами по разным перечечениям, по которым можно образовать меньше групп Зы не заморачивайся

перем начинт[100]; перем конинт[100]; перем подобрали[100]; перем колинт; Функция пересекается(а,б)    Если (начинт[а]<=начинт[б])и(конинт[а]>=начинт[б]) тогда        возврат 1;    иначеесли (начинт[а]>=начинт[б])и(начинт[а]<=конинт[б]) тогда            возврат 1;    иначе        возврат 0;    Конецесли;     Конецфункции     Процедура Сформировать   колинт=5;           Для а=1 по колинт цикл      подобрали[а]=0;   конеццикла;       начинт[1]=1;конинт[1]=10;   начинт[2]=2;конинт[2]=4;   начинт[3]=9;конинт[3]=12;   начинт[4]=8;конинт[4]=11;   начинт[5]=3;конинт[5]=4;   Для а=1 по колинт цикл          Если подобрали[а]=0 тогда               // начинаем группу               подобрали[а]=1;               сообщить("-----");                   сообщить(""+а+" "+начинт[а]+"-"+конинт[а]);                 списподобранных=создатьобъект("списокзначений");                 списподобранных.добавитьзначение(а);                 Для б=а+1 по колинт цикл                    Если подобрали[б]=1 тогда                        продолжить;                    Конецесли;                                                        подходит=1;                    для в=1 по списподобранных.размерсписка цикл                        Если пересекается(б,списподобранных.получитьзначение(в))=0 тогда                            подходит=0;                            прервать;                        Конецесли;                        Конеццикла;                          Если подходит=1 тогда                        // добавляем в группу                          подобрали[б]=1;                        списподобранных.добавитьзначение(б);                        сообщить(""+б+" "+начинт[б]+"-"+конинт[б]);                    Конецесли;                     Конеццикла;              КонецЕсли;       Конеццикла;         КонецПроцедуры

Приведи пример. Не может.

а время дискретно?

Да. Минимальная частица - секунда.

Хотя наверно действительно может дать неоптимальное разбиение, но даже если это так - это экзотика, сходу даже пример не придумать.

Это тоже вариант, который теоретически решит задачу "в лоб", но на его реализацию нужно избыточное количество вычислительных ресурсов. Памяти не хватит.

12345 *1 12    *2 2345  *3 23456 *4 Начинаем перебирать *1 и *2 Пересекаются по 1,2 и 12, но все 4 закрываются по 2

Вам - спасибо. Сейчас буду разбирать ваши алгоритмы :)

Хотя конечно наверное можно извернуться с обработкой данных долями и очисткой памяти.

а отсортировать интервалы по возрастанию и положению на временной оси не предлагать?

А зачем?

угу, не совсем то ...

В реальной задаче каково количество анализируемых интервалов?

Ну и? Берем первый интервал, добавляем к нему второй, третий и четвертый. Получаем одну группу. Такой результат код и выдаст.

границаНабора = ОтсортированныеПоДатеНачалаИнтервалы[0].ВремяОкончания; группа = Новый Массив массивГрупп = Новый Массив Для каждого интервал Из ОтсортированныеПоДатеНачалаИнтервалы Цикл   Если интервал.ВремяНачала > границаНабора Тогда       массивГрупп.Добавить(группа);       группа.Очистить;       границаНабора = интервал.ВремяОкончания;   Иначе       границаНабора = Мин(интервал.ВремяОкончания, границаНабора);   КонецЕсли;   группа.Добавить(интервал); КонецЦикла; массивГрупп.Добавить(группа); Вот и весь алгоритм, готов доказать, что количество групп будет минимальным. Если не стоит задача максимизировать количество интервалов в группах, то это оптимальный алгоритм, на мой взгляд.

вчера не успел подумать на работе, по дороге домой посчитал

Этот алгоритм не может быть оптимальным. Так как мой алгоритм в лучшем случае работает за О(N), а твой всегда за О(N ln N) Правда в худшем случае (когда один интервал) мой алгоритм работает за О(N^2)

а ты не считал количество операций в итерации у себя и у меня?

я понимаю, что еще сортировка, но это вполне окупится

Вообще-то принято считать сложность алгоритма, а не итерации. то есть О от количества итераций. У тебя за счет сортировки всегда Эн логарифмов.

да, я тебя понял но это все же для случая с одинаковой сложностью применимо ... надо будет попробовать замеры сделать

Представим задачу (для дискретного случая) в виде двудольного графа (ИНТЕРВАЛЫ, ЧИСЛА). Вершинами доли ИНТЕРВАЛЫ будут интервалы, вершинами доли ЧИСЛА будут числа, входящие в интервалы. Дуга от вершины ИНТЕРВАЛ к вершине ЧИСЛО будет если число входит в интервал. Тогда, если НЕ ошибаюсь, задача заключается в том, чтобы найти минимальное множество вершин доли ЧИСЛА, так чтобы из него были видны ВСЕ интервалы. ВОЗМОЖНО, здесь работает жадный алгоритм: брать число, которое входит в максимальное число интервалов - это будет "представитель" 1-ой группы, группу составят интервалы, которым число принадлежит, удалить число и интервалы из графа, повторить. Для примера выше (интервалы обозначил буквами): а(1234), б, в. г, д. Для чисел вхождение в интервалы: 1(аб), 2(аб), 3(аб), 4(а), 5(в), 7(вгд), 8(вгд), 9(г). 1-я группа - число 7 (или 8), интервалы (вгд) 2-я группа - число 1 (или 2), интервалы (аб). Не знаю, есть ли для этой задачи полиномиальный алгоритм: ее сложность пока не выяснил. Если выясню - отпишу.

Найди пример когда или не дадут лучший результат.

Того, что 24 или 38 неоптимальны я не утверждал. Хочется понять характер задачи.

Задача ИМХО не сводится к теории графов в явном виде.

Буду признателен, если укажите, где неправ: сам дыры не нашел.

Дыра в сложности алгоритма и в количестве вершин графа. Числа вообще могут быть не дискретны. И даже если они дискретны полиномиальным алгоритм от количества интервалов быть не может, так как количество чисел у нас вообще от количества интервалов не зависит.

Хотя можно числами считать только крайние границы интервалов. Тогда вы прийдете к методу в и

Возможно жадный алгоритм и совпадает с , . Пока открыт вопрос, является ли жадный алгоритм оптимальным.

По теории графов можно еще по-другому эту задачу представить: Вершины графа - это интервалы. Дуга между вершинами - интервалы имеют общую точку. Тогда, задача сводится к разбитию графа на минимальное количество "полных" подграфов. Естественно, после выделения очередного полного подграфа, дуги, соединяющие его с основным, удаляются.

На первый взгляд это справедливо, если интервалы не "дырявые". Известно, что поиск максимальной клики - NP-полная задача (правда, неочевидно, что интервалами можно породить произвольный граф). Для этой задачи неплохо работает алгоритм Брона — Кербоша Может поиск минимального числа клик проще?

угу, только сначала надо построить графы

Разве здесь есть какая-то проблема?

время

Может и не к месту, но два временных интервала могут отображаться 16-ю разными способами на временной прямой.

как это?

Интервал это или точка или отрезок, ну а далее: "точка" может быть до начала, равна началу, внутри, равна концу, за концом (всего 5 позиций). Если "отрезок то может не пересекать до начала, пересекать 2-й интервал, заканчиваться в начале 2-го, начинаться в начале 2-го, начинаться в конце 2-го, находиться внутри 2-го "отрезка", включать в себя 2-й "отрезок", заканчиваться в конце 2-го, находиться после 2-го и т.д. Всего может быть 16 положений временных интервалов на прямой относительно друг друга (если каждым интервалом можно считать и "точку"(нулевая длительность ДатаНачала = ДатаОкончания) или "отрезок" (ДатаНачала < ДатаОкончания).

Обычная задачка на пересечение множеств. Причём множества - конечные.

Задача оказалась не так проста: в случае "дырявых" интервалов она эквивалента NP-полной задаче о покрытии Жадный алгоритм не дает оптимального решения: пример в той же статье в Википедии. Для "сплошных" интервалов пример из Википедии не годится.

по-моему условие вообще некорректно поставлено: либо приводите все временные интервалы к единой т.о. и используйте полярные координаты для отсечения "групп" и точек в них (естесственно, все интревалы внутри групп будут равны), либо - то же самое, но с другого боку: определитесь, чем ограничена группа (каждая из m-множества групп), чтобы найти максимально входящее в каждую группу число неделимых интервальчиков (в данном случае - это секунды), и уже это принять за базу и строить отсюда какие-то теории. Иначе бессмысленно условие "минимально возможное количество групп" - все зависит, где я проведу границу группы: у этого исходного интервала эта секунда попадает во все интервалы группы, а эта - не попадает; делаю границу группы другой - все наоборот. И получается, что минимальное количество групп равно количеству минимальных неделимых частичек (в данной задаче - секунды), которые являются просто общими для всех интервалов: разбейте еще мельче (полсекунды, четверть секунды) - и количество искомых групп возрастет в соответствии с новым измельчением.

ну вот приехали