- Создан 2010-07-23 21:07:27
- пользователем Timur
Онлайн калькулятор: Задача об упаковке в контейнеры
Тут давеча пользователь Artuem оставил очень интересный запрос - Калькулятор количества целых досок из отрезков.
Приведу его здесь полностью, чтобы не прерывать нить повествования: "Есть некоторое количество отрезков разной длины, необходимо рассчитать минимальное кол-во досок из которых их можно нарезать, или что то типа того :)"
Немного подумав можно понять, что сие есть не что иное, как формулировка Задачи об упаковке в контейнеры.
Иными словами, имеются контейнеры фиксированного объема и набор предметов произвольного объема (понятно, что объем каждого предмета в отдельности меньше объема контейнера). Требуется упаковать эти предметы в минимальное число контейнеров.
Можно еще привести пример "из жизни" - есть набор файлов (например, кинофильмы) разного размера. Требуется записать весь набор на наименьшее число DVD-дисков. Ну и так далее. Частным случаем этой задачи является задача о рюкзаке, кстати.
Задача эта - NP-полная, то есть для гарантированного нахождения оптимального решения нужен полный перебор. Однако есть эвристические алгоритмы для нахождения подходящего решения. Если повезет, оно будет и оптимальным :)
Ниже калькулятор, а используемые алгоритмы, как водится, описаны под ним. И кстати, хоть на данных по умолчанию некоторые решения совпадают, но алгоритмы все-таки разные, и на других данных различия будут заметны
Начнем с Next Fit Algorithm (не уверен, как это переводится в соответствующей литературе, поэтому буду давать английские названия)
Next Fit Algorithm
Алгоритм очень туп, и в большинстве случаев даст наихудшие результаты из всех рассматриваемых алгоритмов.
Суть алгоритма в следующем:
1. Берем новый элемент
2. Берем новый контейнер.
3. Кладем элемент в контейнер.
4. Берем следующий элемент.
5. Если элемент влезает в контейнер, идем на шаг 3. Если элемент не влезает в контейнер, идем на шаг 2.
То есть мы тупо кладем элементы в контейнер, и если некий элемент уже не влазит, берем новый контейнер.
Можно придумать алгоритм и похитрее, но у этого алгоритма есть один плюс - он не требует просмотра прошлых контейнеров. Это может оказаться полезным, если, например, контейнеры к нам подъезжают по конвейеру.
First Fit Algorithm
Суть алгоритма в следующем:
1. Берем новый элемент
2. Берем новый контейнер.
3. Кладем элемент в контейнер.
4. Берем следующий элемент.
5. Если элемент влезает в контейнер, идем на шаг 3. Если элемент не влезает в контейнер, проверяем остальные контейнеры по порядку. Если находится контейнер с достаточным количеством свободного места, кладем элемент в контейнер и идем на шаг 4, иначе идем на шаг 2.
То есть кладем элементы в контейнер, и если элемент уже не влазит, пытаемся найти подходящий контейнер среди уже частично заполненных. Если места не находим, берем новый контейнер.
Worst Fit Algorithm
Суть алгоритма в следующем:
1. Берем новый элемент
2. Берем новый контейнер.
3. Кладем элемент в контейнер.
4. Берем следующий элемент.
5. Если элемент влезает в контейнер, идем на шаг 3. Если элемент не влезает в контейнер, берем частично заполненный контейнер с максимумом свободного места. Если элемент влазит в контейнер, кладем элемент в контейнер и идем на шаг 4, иначе идем на шаг 2.
То есть кладем элементы в контейнер, и если элемент уже не влазит, пытаемся положить его в наименее заполненных контейнер. Если это сделать не удается, берем новый контейнер.
Best Fit Algorithm
Суть алгоритма в следующем:
1. Берем новый элемент
2. Берем новый контейнер.
3. Кладем элемент в контейнер.
4. Берем следующий элемент.
5. Если элемент влезает в контейнер, идем на шаг 3. Если элемент не влезает в контейнер, берем частично заполненный контейнер с минимумом свободного места, но в который еще можно положить данный элемент. Если такой контейнер находится, идем на шаг 3, иначе идем на шаг 2.
То есть кладем элементы в контейнер, и если элемент уже не влазит, пытаемся положить его в наиболее заполненных контейнер, но в котором еще есть достаточно места для этого элемента. Если это сделать не удается, берем новый контейнер.
Также надо упомянуть и о том, что для каждого алгоритма есть вариант с предварительной сортировкой элементов по уменьшению - First Fit Decreasing, Best Fit Decreasing и т.п. То есть все тоже самое, только элементы берутся, начиная с самого крупного. Получается, я рассмотрел аж восемь алгоритмов. Но в калькуляторе используются только четыре - все варианты с предварительной сортировкой, ибо они дают лучшие результаты.
Приведу его здесь полностью, чтобы не прерывать нить повествования: "Есть некоторое количество отрезков разной длины, необходимо рассчитать минимальное кол-во досок из которых их можно нарезать, или что то типа того :)"
Немного подумав можно понять, что сие есть не что иное, как формулировка Задачи об упаковке в контейнеры.
Иными словами, имеются контейнеры фиксированного объема и набор предметов произвольного объема (понятно, что объем каждого предмета в отдельности меньше объема контейнера). Требуется упаковать эти предметы в минимальное число контейнеров.
Можно еще привести пример "из жизни" - есть набор файлов (например, кинофильмы) разного размера. Требуется записать весь набор на наименьшее число DVD-дисков. Ну и так далее. Частным случаем этой задачи является задача о рюкзаке, кстати.
Задача эта - NP-полная, то есть для гарантированного нахождения оптимального решения нужен полный перебор. Однако есть эвристические алгоритмы для нахождения подходящего решения. Если повезет, оно будет и оптимальным :)
Ниже калькулятор, а используемые алгоритмы, как водится, описаны под ним. И кстати, хоть на данных по умолчанию некоторые решения совпадают, но алгоритмы все-таки разные, и на других данных различия будут заметны
Начнем с Next Fit Algorithm (не уверен, как это переводится в соответствующей литературе, поэтому буду давать английские названия)
Next Fit Algorithm
Алгоритм очень туп, и в большинстве случаев даст наихудшие результаты из всех рассматриваемых алгоритмов.
Суть алгоритма в следующем:
1. Берем новый элемент
2. Берем новый контейнер.
3. Кладем элемент в контейнер.
4. Берем следующий элемент.
5. Если элемент влезает в контейнер, идем на шаг 3. Если элемент не влезает в контейнер, идем на шаг 2.
То есть мы тупо кладем элементы в контейнер, и если некий элемент уже не влазит, берем новый контейнер.
Можно придумать алгоритм и похитрее, но у этого алгоритма есть один плюс - он не требует просмотра прошлых контейнеров. Это может оказаться полезным, если, например, контейнеры к нам подъезжают по конвейеру.
First Fit Algorithm
Суть алгоритма в следующем:
1. Берем новый элемент
2. Берем новый контейнер.
3. Кладем элемент в контейнер.
4. Берем следующий элемент.
5. Если элемент влезает в контейнер, идем на шаг 3. Если элемент не влезает в контейнер, проверяем остальные контейнеры по порядку. Если находится контейнер с достаточным количеством свободного места, кладем элемент в контейнер и идем на шаг 4, иначе идем на шаг 2.
То есть кладем элементы в контейнер, и если элемент уже не влазит, пытаемся найти подходящий контейнер среди уже частично заполненных. Если места не находим, берем новый контейнер.
Worst Fit Algorithm
Суть алгоритма в следующем:
1. Берем новый элемент
2. Берем новый контейнер.
3. Кладем элемент в контейнер.
4. Берем следующий элемент.
5. Если элемент влезает в контейнер, идем на шаг 3. Если элемент не влезает в контейнер, берем частично заполненный контейнер с максимумом свободного места. Если элемент влазит в контейнер, кладем элемент в контейнер и идем на шаг 4, иначе идем на шаг 2.
То есть кладем элементы в контейнер, и если элемент уже не влазит, пытаемся положить его в наименее заполненных контейнер. Если это сделать не удается, берем новый контейнер.
Best Fit Algorithm
Суть алгоритма в следующем:
1. Берем новый элемент
2. Берем новый контейнер.
3. Кладем элемент в контейнер.
4. Берем следующий элемент.
5. Если элемент влезает в контейнер, идем на шаг 3. Если элемент не влезает в контейнер, берем частично заполненный контейнер с минимумом свободного места, но в который еще можно положить данный элемент. Если такой контейнер находится, идем на шаг 3, иначе идем на шаг 2.
То есть кладем элементы в контейнер, и если элемент уже не влазит, пытаемся положить его в наиболее заполненных контейнер, но в котором еще есть достаточно места для этого элемента. Если это сделать не удается, берем новый контейнер.
Также надо упомянуть и о том, что для каждого алгоритма есть вариант с предварительной сортировкой элементов по уменьшению - First Fit Decreasing, Best Fit Decreasing и т.п. То есть все тоже самое, только элементы берутся, начиная с самого крупного. Получается, я рассмотрел аж восемь алгоритмов. Но в калькуляторе используются только четыре - все варианты с предварительной сортировкой, ибо они дают лучшие результаты.
