округление
Oct. 29th, 2018 05:23 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sab123А вот еще к вопросу о динамическом программировании. Одна из типовых задач для него - "заполнение рюкзака".
Когда-то давно, когда я еще учился в школе, мои друзья написали программу для записи кучи файлов с делением на дискеты (файл между дискетами не делится). Это то самое заполнение рюкзаков (дискет). Ну, они лишнего заморачиваться с оптимальностью не стали, а выбирали файлы тупо в порядке "самый большой из оставшихся, который войдет в оставшееся место на дискете".
Но если мы пытаемся использовать динамическое программирование, то оказывается, что все файлы разного размера, и оттого толку от мемоизации - ноль. Чтобы вышел толк, надо округлить размер файлов вверх до некоторого небольшого числа классов. Но тогда очевидным образом решение получается неточным, неоптимальным. Любопытно (не так чтобы очень, а так, выйти потрепаться), есть ли способы легко "добить" такое неточное решение до более точного? Или возникают сильные возмущения и все рушится? Ведь наверняка же кто-нибудь из гигантов мысли уже задавался таким вопросом.
Когда-то давно, когда я еще учился в школе, мои друзья написали программу для записи кучи файлов с делением на дискеты (файл между дискетами не делится). Это то самое заполнение рюкзаков (дискет). Ну, они лишнего заморачиваться с оптимальностью не стали, а выбирали файлы тупо в порядке "самый большой из оставшихся, который войдет в оставшееся место на дискете".
Но если мы пытаемся использовать динамическое программирование, то оказывается, что все файлы разного размера, и оттого толку от мемоизации - ноль. Чтобы вышел толк, надо округлить размер файлов вверх до некоторого небольшого числа классов. Но тогда очевидным образом решение получается неточным, неоптимальным. Любопытно (не так чтобы очень, а так, выйти потрепаться), есть ли способы легко "добить" такое неточное решение до более точного? Или возникают сильные возмущения и все рушится? Ведь наверняка же кто-нибудь из гигантов мысли уже задавался таким вопросом.
А как же
Date: 2018-10-30 01:18 am (UTC)Re: А как же
Date: 2018-10-30 09:32 pm (UTC)Мне тут, кстати, пришел в голову простой способ полиномиальной апроксимации: Процесс подгонки к рюкзаку заключается в том, что если в рюкзаке осталось Se пустого места, и если у нас есть набор из K предметов в рюкзаке совокупным размером Sk и из M предметов вне рюкзака размером Sm, таким что Sm > Sk && Sm-Sk <= Se, то мы можем улучшить заполнение, поменяв местами эти наборы. Экспоненциальность обусловлена тем, что M и K ограничены только изначальным размером набора предметов. Ограничивая их меньшим фиксированным числом, получаем полиномиальность в соответствующей степени.
Алгоритм с выбором самого большого входящего предмета - это разновидность такой апроксимации со степенью 1.
Степень можно постепенно увеличивать, пока не достигнута требуемая точность или не исчерпано отведенное время. А вот тут можно и мемоизацию использовать - считать размеры наборов из N+1 предметов, используя информацию о наборах из N предметов. И никакого округления.