Что известно о сложности следующей задачи:
- Дано: рациональные числа .
- Вывод: целые числа .
- Цель: минимизировать где
То есть мы хотели бы округлить рациональные числа до целых чисел, чтобы минимизировать сумму ошибок в парных расстояниях. Для каждой пары мы бы хотели, чтобы округленное расстояние как можно ближе к истинному расстоянию .
Мотивация: скучная поездка на метро и плакат, показывающий «расположение» станций с разрешением в одну минуту времени в пути. Здесь мы минимизируем ошибку, которую совершают люди, если используют плакат для поиска времени в пути между станциями и , усредняя по всем парам .
Например, здесь мы можем прочитать следующие приближения парных расстояний между четырьмя станциями (для краткости используем A, B, C, D):
- A – B ≈ 1 минута, B – C ≈ 2 минуты, C – D ≈ 2 минуты
- A – C ≈ 3 минуты, B – D ≈ 4 минуты
- A – D ≈ 5 минут
Это наилучшее из возможных приближений? Если бы вы знали реальное время в пути, могли бы вы найти лучшее решение?
Сначала это звучало как простое упражнение в динамическом программировании, но теперь кажется, что требуется некоторое количество фактического мышления.
Кто-нибудь признает эту проблему? Или видите умный алгоритм для его решения?
Изменить: Есть несколько естественных вариантов вопроса, которые были упомянуты в комментариях; давайте дадим им несколько имен:
версия пола / потолка : требуется, чтобы для всех .i
целочисленная версия: достаточно, чтобы для всех . i
монотонная версия: требуется, чтобы .
немонотонная версия: у нас может быть для . i < j
Оригинальный вопрос рассматривает монотонную целочисленную версию, но ответы, связанные с любой из этих версий, приветствуются.
источник
Ответы:
ХОРОШО. Алгоритм DP кажется излишне сложным. После прочтения комментариев я думаю, что это может решить монотонную версию проблемы (но я не проверял каждую деталь).
Сначала предположим, что каждый , где является неотъемлемой частью, является дробной частью. Предположим, что округлено до , где - неотрицательное целое число (конечно, в общем случае может быть отрицательным, но мы всегда можем сдвинуться так, чтобы наименьшее значение 0).⌊ x i ⌋ { x i } x i ⌊ x i ⌋ + v i v i v i v iИкся= ⌊ хя⌋ + { xя} ⌊ хя⌋ { хя} Икся ⌊ хяV + vя vя vя vя
Теперь рассмотрим стоимость пары , при выполнении этого округления. Стоимость должна бытьх JИкся ИксJ
Выражение сложное из-за абсолютных значений. Однако обратите внимание, что у нас есть монотонность, поэтому вещи внутри двух внутренних абсолютных значений должны иметь тот же знак. Поскольку у нас есть внешнее абсолютное значение, на самом деле не имеет значения, что это за знак, выражение просто упрощается до
Отныне мы не предполагаем, что решение является монотонным, но вместо этого мы меняем цель, чтобы минимизировать сумму вышеуказанного члена для всех пар. Если решение этой проблемы оказывается монотонным, то, конечно, это также оптимальное решение для монотонной версии. (Думайте об этом как: исходная задача имеет бесконечное наказание, когда решение не является монотонным, новая проблема имеет меньшее наказание, если монотонное решение выигрывает даже в новой версии, это должно быть решение монотонной версии)
Теперь мы хотели бы доказать, что если , то в оптимальном решении должно быть .v i ≥ v j{ хя} > { xJ} vя≥ vJ
Предположим, что это не так, что у нас есть пара но . Покажем, что если мы местами решение станет строго лучше.v i < v j v i v j{ хя} > { xJ} vя<vJ vя vJ
Сначала мы сравним термин между и , здесь действительно ясно, что подкачка строго лучше, потому что в не-своп версии, и имеют одинаковый знак, абсолютный значение будет суммой двух абсолютных значений.j v i - v j { x j } - { x i }i j vi−vj {xj}−{xi}
Теперь для любого сравним сумму пар и . То есть нам нужно сравнить( i , k ) ( j , k )k (i,k) (j,k)
| v j - v k - ( { x i } - { x k } ) | + | v|vi−vk−({xi}−{xk})|+|vj−vk−({xj}−{xk})| и,|vj−vk−({xi}−{xk})|+|vi−vk−({xj}−{xk})|
Использование , , , , чтобы обозначить четыре условия внутри абсолютного значения, то ясно , что . Также ясно, что, По выпуклости абсолютного значения мы знаем, Взять сумму по всем , мы знаем, что обмен может быть только лучше.B C D A + B = C + D | A - B | ≥ | C - D | | A | + | Б | ≥ | C | + | D | х кA B C D A+B=C+D |A−B|≥|C−D| |A|+|B|≥|C|+|D| xk
Обратите внимание, что теперь у нас уже есть решение для версии Monotonic floor / ceil: должен быть порог, когда больше всегда округляется вверх, когда он меньше всегда округляется вниз, когда он равен округлению вверх и некоторые вниз, а качество решения зависит только от количества. Мы перечислим все эти решения и выберем решение с наименьшей целевой функцией. (Все эти решения обязательно являются монотонными).{xi}
Наконец, мы хотели бы перейти к монотонной целочисленной версии задачи. Фактически мы можем доказать, что оптимальное решение такое же, как и в монотонной версии пола / потолка.
Как мы и предполагали, наименьшее значение равно 0. Сгруппируйте все значения по их и назовите их группой . Сначала мы докажем, что нет пустых групп, но это просто, если группа пуста, для любого просто пусть . Легко видеть, что целевая функция всегда улучшается (в основном потому, что ).х я v я 0 , 1 , 2 , . , , , max { v i } k v i > k v i = v i - 1 | { x i } - { x j } | < 1vi xi vi 0,1,2,...,max{vi} k vi>k vi=vi−1 |{xi}−{xj}|<1
Теперь мы докажем, что среднее значение в группе по крайней мере равно среднему в группе плюс . Если это не так, просто пусть для всех , вычисление снова показывает, что целевая функция улучшается.к + 1 { х я } к 1 / 2 v я = v я - 1 V я > к{xi} k+1 {xi} k 1/2 vi=vi−1 vi>k
Поскольку среднее значение находится в диапазоне , в действительности существует не более двух групп, что соответствует версии floor / ceil.[ 0 , 1 ){xi} [0,1)
источник
Просто расширенный комментарий ... (возможно, банальный и / или неправильный :)
Если и является наименьшим общим кратным s, то мы можем избавиться от рациональных чисел: . M b i x ′ i = M ∗ x ixi=ai/bi M bi x′i=M∗xi
Если (floor, ceil ограничение), то мы можем использовать двоичные переменные чтобы выразить используя его расстояние от ( или ):yi∈{⌈xi⌉,⌊xi⌋} y ′ i x ′ i L i = x ′ i - M ∗ ⌊ x i ⌋ R i = x ′ i - M ∗ ⌈ x i ⌉vi y′i x′i Li=x′i−M∗⌊xi⌋ Ri=x′i−M∗⌈xi⌉
И исходная проблема должна (?!?) Быть эквивалентной нахождению которое минимизирует:vi
сvi∈{0,1},Di∈Z
источник
Еще один расширенный комментарий ... Может быть неправильно.
Я также рассматриваю случай с ограничениями пола / потолка и пытаюсь решить его с помощью динамического программирования (не могу, но, возможно, это работает, когда общий делитель мал).
Пусть будет дробной частью , мы рассмотрим вещи от самого маленького до самого большого. Предположим, что наибольшим является , и поскольку мы занимаемся динамическим программированием, мы уже знаем «что-то» (я объясню, что это такое) об оптимальном решении для всего остального, кроме .x i { x i } { x k } x k{xi} xi {xi} {xk} xk
Теперь рассмотрим разницу в целевой функции, когда мы вверх или вниз. Если изначально некоторые округлены, то разница равна просто 1 (на самом деле не очень тщательно проверил, но кажется, что это так, очень важно, чтобы независимо от того, находится ли слева или справа от , разница всегда одинаково); если изначально некоторый округляется в сторону, то разница составляет . Итак: мы знаем, какое решение нам следует принять, если известны следующие три величины:x i x i x k x i 2 { x k } - 2 { x i } - 1xk xi xi xk xi 2{xk}−2{xi}−1
Хорошо, 1 и 2 по существу одинаковы, мы можем позволить f [N, Ndown, Sdown] быть оптимальным решением для первых N точек (когда точки сортируются в порядке возрастания ), число округляется в меньшую сторону - Ndown, а сумма для округленных в меньшую сторону - Sdown. Тогда нетрудно написать, как перейти от f [N-1] к f [N].x i { x i }{xi} xi {xi}
Проблема, конечно, в том, что Sdown может иметь экспоненциально много значений. Но это работает, когда общий делитель мал или мы можем сначала округлить все до точки сетки и получить FPTAS (если приведенная выше динамическая программа верна ...)
источник