Дано:
склад с пронумерованными ячейками, в которых лежат различные товары.
один товар может лежать в нескольких местах.
задано, сколько нужно собрать на поддон товара A(1) N(1) штук, товара А (2) N(2) штук, ... товара А (m) N(m) штук
Надо:
рассчитать из каких ячеек брать и порядок обхода, чтобы длина пути была минимальна.
Если бы ячейки были фиксированными, то это алгоритм коммивояжера. Но тут можно варьировать, из каких ячеек брать.
Здравствуйте, Black-bear2, Вы писали:
BB>Если бы ячейки были фиксированными, то это алгоритм коммивояжера. Но тут можно варьировать, из каких ячеек брать.
Ясно, что эта задача "не проще" чем задача коммивояжера. Так что в общем случае — перебор.
Здравствуйте, Black-bear2, Вы писали:
V_>>Ясно, что эта задача "не проще" чем задача коммивояжера. Так что в общем случае — перебор. BB>ты бы хоть прикинул число вариантов, перед тем как советовать прямой перебор.
Что ты хочешь этим сказать? В коммивояжере тоже вариантов не мало, но, кроме перебора, она никак не решается. Есть достаточно эффективные алгоритмы перебора, типа ветвей и границ, в их сторону и надо смотреть. Можно использовать какие-нибудь априорные знания о задаче, чтобы этот перебор сократить. Если достаточно будет приближенного решения, можно какую-нибудь эвристику выдумать, но тут опять же нужны дополнительные данные о задаче.
Здравствуйте, Black-bear2, Вы писали:
BB>Подскажите алгоритм.
BB>Дано: BB>склад с пронумерованными ячейками, в которых лежат различные товары. BB>один товар может лежать в нескольких местах. BB>задано, сколько нужно собрать на поддон товара A(1) N(1) штук, товара А (2) N(2) штук, ... товара А (m) N(m) штук
BB>Надо: BB>рассчитать из каких ячеек брать и порядок обхода, чтобы длина пути была минимальна.
BB>Если бы ячейки были фиксированными, то это алгоритм коммивояжера. Но тут можно варьировать, из каких ячеек брать.
А как ячейки расположены? Как заданы расстояния между ними. Если, скажем на прямой или более-менее по сетке, то задача проще становится...
Здравствуйте, Au1, Вы писали:
Au1>А как ячейки расположены? Как заданы расстояния между ними. Если, скажем на прямой или более-менее по сетке, то задача проще становится...
Ячейки — это поддономеста. Выстроены прямыми рядами. Между рядами есть переходы.
Здравствуйте, Black-bear2, Вы писали:
BB>Дано: BB>склад с пронумерованными ячейками, в которых лежат различные товары. BB>один товар может лежать в нескольких местах. BB>задано, сколько нужно собрать на поддон товара A(1) N(1) штук, товара А (2) N(2) штук, ... товара А (m) N(m) штук
BB>Надо: BB>рассчитать из каких ячеек брать и порядок обхода, чтобы длина пути была минимальна.
Интересно, а нельзя ли выбором расположения товаров свести задачу к динамическому программированию? А следовательно и к простому решению?
Еше мне показалось, что общая длина пути возможно не самый лучший критерий. Не надо ли учитывать и вес товаров (очень тяжелые брать последними)?
Здравствуйте, Black-bear2, Вы писали:
BB>Здравствуйте, Au1, Вы писали:
Au1>>А как ячейки расположены? Как заданы расстояния между ними. Если, скажем на прямой или более-менее по сетке, то задача проще становится...
BB>Ячейки — это поддономеста. Выстроены прямыми рядами. Между рядами есть переходы.
Действительно, задача коммивояжера получается. Вам ведь нужно вернуться в исходную точку? Есть следующие мысли:
1. когда вершины на плоскости фиксированы, то есть довольно простой способ построения пути, который хуже оптиального не более, чем на 23% (кажется). Суть в том, что нужно строить несамопересекающийся многоугольник. Прием примерно такой: выбираем самую левую и самую правую точки. дальше (надо подумать динпрогом или перебором) делим остальные точки на 2 множества: по которому идем слева направо "по верху" и справа налево "по низу", чтобы путь был оптимальным. Подробнее можно искать в литературе. В Кормене-Лейзерсоне-Ривесте есть не то описание такого решения, не то ссылки на литературу. Навскидку не помню и под рукой нет.
2. Это ведь нужно будет делать не один раз? И нужно в принципе оптимизировать сумму всех путей. Т.е. ничего страшного, например, что в этот раз возьмем чего-то не там, зато в следующий раз идти будет ближе. Тут много чего можно придумать, как оптимизировать выбор множества вершин. Одна из идей: если есть несколько вершин из которых надо брать один и тот же товар, то надо постараться, чтобы полностью опустошить максимальное количество из них.
3. Чтобы путь был короче, нужно, чтобы все вершины лежали "в куче". Как это сделать:
а. Проанализировать какой товар с каким вместе берут чаще и при приходовании стараться класть их рядом. Можно вводить какие-то весовые функции, по которым выбирать предпочтительную ячейку для прихода.
б. При расходовании искать множество вершин, диаметр которого минимален и расстояние до входа минимально среди всех таких. Искать можно жадно (надо доказать, конечно). Фиксируем "центр" множества и жадно собираем все нужные ящики, которые ближе к центру и в которых лежит то, что надо. "центр" нужно начинать перебирать от входа — чтобы отсечений в переборе было больше.
