Сравнение* древовидных графов

[IvanPonomarev]

Несколько лет назад я решал подобную задачу, реализуя алгоритм FastMatch, описанный здесь: http://ilpubs.stanford.edu:8090/115/1/1995-46.pdf На выходе получался скрипт с перечислением команд, которые нужно произвести с деревом в начальном состоянии, чтобы получить дерево в конечном состоянии, и причём авторы алгоритма стремились к тому, чтобы этот скрипт был близок к минимально возможному по длине.

У вас ноды идентифицируются своими номерами, все номера разные. А разве двух нерализичимых нод не может оказаться в двух местах дерева?

[tooteetoo]

Не совсем понял ваш вопрос. Ноды идентифицируются своими номерами, но сравнивать эти номера нет смысла, т.к. они не несут в данном случае информации. Информация лежит в kts_item_id, они и сравниваются. Два одинаковых kts_item_id не могут входить в один узел.

[IvanPonomarev]

Два одинаковых kts_item_id не могут входить в один узел — но они могут входить в разные узлы?

[tooteetoo]

Да

[Alex_PLM]

Поясните, пожалуйста, для чего вам сравнение составов?
Вы сами разрабатываете систему для АКТПП?
Почему не используете готовое решение — PLM-систему?

[tooteetoo]

Да, АКТПП разрабатывается, но что называется «под свои хотелки».
Есть дерево состава на заказе, по изменениям за день оно пересчитывается. И после этого пересчета непонятно какие узлы куда пропали. Неясно что осталось на месте, а что ушло. Да, можно сравнить два линейных списка и посмотреть количество чего изменилось, что добавилось, что убавилось. Проблема в том, что в зависимости от входимости элемент имеет определенные свойства. Например, маршрут изготовления. Для одной части машины деталь делается одним маршрутом, а для другой другим маршрутом, хотя это одна и та же деталь. И всё это части одного дерева, которое нельзя делить. Сейчас если такое встречается, то приходится подбивать руками. Такое сравнение это первый шаг. Во-первых, видно только изменения. Во-вторых, я думаю, что можно будет найти конкретный элемент (item_id) старого дерева в новом и указать что куда ушло. Думаю, что это сократит ручную работу.
PLM-система есть, но подобный функционал она не дает.

[Alex_PLM]

"Например, маршрут изготовления. Для одной части машины деталь делается одним маршрутом, а для другой другим маршрутом, хотя это одна и та же деталь. "
В Plm выделяют конструкторское представление эси и технологическое. Грубо говоря, конструкторское — представляет собой спецификацию, технологическое — последовательность сборки.
Опять же в Plm есть коннекторы к erp-системам.
PS. Часом не лоцман используете?
PSS. С планированием не знаком, поэтому плохо представляю данную проблему

[tooteetoo]

Лоцман. Он дает возможность задать маршрут в зависимости от вышестоящей детали, но только на 1 уровень вверх. В моем случае вышестоящая деталь, от которой зависит маршрут, может быть выше на несколько уровней.
Проблема в том, чтоб запланировать одну и ту же деталь в разные цеха в зависимости от того во что она входит. При этом изменения от конструктора идут во время изготовления изделия и эту деталь могут запросто выкинуть из состава или добавить еще. А потом гадай что куда, потому что изменений много и спецификация пересчитывается полностью.

[kostey2204]

Вы показали схему таблицы MR_ORDER_TREE в которой хранится дерево изделия.
В ней присутствует поле «is_item_buy», означающее «Покупное ли изделие».

Означает ли это что изделие может быть собственного изготовления в случае вхождения в сборку А и покупным в случае вхождения в сборку Б?
(Не могли бы вы привести реальный пример из вашей АКТПП-системы)

У нас, например, данный признак относится к изделию не зависимо от его вхождений.

[tooteetoo]

Промахнулся комментарием

[tooteetoo]

В данный момент изделие является покупным вне зависимости от входимости. Как и у вас. Мы используем Лоцман, там покупка это атрибут изделия. Это как правило различные стандартные изделия (гвозди, гайки, болты и т.п.).
Так же, иногда, некоторые детали или сборки оказывается дешевле в данный момент купить чем изготавливать самостоятельно или наоборот. Поэтому на них меняется признак покупки. Само собой, это затрагивает все заказы куда данный элемент входит. Изменение покупки приходит из PLM-системы, и такие детали нужно убирать из планов или планировать для каких-то цехов.
В АКТПП-системе заложено немного больше. Там деталь может быть покупной в зависимости от маршрута.

[bo0rsh201]

Простите, а почему нельзя было вести рядом лог изменений и вообще не решать описанную проблему? :-)
Или как минимум сильно упростить

[tooteetoo]

Такая мысль была изначально. Но тут есть такие нюансы. Во-первых, изменения приходят в виде узла и изменений по входящим в него элементам первого уровня. Поэтому если вы замените в машине, например, один статор на другой, то вернетесь к описанной выше задаче. Потроха у них тоже нужно сравнить. Не говоря уже о ситуациях, когда удаляется и вставляется больше одной сборки. Во-вторых, изменений идет много и идут они часто. Постоянные пересчеты не пойдут на пользу серверу.
Либо вы какой-то другой лог предложите?)