Ищете чистый и эффективный способ сопоставления набора данных с известными шаблонами.

Использование php5.2 и MySQL 4.1.22

Я столкнулся с чем-то, что сначала казалось простым, но с тех пор ускользнуло от меня в отношении простого и чистого решения.

У нас есть заранее определенные «пакеты» продукта. Пакет 1 может содержать продукты A, B и C. Пакет 2 может содержать A, C, D и G и т. д. Размер пакетов варьируется от 3 до 5 продуктов.

Теперь покупатель может выбрать любые 10 доступных продуктов и сделать «индивидуальную» упаковку. Поскольку у нас уже есть определенные предопределенные пакеты, мы хотели бы создать пользовательский пакет с меньшими существующими пакетами (для упрощения доставки), где это возможно.

Так, например, клиент выбирает создание «индивидуального пакета» продуктов A, B, C, D, E и F. У нас уже есть предопределенный пакет, содержащий A, B и C, который называется Foo. Таким образом, порядок будет таким: Foo, D, E и F.

Загвоздка в том, что у вас наименьшее количество отдельных предметов, за которыми следует наименьшее количество упаковок. Например:

Пользовательский пакет: A, B, C, D, E, F, G, H, I, J.

Стандартный пакет (1): A, B, C, D, E

Предопределенный пакет (2): A, B, C

Предопределенный пакет (3): D, E, F

Если я просто возьму самую большую спичку, то у меня будет 1 (5шт) упаковка и 5 отдельных предметов. Ни Пакет (2), ни (3) не могут быть собраны из оставшихся предметов.

Если я загляну глубже, я обнаружу, что, не собирая пакет (1), я могу вместо этого собрать пакет (2) и пакет (3). Это означает, что у меня есть 2 пакета и 4 отдельных предмета (лучший выбор в этом бизнес-правиле).

Поскольку я использую MySQL, я ограничен наличием только одного уровня подвыборки (насколько мне известно). Так что эту сортировку нужно будет выполнять в php. Я рассматривал использование array_intersect() для определения совпадений, но каждый способ, который я нашел, растет экспоненциально в отношении обработки, поскольку количество предопределенных пакетов растет линейно.

Я проверил это с парой других друзей-кодеров, и снова, хотя казалось, что должен быть простой ответ, мы все обнаружили, что это не так просто, как кажется. Итак, я решил опубликовать это здесь как хороший носилок для лапши. Заранее спасибо за ваше время!


mysql php pattern-matching
person Sumptin    schedule 09.04.2009    source источник
comment
+1 отличный вопрос, на который я понятия не имею, как ответить. Мне будет интересно посмотреть, что люди придумают   -  person Paolo Bergantino    schedule 10.04.2009
comment
Сколько продуктов у вас есть и сколько готовых пакетов? Есть несколько других возможных решений/оптимизаций, о которых я расскажу в зависимости от их размера.   -  person Chad Birch    schedule 10.04.2009
comment
Кроме того, может ли клиент выбрать один и тот же продукт несколько раз?   -  person Chad Birch    schedule 10.04.2009

Ответы (3)


arrow_upward
4
arrow_downward

Проблема вообще "тяжелая" (говоря с точки зрения вычислительной сложности). На самом деле, у меня в голове звенит колокольчик, который, вероятно, сводится к одной из тех классических алгоритмических проблем, таких как проблема с рюкзаком, но я не могу присвоить ей имя собственное.

Однако с таким небольшим проблемным пространством (они могут выбрать только 10 продуктов) должно быть довольно быстро просто переборщить. Когда кто-то отправляет пользовательскую сборку, просто рекурсивно атакуйте ее всеми возможностями и посмотрите, какая из них лучше.

То есть взять компоненты, которые они выбрали, и сначала попытаться удалить из него компоненты «Пакета 1». Если это возможно, возьмите оставшиеся компоненты и попытайтесь взять из него компоненты «Пакета 2» и т. д. Отслеживайте лучшее решение, которое вы нашли на данный момент.

Если это все еще недостаточно быстро (но я думаю, что, вероятно, будет, в зависимости от того, сколько у вас готовых пакетов), вы можете применить динамическое программирование для ускорения.

Отредактировано для добавления:

В зависимости от количества возможностей и того, сколько времени это на самом деле занимает, вы можете написать код, который я описал выше, а затем просто продолжить и предварительно вычислить все решения для каждой возможной комбинации. Затем, когда кто-то отправляет пользовательскую сборку, вам просто нужно получить ответ, а не вычислять его каждый раз с нуля.

Даже если вы не хотите предварительно вычислять их все, я бы посоветовал сохранять результат каждый раз, когда кто-то делает пользовательскую сборку, тогда в будущем, если кто-то еще сделает ту же пользовательскую сборку, вам не придется пересчитывать решение. .

person Chad Birch    schedule 09.04.2009
comment
неохотно +1, я печатал тот же самый ответ, когда получил сообщение о новых ответах :) - person Not Sure; 10.04.2009

arrow_upward
0
arrow_downward

Я предлагаю вам позволить клиенту помочь. На экранах выбора продуктов покажите, какие наборы в упаковке доступны, и позвольте им составить комбинации (соответствующие цены, чтобы суммы комбинезонов хватило на специальную обработку).

person dkretz    schedule 09.04.2009

arrow_upward
0
arrow_downward

Извините, что немного усложняю вашу задачу. :-)

Хотя вам может понравиться предварительный расчет возможных решений или позволить потребителям самим выбирать из предопределенных пакетов: что, если предопределенного пакета больше нет на складе?

Что делать, если в настоящее время не существует решения для выполнения заказа? Отправили бы вы часть заказа, и если да, то включили бы вы отдельные позиции, даже если бы знали, что позже сможете выбрать предопределенную упаковку?

И вы действительно уверены, что предопределенным пакетам не будет назначено какое-то «предпочтение»? Например, какой предопределенный пакет выбрать при заказе «ABCD», а предопределенные пакеты «ABC» и «BCD» существуют? Если, например, вы знаете, что предопределенного пакета «ABC» часто нет в наличии, то, возможно, это сделает «BCD» предпочтительным, когда это возможно.

Итак: возможно, вам нужно использовать какое-то моделирование, в котором вы можете легко изменить некоторые жестко закодированные правила, а не пытаться найти автоматизированное решение. Конечно, это может быть сам PHP.

person Arjan    schedule 09.04.2009
comment
К счастью, у нас никогда нет товаров на складе ;). Вы правы в отношении моделирования в том, что теперь оно предназначено для создания битовой маски возможных пакетов, поэтому вы можете применить бизнес-правило к маске, чтобы решить, какой выбор является оптимальным, без необходимости изменения кода. - person Sumptin; 11.04.2009