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