- Добро пожаловать на NovaLingua - форум любителей лингвистики.
NovaLingua - форум любителей лингвистики
Автор _Swetlana
- 29 июня 2024, 19:18Цитата: Hellerick от 29 июня 2024, 19:10Кстати.Алгоритм Йена находит первые k маршрутов.
Я еще в школе написал программку, находившую кратчайший маршрут в московском метро.
Но для меня по-прежнему загадка, как находить второй по краткости маршрут.
Автор Hellerick
- 29 июня 2024, 19:10Кстати.
Я еще в школе написал программку, находившую кратчайший маршрут в московском метро.
Но для меня по-прежнему загадка, как находить второй по краткости маршрут.
Я еще в школе написал программку, находившую кратчайший маршрут в московском метро.
Но для меня по-прежнему загадка, как находить второй по краткости маршрут.
Автор Vesle Anne
- 29 июня 2024, 18:56Цитата: Hellerick от 06 мая 2024, 04:33Найти бы хотя бы просто "недетерминированный" алгоритм, который перебирает варианты, вместо того, чтобы выдавать единственный.рл вам в помощь
А уж выбрать из них хороший — не проблема.
Автор _Swetlana
- 29 июня 2024, 18:39Какая гадость эта ваша динамическая типизация.
ссылка на яндекс-диск
ссылка на яндекс-диск
Автор _Swetlana
- 06 мая 2024, 12:12Цитата: Hellerick от 06 мая 2024, 04:33Найти бы хотя бы просто "недетерминированный" алгоритм, который перебирает варианты, вместо того, чтобы выдавать единственный.Да запросто. Ещё одна неглубокая идея
А уж выбрать из них хороший — не проблема.
В оптимальной упаковке не может быть двух контейнеров, заполненных не более чем наполовину. Иначе бы мы сложили их содержимое в один контейнер и уменьшили целевую функцию.
Что отсюда следует. А то, что n-1 контейнер заполнен более чем на половину и только один-единственный может быть заполнен менее чем на половину. Так какой смысл пытаться уплотнить упаковку сразу во всех контейнерах? За этот один и возьмёмся, будем максимизировать "огрызок" в одном контейнере. Делать это можно локальным поиском: найдём решение FFD-алгоритмом, затем будем искать лучшее решение в его окрестности. Допустимые операции: одна палка перекладывается из одного контейнера в другой; две палки из разных контейнеров меняются местами.
Автор Hellerick
- 06 мая 2024, 04:33Найти бы хотя бы просто "недетерминированный" алгоритм, который перебирает варианты, вместо того, чтобы выдавать единственный.
А уж выбрать из них хороший — не проблема.
А уж выбрать из них хороший — не проблема.
Автор _Swetlana
- 06 мая 2024, 00:44Цитата: Hellerick от 05 мая 2024, 16:29(в том смысле, в котором в питоне сравниваются два списка).понятно
Ну тут как можно. FFD сформировать начальное решение. В скобках замечу, что по числу использованных шестов оно будет минимальным. А потом методом локального поиска пытаться улучшить упаковку. Например, делать обмены. Выбирать пару шестов, пусть они обмениваются палками. Если целевая функция улучшилась, то делать обмен. Давно я такое делала для равномерного распределения работ между бригадами, но подробности плохо помню.
Автор Hellerick
- 05 мая 2024, 16:29Цитата: _Swetlana от 05 мая 2024, 16:10А что там за ИИ-то был?
Если не ошибаюсь, я использовал модель claude-3-haiku вот здесь:
https://labs.perplexity.ai/
Цитата: _Swetlana от 05 мая 2024, 16:10Нужно как-то формализовать наши дальнейшие хотелки
Ны дык:
Цитата: Hellerick от 30 апреля 2024, 07:21Критерий оптимизации: список `remainders`, содержащий в себе неиспользуемые остатки каждого шеста, отсортированный в порядке убывания, должен быть как можно больше (в том смысле, в котором в питоне сравниваются два списка). То есть, надо использовать как можно меньше шестов, при этом от использованных шестов надо оставить как можно бо́льшие остатки.
Для моего решения:
Цитировать2200×2 + 680×1 + 450×2 = 5980 (20 poles)
1429×3 + 680×2 + 170×2 = 5987 (10 poles)
1429×2 + 496×6 = 5834 (3 poles)
1429×4 = 5716 (1 pole)
496×2 = 992 (1 pole)
остатки будут равны:
remainders = [5008, 284, 166, 166, 166, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13]
Задача -- найти раскладку, для которого отсортированный массив остатков будет наибольшим.
Автор _Swetlana
- 05 мая 2024, 16:10Цитата: H_N от 05 мая 2024, 12:57Не программист я и не математик. Зацепила реплика Hellerick'а, что ИИ сработал хуже человека.@Hellerick А что там за ИИ-то был?
Так ИИ просили использовать минимальное количество шестов. Что он и сделал.
Нужно как-то формализовать наши дальнейшие хотелки, иначе многокритериальная оптимизация получится, а это другая задача.
Из всех минимальных упаковок в 35 шестов выбрать ту самую ... Ну давайте подумаем, что мы тут максимизируем.
У каждого шеста вычисляем длину "огрызка". У меня она прямо в атрибуте экземпляра хранится, и вычислять не надо. Далее, среди всех шестов находим максимальный огрызок.
Вопрос к ИИ. При таких-то исходных данных среди всех упаковок в 35 шестов найти упаковку, у которой длина максимального огрызка максимальна.
Автор H_N
- 05 мая 2024, 12:57Не программист я и не математик. Зацепила реплика Hellerick'а, что ИИ сработал хуже человека. Попробовал и сам поискать решение его задачи. Действовал тупым перебором вариантов. Тактика простая: поначалу компоновал крупняк. Удачно подошли 20 раскроек по 5999 мм. Далее по убыванию... Итог: влез в 35-ый шест на 450 мм. Остаток, соответственно, 5550 мм. Был и промежуточный — 5100, но я нашёл и лучший.
2200*2 + 1429*1 + 170*1 = 5999 (20 шт.)
1429*3 + 680*1 + 496*2 = 5959 (5 шт.)
1429*1 + 680*2 + 496*1 + 450*6 = 5985 (2 шт.)
1429*1 + 680*3 + 496*2 + 450*3 = 5811 (1 шт.)
1429*1 + 450*10 = 5929 (2 шт.)
680*6 + 496*2 + 450*2 = 5972 (2 шт.)
680*8 + 496*1 = 5936 (2 шт.)
450*1 = 450 (1 шт.)
2200*2 + 1429*1 + 170*1 = 5999 (20 шт.)
1429*3 + 680*1 + 496*2 = 5959 (5 шт.)
1429*1 + 680*2 + 496*1 + 450*6 = 5985 (2 шт.)
1429*1 + 680*3 + 496*2 + 450*3 = 5811 (1 шт.)
1429*1 + 450*10 = 5929 (2 шт.)
680*6 + 496*2 + 450*2 = 5972 (2 шт.)
680*8 + 496*1 = 5936 (2 шт.)
450*1 = 450 (1 шт.)
Автор _Swetlana
- 03 мая 2024, 13:11Цитата: Hellerick от 03 мая 2024, 05:21Среди найденных вариантов я выбираю те, которые кажутся перспективными.Вот это правильно, повторяющиеся раскладки. Тем более, данные у вас уж очень регулярные - каждого вида по 40 штук.
Перспективные раскладки — те, которые можно многократно повторять, то есть рабочий может нарезать эту раскладку несколько раз.
Как-то решала задачу, там разрезалась стальная полоса на полосы определенной ширины, и вот эти ширины набирались с помощью втулок, которые на листе выставлялись. И нужно было не просто набрать нужные суммы (ширины), а набрать минимальным числом втулок, чтобы резчику не приходилось долго это всё выкладывать.
Ну та задача решалась динамическим программированием.
Потом я ее в свой учебник вставила, вот она:
ЦитироватьЗадание 3 (высокий уровень)
Линия продольной резки рулонного металла вырезает из рулона полосу определённой ширины. У резчика имеется набор втулок разной ширины. Набрать заданную ширину с помощью имеющихся втулок так, чтобы количество использованных втулок было минимально. Исходные данные придумать самому, набор должен содержать не менее 25 втулок, в наборе могут быть втулки одинаковой ширины.
Автор Hellerick
- 03 мая 2024, 05:21Для полуавтоматической раскладки я сделал себе такую перебиралку:
Она мне печатает наиболее удачные возможные раскладки:
Среди найденных вариантов я выбираю те, которые кажутся перспективными.
Перспективные раскладки — те, которые можно многократно повторять, то есть рабочий может нарезать эту раскладку несколько раз, избавляя нас от наиболее длинных палок, но при этом оставляя разумное количество коротких палок для дальнейших раскладок. Наверное, перспективную "хорошесть" раскладки можно как-то оценить численно.
Выбрав одну раскладку, и "нарезав" по ней палки, я прогоняю скрипт повторно, уже с меньшим набором требуемых палок. Чем дальше, тем меньше остается выбор, и тем меньше "мощность" задачи по перебору вариантов.
Короче, при осознанном подходе, у задачи не такое уж великое ветвление, и разумные варианты там вполне посильно перебрать.
Код Выделить
sticks = {
2200: 40,
1429: 40,
680: 40,
496: 20,
450: 40,
170: 20}
pole_length = 6000
stick_lengths = sorted([l for l in sticks], reverse=True)
def vary(inlayouts, depth):
check_qty = min(
pole_length//stick_lengths[depth],
sticks[stick_lengths[depth]],
)
outlayouts = []
if depth == len(stick_lengths)-1:
for i in range(check_qty+1):
outlayouts = outlayouts + [inlayouts + [i]]
else:
for i in range(check_qty+1):
outlayouts = outlayouts + vary(inlayouts+[i], depth+1)
return outlayouts
layouts = vary([], 0)
def layout_total_len(layout):
return sum([layout[i]*stick_lengths[i] for i in range(len(layout))])
layouts = [l for l in layouts if layout_total_len(l) <= pole_length and sum(l)>0]
layouts.sort(key = layout_total_len, reverse = True)
print(f'Number of layouts found: {len(layouts)}')
print(f'For sticks with lengths\n{stick_lengths}\n')
print(f'Best layouts:')
for l in layouts[:400]:
print(f'{l}, L={layout_total_len(l)}')
Она мне печатает наиболее удачные возможные раскладки:
Код Выделить
Number of layouts found: 6350
For sticks with lengths
[2200, 1429, 680, 496, 450, 170]
Best layouts:
[0, 0, 3, 0, 2, 18], L=6000
[0, 0, 4, 0, 2, 14], L=6000
[0, 0, 5, 0, 2, 10], L=6000
[0, 0, 6, 0, 2, 6], L=6000
[0, 0, 7, 0, 2, 2], L=6000
[0, 2, 0, 2, 1, 10], L=6000
[0, 2, 1, 2, 1, 6], L=6000
[0, 2, 2, 2, 1, 2], L=6000
[0, 1, 0, 0, 6, 11], L=5999
[0, 1, 0, 5, 2, 7], L=5999
[0, 1, 1, 0, 6, 7], L=5999
[0, 1, 1, 5, 2, 3], L=5999
[0, 1, 2, 0, 6, 3], L=5999
[1, 1, 0, 0, 3, 6], L=5999
[1, 1, 1, 0, 3, 2], L=5999
[2, 1, 0, 0, 0, 1], L=5999
[0, 0, 0, 3, 7, 8], L=5998
[0, 0, 0, 8, 3, 4], L=5998
[0, 0, 1, 3, 7, 4], L=5998
[0, 0, 1, 8, 3, 0], L=5998
[0, 0, 2, 3, 7, 0], L=5998
[1, 0, 0, 3, 4, 3], L=5998
[0, 1, 0, 1, 3, 16], L=5995
[0, 1, 1, 1, 3, 12], L=5995
[0, 1, 2, 1, 3, 8], L=5995
[0, 1, 3, 1, 3, 4], L=5995
[0, 1, 4, 1, 3, 0], L=5995
[1, 1, 0, 1, 0, 11], L=5995
[1, 1, 1, 1, 0, 7], L=5995
[1, 1, 2, 1, 0, 3], L=5995
...
Среди найденных вариантов я выбираю те, которые кажутся перспективными.
Перспективные раскладки — те, которые можно многократно повторять, то есть рабочий может нарезать эту раскладку несколько раз, избавляя нас от наиболее длинных палок, но при этом оставляя разумное количество коротких палок для дальнейших раскладок. Наверное, перспективную "хорошесть" раскладки можно как-то оценить численно.
Выбрав одну раскладку, и "нарезав" по ней палки, я прогоняю скрипт повторно, уже с меньшим набором требуемых палок. Чем дальше, тем меньше остается выбор, и тем меньше "мощность" задачи по перебору вариантов.
Короче, при осознанном подходе, у задачи не такое уж великое ветвление, и разумные варианты там вполне посильно перебрать.
Автор _Swetlana
- 03 мая 2024, 01:00Мой FFD дает такой же результат, как ИИ. Но у меня ООП, в отличии от.
Правда, класс "палка" я не стала создавать, чтобы не усложнять ввод данных. Создала только класс шест
Использованных контейнеров: 35
5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5716 5716 5716 5716 5716 5936 5936 5936 5936 5936 5952 5988 5850 5850 1800 0 0 0 0 0
Правда, класс "палка" я не стала создавать, чтобы не усложнять ввод данных. Создала только класс шест
Код Выделить
class Pole:
pcount = 0
def __init__(self):
self.length = 6000
self.stics = []
def add_stic(self, lstick):
if lstick <= self.length:
if self.length == 6000: # начинаем новый контейнер
Pole.pcount += 1
self.length -= lstick
self.stics.append(lstick)
return True
else:
return False
stics = [2200]*40 + [1429]*40 + [680]*40 + [496]*20 + [450]*40 + [170]*20
poles = [Pole() for _ in range(40)]
for stic in stics:
for p in poles:
if p.add_stic(stic):
break
print('Использованных контейнеров:', Pole.pcount)
for p in poles:
print(6000 - p.length, end=' ')Использованных контейнеров: 35
5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5716 5716 5716 5716 5716 5936 5936 5936 5936 5936 5952 5988 5850 5850 1800 0 0 0 0 0
Автор _Swetlana
- 02 мая 2024, 23:19Цитата: Hellerick от 02 мая 2024, 18:09Попытался почитать материалы по предоставленным вами ссылкам, но, честно говоря, ничего кроме неглубокой мысли...Еще одна неглубокая мысль. Оценка снизу: складываем длины всех заготовок и делим нацело 6000.
Это я сделала в питоне (вот питон и пригодился
), получила 33.Т.е. 33 - оценка снизу, которой явно не хватит, а 35 дает приближенный алгоритм.
Вы думаете, что какая-то очень глубокая мысль даст 34?
Можно проверить, путем точного перебора и логических рассуждений (раскидываем 40 заготовок по 2200 на 34 шеста однозначно, затем заготовки по 1429 тоже без вариантов распределяются), что для этого примера 34 недостаточно.
Автор _Swetlana
- 02 мая 2024, 22:14Ну что я могу сказать. Этой неглубокой мысли соответствует доказанная теорема, что в самом худшем специально сконструированном случае FFD ошибётся на 22%, что очень неплохо для NP-hard. Более глубоких мыслей у меня нет
Сортируйте заготовки по убыванию длины и раскладывайте по принципу "в первый подходящий".
Остатки шестов мы не максимизируем! оптимизация по одному параметру - количеству использованных шестов. Видимо, в вашем примере 35 шестов и есть оптимальное решение.
P.S. Попробую написать FFD на питоне, для тренировки.
Сортируйте заготовки по убыванию длины и раскладывайте по принципу "в первый подходящий".
Остатки шестов мы не максимизируем! оптимизация по одному параметру - количеству использованных шестов. Видимо, в вашем примере 35 шестов и есть оптимальное решение.
P.S. Попробую написать FFD на питоне, для тренировки.
Автор Hellerick
- 02 мая 2024, 18:09Попытался почитать материалы по предоставленным вами ссылкам, но, честно говоря, ничего кроме неглубокой мысли, что сначала нужно постараться распределить самые большие изделия, потом -- поменьше, и надеяться, что результат получится неплохим, я не увидел.
Взял конкретный рабочий пример из своей практики: sticks = {2200: 40, 1429: 40, 680: 40, 496: 20, 450: 40, 170: 20}
Для простоты решил все шесты взять по 6000 мм: pole_length = 6000
Попросил ИИ написать мне алгоритм. Тот решил задачу напрямик:
Результат:
Результат неплохой.
А вот решение, которое я некогда нашел вручную:
И там, и там использовано по 35 шестов.
Разница в том, что от последнего шеста ИИ оставил 6000-1800=4200 мм, а я -- 6000-992=5008 мм.
То есть я оставил больший деловой отход, так что мое решение лучше ИИшного.
ИИ решил пять шестов разрезать по схеме 1429+1429+1429+1429=5716, оставляя 6000-5716=284 мм отхода.
На этой длине поместилась бы палка длиной 170 мм, вот только ИИ их все уже использовал в предыдущих раскроях.
Когда я кроил осмысленно, я таких ситуаций не допускаю. Я знаю, что короткие палки дают больше свободы для раскроя, и их надо беречь.
Взял конкретный рабочий пример из своей практики: sticks = {2200: 40, 1429: 40, 680: 40, 496: 20, 450: 40, 170: 20}
Для простоты решил все шесты взять по 6000 мм: pole_length = 6000
Попросил ИИ написать мне алгоритм. Тот решил задачу напрямик:
Код Выделить
pole_length = 6000
sticks = {2200: 40, 1429: 40, 680: 40, 496: 20, 450: 40, 170: 20}
def cut_poles(pole_length, sticks):
stick_lengths = list(sticks.keys())
stick_lengths.sort(reverse=True)
cutting_plan = []
poles_used = 0
while any(count > 0 for count in sticks.values()):
remaining_length = pole_length
pole_cutting_plan = []
for stick_length in stick_lengths:
while remaining_length >= stick_length and sticks[stick_length] > 0:
pole_cutting_plan.append(stick_length)
remaining_length -= stick_length
sticks[stick_length] -= 1
if pole_cutting_plan:
cutting_plan.append(pole_cutting_plan)
poles_used += 1
return cutting_plan, poles_used
cutting_plan, poles_used = cut_poles(pole_length, sticks)
print(f"Minimum number of poles needed: {poles_used}")
print("\nCutting Plan:")
for i, pole_plan in enumerate(cutting_plan, start=1):
print(f"Pole {i}: {' + '.join(str(length) for length in pole_plan)} = {eval(' + '.join(str(length) for length in pole_plan))}")
Результат:
Код Выделить
Minimum number of poles needed: 35
Cutting Plan:
Pole 1: 2200 + 2200 + 1429 + 170 = 5999
Pole 2: 2200 + 2200 + 1429 + 170 = 5999
Pole 3: 2200 + 2200 + 1429 + 170 = 5999
Pole 4: 2200 + 2200 + 1429 + 170 = 5999
Pole 5: 2200 + 2200 + 1429 + 170 = 5999
Pole 6: 2200 + 2200 + 1429 + 170 = 5999
Pole 7: 2200 + 2200 + 1429 + 170 = 5999
Pole 8: 2200 + 2200 + 1429 + 170 = 5999
Pole 9: 2200 + 2200 + 1429 + 170 = 5999
Pole 10: 2200 + 2200 + 1429 + 170 = 5999
Pole 11: 2200 + 2200 + 1429 + 170 = 5999
Pole 12: 2200 + 2200 + 1429 + 170 = 5999
Pole 13: 2200 + 2200 + 1429 + 170 = 5999
Pole 14: 2200 + 2200 + 1429 + 170 = 5999
Pole 15: 2200 + 2200 + 1429 + 170 = 5999
Pole 16: 2200 + 2200 + 1429 + 170 = 5999
Pole 17: 2200 + 2200 + 1429 + 170 = 5999
Pole 18: 2200 + 2200 + 1429 + 170 = 5999
Pole 19: 2200 + 2200 + 1429 + 170 = 5999
Pole 20: 2200 + 2200 + 1429 + 170 = 5999
Pole 21: 1429 + 1429 + 1429 + 1429 = 5716
Pole 22: 1429 + 1429 + 1429 + 1429 = 5716
Pole 23: 1429 + 1429 + 1429 + 1429 = 5716
Pole 24: 1429 + 1429 + 1429 + 1429 = 5716
Pole 25: 1429 + 1429 + 1429 + 1429 = 5716
Pole 26: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 27: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 28: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 29: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 30: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 31: 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 = 5952
Pole 32: 496 + 496 + 496 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 = 5988
Pole 33: 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 = 5850
Pole 34: 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 = 5850
Pole 35: 450 + 450 + 450 + 450 = 1800
Результат неплохой.
А вот решение, которое я некогда нашел вручную:
Код Выделить
2200×2 + 680×1 + 450×2 = 5980 (20 poles)
1429×3 + 680×2 + 170×2 = 5987 (10 poles)
1429×2 + 496×6 = 5834 (3 poles)
1429×4 = 5716 (1 pole)
496×2 = 992 (1 pole)
И там, и там использовано по 35 шестов.
Разница в том, что от последнего шеста ИИ оставил 6000-1800=4200 мм, а я -- 6000-992=5008 мм.
То есть я оставил больший деловой отход, так что мое решение лучше ИИшного.
ИИ решил пять шестов разрезать по схеме 1429+1429+1429+1429=5716, оставляя 6000-5716=284 мм отхода.
На этой длине поместилась бы палка длиной 170 мм, вот только ИИ их все уже использовал в предыдущих раскроях.
Когда я кроил осмысленно, я таких ситуаций не допускаю. Я знаю, что короткие палки дают больше свободы для раскроя, и их надо беречь.
Автор _Swetlana
- 01 мая 2024, 00:28Цитата: Hellerick от 30 апреля 2024, 07:21@_SwetlanaНемножко удалила, что с телефона отправляла
А вы не могли бы поразмыслить над практической задачей?
Я называю ее задачей линейного раскроя.
Вот нам даны, скажем 9 шестов длинной 6000 мм: `poles={6000:9}`
Их надо разрезать на палки, при этом даны длины палок и требуемые их количества: `sticks={1550:10, 1200:8, 600:12, 550:4, 300:20}`.
Требуется: Напечатать, как следует разрезать шесты на палки оптимальным образом. Примерно так: "Pole #1: 1550*3+1550*3+1200=5850".
Критерий оптимизации: список `remainders`, содержащий в себе неиспользуемые остатки каждого шеста, отсортированный в порядке убывания, должен быть как можно больше (в том смысле, в котором в питоне сравниваются два списка). То есть, надо использовать как можно меньше шестов, при этом от использованных шестов надо оставить как можно бо́льшие остатки.
Я догадываюсь, что это какая-то классическая задача на оптимизацию, но не в курсе, как такие принято решать.
Сейчас я решаю ее в полуавтоматическом режиме: скрипт на питоне подсказывает, как красиво избавляться самого большого числа самых длинных палок, а потом, комбинируя предложенные способы, я нахожу хороший общий раскрой.
Будут вопросы - пишите, обсудим. Страсть как люблю производственные оптимизационные NP-полные задачи решать Автор _Swetlana
- 30 апреля 2024, 21:31Ну и как задача одномерной упаковки решается FFD-алгоритмом двойным циклом за O(n2), где n - количество пакуемых предметов.
FFD-алгорит для задачи одномерной упаковки
FFD-алгорит для задачи одномерной упаковки
Автор _Swetlana
- 30 апреля 2024, 21:28Наша задача, неформально. Имеется n одинаковых контейнеров. Вместимость может быть любая, в модельной задаче вместимость равна 1. Имеется n предметов размерами от 0 до 1, не включая 0.
Нужно упаковать предметы в минимальное число контейнеров таким образом, чтобы все предметы были упакованы, и сумма размеров предметов в одном контейнере не превосходила его вместимости, т.е. 1.
Как она решается точным алгоритмом с возвратом, когда предметов <= 20:
общее описание алгоритма с возвратом
алгоритм с возвратом для одномерной упаковки
Нужно упаковать предметы в минимальное число контейнеров таким образом, чтобы все предметы были упакованы, и сумма размеров предметов в одном контейнере не превосходила его вместимости, т.е. 1.
Как она решается точным алгоритмом с возвратом, когда предметов <= 20:
общее описание алгоритма с возвратом
алгоритм с возвратом для одномерной упаковки
Автор _Swetlana
- 30 апреля 2024, 21:20Задача одномерной упаковки - классическая NP-трудная в сильном смысле задача. Что это значит.
1. NP-трудная - никто не знает, как решить её за полиномиальное время точным алгоритмом.
2. ... в сильном смысле - не решается за псевдополиномиальное время динамическим программированием.
На самом деле таких задач полно - и на производстве, и в науке. По факту на производстве чего ни коснись - конгломерат различных NP-трудных задач.
Как такие задачи решают.
а) Для малой размерности (n<= 20) лучше всего воспользоваться точным экспоненциальным алгоритмом, который называется "алгоритм с возвратом" или бэктрекинг. Алгоритмом с возвратом можно решить любую NP-трудную (полную) задачу за экспоненциальное время.
б) Если размерность средняя и задача псевдополиномиальная - то решают динамическим программированием.
в) Если задача оптимизационная (найти максимальное или минимальное решение), а размерность большая и/или задача трудная в сильном смысле - то можно действовать по-разному.
На крайних полюсах - приближенные и эвристические алгоритмы.
В чем разница между приближенным и эвристическим алгоритмом, если они оба решают задачу неточно?
I. У приближенного доказана оценка погрешности: знаем насколько наше решение может отклониться от оптимального в самом худшем случае. Найти такую оценку - доказать теорему. Тот алгоритм, которым мы будем решать задачу одномерной упаковки - FFD-алгоритм (First Fit Decreasing, первый подходящий в порядке убывания) - как раз относится к таким алгоритмам. Собственно, его можно применять к любой задаче на минимум, но именно для одномерной упаковки он поразительно хорошо работает! На очень сложных, специально сконструированных плохих примерах он отклоняется от оптимального решения не более чем на 22%. А на реальных наборах данных работает практически как точный. Для производства - самое то.
II. Эвристические алгоритмы - нам никто ничего не гарантирует. ХЗ, насколько эвристическое решение отклонится от оптимального. Пример - ГА, генетические алгоритмы - стильно, модно, молодёжно. Если соберётесь научную статью писать, в журнал посылать - берите ГА, не прогадаете
III. Ну и третий путь, которым я часто пользовалась - гибридные алгоритмы. Пример задачи. Госзакупки, на подразделение выделяется сумма денег, ее нужно выбрать. Есть список товаров, которые нужны, известна их стоимость. Только размерность очень большая: и сумма велика, и товаров много.
Как эта задача решается гибридным алгоритмом.
Товары сортируются по убыванию стоимости. Придумывается приближенный алгоритм, который выбирает большую часть суммы, в первую очередь забирая дорогие товары. А на втором этапе начинает работать точный алгоритм: остаток суммы набирается с точностью до нескольких рублей перебором не более 20 товаров.
1. NP-трудная - никто не знает, как решить её за полиномиальное время точным алгоритмом.
2. ... в сильном смысле - не решается за псевдополиномиальное время динамическим программированием.
На самом деле таких задач полно - и на производстве, и в науке. По факту на производстве чего ни коснись - конгломерат различных NP-трудных задач.
Как такие задачи решают.
а) Для малой размерности (n<= 20) лучше всего воспользоваться точным экспоненциальным алгоритмом, который называется "алгоритм с возвратом" или бэктрекинг. Алгоритмом с возвратом можно решить любую NP-трудную (полную) задачу за экспоненциальное время.
б) Если размерность средняя и задача псевдополиномиальная - то решают динамическим программированием.
в) Если задача оптимизационная (найти максимальное или минимальное решение), а размерность большая и/или задача трудная в сильном смысле - то можно действовать по-разному.
На крайних полюсах - приближенные и эвристические алгоритмы.
В чем разница между приближенным и эвристическим алгоритмом, если они оба решают задачу неточно?
I. У приближенного доказана оценка погрешности: знаем насколько наше решение может отклониться от оптимального в самом худшем случае. Найти такую оценку - доказать теорему. Тот алгоритм, которым мы будем решать задачу одномерной упаковки - FFD-алгоритм (First Fit Decreasing, первый подходящий в порядке убывания) - как раз относится к таким алгоритмам. Собственно, его можно применять к любой задаче на минимум, но именно для одномерной упаковки он поразительно хорошо работает! На очень сложных, специально сконструированных плохих примерах он отклоняется от оптимального решения не более чем на 22%. А на реальных наборах данных работает практически как точный. Для производства - самое то.
II. Эвристические алгоритмы - нам никто ничего не гарантирует. ХЗ, насколько эвристическое решение отклонится от оптимального. Пример - ГА, генетические алгоритмы - стильно, модно, молодёжно. Если соберётесь научную статью писать, в журнал посылать - берите ГА, не прогадаете
III. Ну и третий путь, которым я часто пользовалась - гибридные алгоритмы. Пример задачи. Госзакупки, на подразделение выделяется сумма денег, ее нужно выбрать. Есть список товаров, которые нужны, известна их стоимость. Только размерность очень большая: и сумма велика, и товаров много.
Как эта задача решается гибридным алгоритмом.
Товары сортируются по убыванию стоимости. Придумывается приближенный алгоритм, который выбирает большую часть суммы, в первую очередь забирая дорогие товары. А на втором этапе начинает работать точный алгоритм: остаток суммы набирается с точностью до нескольких рублей перебором не более 20 товаров.