Пусть есть множество точек X = {x1, ..., xn}, лежащих на оси. Есть множество отрезков P = {p1, ..., pn},
причем каждый отрезок p может располагаться в произвольном месте на оси. Каждый отрезок p обладает
способностью поглощать q точек.
1. Каковы необходимые условия того, что все точки X могут быть поглощены отрезками P
2. Каковы достаточные условия того, что все точки X могут быть поглощены отрезками P
3. Алгоритм расчета местоположения отрезков на оси
Подскажите пожалуйста, есть ли типовые алгоритмы, или возможно есть иная формулировка данной задачи.
Здравствуйте, jerry_ru, Вы писали:
_>Пусть есть множество точек X = {x1, ..., xn}, лежащих на оси. Есть множество отрезков P = {p1, ..., pn}, _>причем каждый отрезок p может располагаться в произвольном месте на оси. Каждый отрезок p обладает _>способностью поглощать q точек. _> 1. Каковы необходимые условия того, что все точки X могут быть поглощены отрезками P _> 2. Каковы достаточные условия того, что все точки X могут быть поглощены отрезками P _> 3. Алгоритм расчета местоположения отрезков на оси
_>Пусть есть множество точек X = {x1, ..., xn}, лежащих на оси. Есть множество отрезков P = {p1, ..., pn}, _>причем каждый отрезок p может располагаться в произвольном месте на оси. Каждый отрезок p обладает _>способностью поглощать q точек. _> 1. Каковы необходимые условия того, что все точки X могут быть поглощены отрезками P _> 2. Каковы достаточные условия того, что все точки X могут быть поглощены отрезками P _> 3. Алгоритм расчета местоположения отрезков на оси
_>Подскажите пожалуйста, есть ли типовые алгоритмы, или возможно есть иная формулировка данной задачи.
хотелось бы пояснить задачу -- правильно ли я понял, что отрезки заданы фактически только своими длинами, а в твоей власти двигать их по оси как угодно?
вообще, задача кажется интересной, потому что не покидает ощущение, что ее можно оптимально решить жадным алгоритмом.
скажем, такой жадный алгоритм: проходим все отрезки начиная с самых длинных до самых коротких. Для любого набора точек определяем такую характеристику: "разброс" -- сумма всех попарных расстояний от точки до точки. Каждый следующий отрезок помещаем на такое место и поглощаем им такой набор точек, чтобы минимизировать "разброс" оставшихся точек.
Ну то есть идея такая -- попытаться найти такое определение функции "разброс", чтобы из существования решения для набора точек с некоторым значением "разброса" следовало существование решения для всех наборов точек с меньшим "разбросом". Тогда можно будет решить задачу динамическим программированием или жадным алгоритмом.
Здравствуйте, jerry_ru, Вы писали:
_>Пусть есть множество точек X = {x1, ..., xn}, лежащих на оси. Есть множество отрезков P = {p1, ..., pn}, _>причем каждый отрезок p может располагаться в произвольном месте на оси. Каждый отрезок p обладает _>способностью поглощать q точек. _> 1. Каковы необходимые условия того, что все точки X могут быть поглощены отрезками P _> 2. Каковы достаточные условия того, что все точки X могут быть поглощены отрезками P _> 3. Алгоритм расчета местоположения отрезков на оси
_>Подскажите пожалуйста, есть ли типовые алгоритмы, или возможно есть иная формулировка данной задачи.
В такой формулировке все множество точек может быть покрыто т.е. каждая точка своим собственным отрезком. Так как количество отрезков равно количеству точек.
Интереснее задача когда количетво точек n, а количество отрезков m, где m<n.
Выбираем m-1 пару последовательных точек между которыми максимальное расстояние. (надеюсь точки {x1, ..., xn} упорядочены). Минимальная необходимая общая длина отрезков для покрытия должна быть >= xn-x1-сумма этих найденых максимальных расстояний. Если это не так, то покрытие не возможно.
Количество оставшихся промежутков (которые и будем покрывать) n-m штук.
Надо подумать как бы их накрыть...
B>Выбираем m-1 пару последовательных точек между которыми максимальное расстояние. (надеюсь точки {x1, ..., xn} упорядочены). Минимальная необходимая общая длина отрезков для покрытия должна быть >= xn-x1-сумма этих найденых максимальных расстояний. Если это не так, то покрытие не возможно. B>Количество оставшихся промежутков (которые и будем покрывать) n-m штук. B>Надо подумать как бы их накрыть...
этот подход не всегда ведет к решению, хотя решение есть.
Пусть q=2. Точки: 1,1,100,200,200,300,400,400
Длины отрезков: 1,1,1,201
Три пары последовательных точек между которыми макс. расстояние: 100,200; 200,300; 300,400
Остались промежутки: 1-100 ; 200-200; 300-300; 400-400
Если ты хочешь покрывать именно эти промежутки и не покрывать те которые выкинул, то ничего не получится, ты не покроешь промежуток 1-100 одним отрезком, потому что q=2, а там 3 точки.
В то же время есть решение: покрыть длинным отрезком точки 100 и 300. А остальные покрыть короткими отрезками. Таким образом правильное решение покрывает промежутки которые ты выкинул.
Здравствуйте, dilmah, Вы писали:
B>>Выбираем m-1 пару последовательных точек между которыми максимальное расстояние. (надеюсь точки {x1, ..., xn} упорядочены). Минимальная необходимая общая длина отрезков для покрытия должна быть >= xn-x1-сумма этих найденых максимальных расстояний. Если это не так, то покрытие не возможно. B>>Количество оставшихся промежутков (которые и будем покрывать) n-m штук. B>>Надо подумать как бы их накрыть...
D>этот подход не всегда ведет к решению, хотя решение есть.
D>Пусть q=2. Точки: 1,1,100,200,200,300,400,400 D>Длины отрезков: 1,1,1,201
D>Три пары последовательных точек между которыми макс. расстояние: 100,200; 200,300; 300,400 D>Остались промежутки: 1-100 ; 200-200; 300-300; 400-400
D>Если ты хочешь покрывать именно эти промежутки и не покрывать те которые выкинул, то ничего не получится, ты не покроешь промежуток 1-100 одним отрезком, потому что q=2, а там 3 точки.
D>В то же время есть решение: покрыть длинным отрезком точки 100 и 300. А остальные покрыть короткими отрезками. Таким образом правильное решение покрывает промежутки которые ты выкинул.
Не очень понял объяснение.
1. Что такое q?
2. Точки на линии? Как-то странно ты их задаешь. Что за точки 200, 200 и 400, 400?
3. отрезки определяются длиной?
Но смысл понятен. Конечно, так в лоб не получится. И не только по той причине что ты сказал. Это только необходимое условие для покрытия, а не алгоритм. Алгоритм не продумал. Есть идея что начинать с удаления первого максимального, а потом пытаться уложить две части. Ну, типа рекурсию запустить.. Но, подумаю завтра утром. Извини.. Телек смотрю.. А ты с обозначениями определись что б людям легче было придумывать.
Предлагаю точки определять одним значением (это пойму что это за точки 200, 200) . Количествто точек n, Отрезки определять длиной, количество отрезков n. Устроит?
Каждый отрезок p обладает способностью поглощать q точек.
B>2. Точки на линии? Как-то странно ты их задаешь. Что за точки 200, 200 и 400, 400?
да, точки на линии, задаются одним числом, координатой. Перечислены через запятую. 200, 200 это две точки, лежащие рядом, в одном месте -- если это очень принципиально, то можно разнести их на эпсилон, скажем 199.9 и 200.1
B>3. отрезки определяются длиной?
да.
B>А ты с обозначениями определись что б людям легче было придумывать.
ээ.. это не моя задача вообще-то
B>Предлагаю точки определять одним значением (это пойму что это за точки 200, 200) . Количествто точек n, Отрезки определять длиной, количество отрезков n. Устроит?
если я правильно понял условие, то да. Только отрезков m, а не n.
Здравствуйте, dilmah, Вы писали:
B>>Не очень понял объяснение. B>>1. Что такое q?
D>в исходном условии: D>
Каждый отрезок p обладает способностью поглощать q точек.
B>>2. Точки на линии? Как-то странно ты их задаешь. Что за точки 200, 200 и 400, 400?
D>да, точки на линии, задаются одним числом, координатой. Перечислены через запятую. 200, 200 это две точки, лежащие рядом, в одном месте -- если это очень принципиально, то можно разнести их на эпсилон, скажем 199.9 и 200.1
B>>3. отрезки определяются длиной?
D>да.
B>>А ты с обозначениями определись что б людям легче было придумывать.
D>ээ.. это не моя задача вообще-то
B>>Предлагаю точки определять одним значением (это пойму что это за точки 200, 200) . Количествто точек n, Отрезки определять длиной, количество отрезков n. Устроит?
D>если я правильно понял условие, то да. Только отрезков m, а не n.
Убедил!
Хочу немного уточнить условие количество точек и отрезков не равно, длины в общем случае произвольные, располагать отрезки на оси можно также произвольно.
_> Ну то есть идея такая -- попытаться найти такое определение функции "разброс"
_>Хочу немного уточнить условие количество точек и отрезков не равно, длины в общем случае произвольные, располагать отрезки на оси можно также произвольно.
Еще маленькое уточнение: количество точек которое может поглотить отрезок может быть разным для разных отрезков.
.
