Цитата(Akina @ 10.1.2007, 18:02  ) |
| Для меня вообще загадка, что означает "сделать одни числа из других"... |
отображение
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > построение приблизительно равных отрезков |
| Автор: Swi 10.1.2007, 16:27 |
| Допустим у нас есть 10 отрезков на интервале от 0 до 1(все отрезки идут строго друг за другом), надо уменьшить количество отрезков до 4, причем таким образом, что бы все отрезки имели приблизительно равную величину. Длина начальных отрезков полностью случайна, интервал так же подразумевается абсолютно любые начальные и конечные количества отрезков. Начало следующего отрезка находится в окончании предыдущего и соответственно все точки принадлежат как первому так и второму массиву отрезков. А вообще задача заключается в следующем, есть n случайных чисел, надо из них сделать m случайных чисел, так что бы расстояния были примерно одинаковыми. |
| Автор: maxim1000 10.1.2007, 17:29 |
| для начала надо придумать критерий "приблизительной равности" средняя длина составных отрезков - (общая длина)/4 например, можно взять сумму модулей отклонений от средней длины или квадратов отклонений (тогда получится что-то вроде дисперсии) так или иначе потом надо найти разбиение, оптииальное с точки зрения выбранного критерия перебираем конец первого составного отрезка (ну и, соответственно, начало второго) для каждого варианта его конца - конец второго (должен быть не левее первого) ну и для каждого конца второго - конец третьего так получаем все варианты разбиений, выбираем из них то, которое даёт наименьшее значение критерия конечно, частенько в таких задачах полагается найти более-менее оптимизированный способ поиска решения, но учитывая масштабы задачи, вряд ли это имеет большой смысл... |
| Автор: Akina 10.1.2007, 19:02 |
| Для меня вообще загадка, что означает "сделать одни числа из других"... |
| Автор: maxim1000 10.1.2007, 19:09 | ||
отображение |
| Автор: esperant0 10.1.2007, 19:23 |
| Задача НП полная а посему решение - перебор |
| Автор: maxim1000 10.1.2007, 19:33 | ||
Хм... вот так вот сразу НП-полная?.. а почему? Добавлено @ 19:46 мне, кстати, приходят мысли о применении динамического программирования: здесь стандартная для него ситация - "марковская", т.е. слева и справа от любой точки можно разбивать абсолютно независимо (при подходящем критерии, например, аддитивном или приводимом к нему) для начала постановка: нужно разбить отрезки на группы так, чтобы минимизировать критерий "сумма f(Li)", количество групп разбиения - N, количество исходных отрезков - M строим массив a1[M+1]: a1[m]=f(L[0,m]), т.е. слагаемое из критерия для первого отрезка, если он начинается в 0 и заканчивается в m-й точке по нему строим массив a2[m]=min[по k] ( a1[k]+f(L[k,m]) ) ну и так далее (1 заменить на i, 2 - на i+1) сложность получается N*M... ну, если памяти жалко, то N*M*M |
| Автор: esperant0 10.1.2007, 21:04 |
| согласен, условие плохо прочитал |