История об использовании теории графов для решения задач промышленного производства.

Введение

Я работал с инфраструктурой всю свою карьеру, но иногда мне приходилось делать что-то другое. Разнообразие — одна из вещей, которые я нашел привлекательным в ИТ, когда решил изучать информатику. Это примерно один из тех случаев, когда я вызвался принять участие в кайдзен-проекте на своем рабочем месте. Кайдзен представляет собой практику непрерывного совершенствования и довольно распространена в промышленных компаниях (я работал в одной из них), во многом как бережливое производство или шесть сигм.

В то время я активно занимался настройкой Oracle SQL (не совсем моя сфера деятельности, но поскольку я отвечал за базы данных и серверы, когда возникала проблема с производительностью, меня обычно просили помочь, и в итоге я оказался становится достаточно опытным). Предполагалось, что ИТ поможет придумать идеи для программы, и, слишком часто проверяя, как плохо спроектированные/написанные программы можно сделать значительно более эффективными, я вроде как присоединился к точкам. Я не был полностью уверен, что это настоящий кайдзен-материал, но разработчикам, с которыми я работал в команде, похоже, понравилась идея, и поэтому я попросил их подумать о серьезной проблеме, которая выиграла бы от сокращения времени выполнения.

Оказалось, что существует семейство связанных задач, связанных с производственным процессом, где нужно определить количество материалов, необходимых для изготовления определенного набора продуктов. Это могут быть как конечные продукты, так и промежуточные. Товары производились с использованием определенного количества различных компонентов, и часто существовало несколько способов изготовления каждого продукта, которые включали различные виды и/или количество входных материалов. Полуфабрикаты сами были сделаны из компонентов более низкого уровня, и так продолжалось до тех пор, пока вы, в конце концов, не достигли сырья.

Все эти отношения были зафиксированы в таблицах базы данных Oracle, а программы, использовавшиеся для решения этой проблемы, были написаны на PL/SQL, и их выполнение могло занять два или три часа, в зависимости от набора входных данных.

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

Проблема

Таблица, в которой записано отношение «сделано из», представляет собой DAG (направленный ациклический граф) со взвешенными ребрами, G=(V,E), где каждая вершина в V является либо сырьем, либо промежуточным продуктом, либо конечным товаром, а каждое ребро представляет собой тройку (отец, сын, количество). В нем было от 30 до 40 тысяч строк.

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

Например, если бы мы использовали DAG для представления того, как приготовить омлет, мы могли бы ожидать найти ребро (смесь омлета, яйцо, 4), то есть требуется 4 яйца для приготовления омлета. Точно так же будут края, обозначающие количество молока, соли и перца, которые нужно добавить в смесь, а также любые другие ингредиенты, которые вы можете себе представить (я часто использую розмарин и тимьян). В реальном случае, как и в этом кулинарном примере, веса ребер были положительными и в принципе могли быть как натуральными, так и действительными числами в зависимости от материалов.

Основная проблема, которую нам нужно было решить, заключалась в том, чтобы при заданном наборе продуктов, которые нужно изготовить, найти подробный перечень сырья, необходимого для каждого из них. Они назвали это «проблемой планирования», и в терминах нашего графа это было аналогично нахождению всех путей от узлов в заданном наборе до конечных узлов (сырья). Если мы определим стоимость пути как произведение весов его ребер, тогда количество элемента t, необходимое для создания произведения s во входном наборе, равно сумма затрат всех путей от s до t.

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

Важно отметить, что в данном случае недостаточно просто вычислить транзитивное замыкание (или его часть) графа, потому что на самом деле нам нужно вычислить стоимость всех возможных путей между двумя узлами, чтобы чтобы узнать количество одного, необходимого для производства другого. Таким образом, обычные алгоритмы транзитивного замыкания, которые заботятся только о достижимости, неприменимы, и мы не можем уменьшить объем работы, отбрасывая пути (например, идентифицируя сильно связанные компоненты). Вместо этого мы должны сосредоточиться на порядке, в котором мы следуем краям.

Оригинальный алгоритм

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

Алгоритм, использовавшийся в то время, начинал с требуемого количества продуктов, которые необходимо произвести, и обходил граф с использованием подхода поиска в ширину (BFS), вычисляя на каждом этапе необходимое количество их потомков с использованием весов в ребрах. . Например, если бы нашим входным набором был узел A, программа начала бы с обхода ребра (A,B,2), чтобы определить, что потребуется (как минимум) 2 B. Затем он проверит ребро (A,C,3) и добавит 3 C к требуемому списку элементов. После этого он перейдет к ребру (A,D,1) и так далее. В конце концов, он доберется до ребра (C, B, 1) и поймет, что ему нужно увеличить количество B в нашем списке покупок с 2 до 5 из-за 3 C.

Прогресс легче отслеживать, если мы упорядочим вычисления по глубине и представим частичные требования, определенные до сих пор, как множество R={(vi, количество vi)}, а текущая линия фронта — набор F узлов, посещенных на текущей глубине:

  1. Когда мы начинаем, мы расширяем узел A, следуя ребрам (A, B, 2), (A, C, 3) и (A, D, 1). После этого наш частичный результат будет равен R={(B,2), (C,3), (D,1)}, а наша линия фронта F есть {В,С,D}.
  2. На глубине 2 мы расширяем узлы B, C и D по ребрам (B, E, 2), (C, B, 1), (C, D, 2) и (D, B, 4). R теперь равно {(B,9), (C,3), (D,7), (E,4)}, а фронт расширения равен F= {Б,Г}.

На этом можно остановиться, так как проблема с этим подходом уже очевидна: при рассмотрении ребра (v,w,k) реальное необходимое количество v все еще неизвестно. . Таким образом, когда мы определяем количество w, это также не окончательное число, так как это ребро, возможно, придется повторить позже. На итерации 3 нам нужно будет расширить узлы B и D во второй раз, а на глубине 4 нам все еще придется расширить B еще раз. Это явно неэффективно.

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

Лучшее решение

Поскольку обе проблемы (планирование и программирование) схожи, я сосредоточусь здесь на общем случае получения списка сырья, необходимого для производства каждого из продуктов входного набора. Поскольку я работал с входным графом G, я решил представить результат также в виде графа G* с ребрами (u,v,k), так что u был конечным продуктом, v сырьем, а k количеством v > требуется, чтобы сделать нужное количество u.

Чтобы не выполнять одну и ту же работу много раз, было бы лучше, если бы мы могли пройти по графу в таком порядке, который гарантировал бы, что мы не расширим данный узел, пока не пройдем все его входящие ребра, т. е. пока мы не определим окончательный количество этого узла, которое нам потребуется. Это гарантировало бы нам, что после того, как мы пройдем по ребру (v,w,k), нам не придется повторять это позже.

Если я до сих пор не утомил вас до смерти, вы, вероятно, думаете: «Эй, да это же топологический порядок, о котором вы говорите!», и вы правы. При работе с DAG такой порядок существует и является старым добрым топологическим порядком. Должен признаться, однако, что в то время, когда происходит моя история (еще в 2005 году), я либо никогда не слышал об этом ни единого слова, либо вообще не имел никаких воспоминаний, и поэтому мне пришлось во всем разбираться самому…

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

Алгоритм 1

Ввод: G=(V,E); S={s1,…,sn} ⊆ Vмножество узлов без входящих ребер (произведения мы хотим сделать); сумма(v), v ∈ S, сумма, которую нужно сделать для каждого из них.

F,G* ← ∅,(∅,∅)
For each node v in G
  id(v) ← # of edges in E reaching v  // compute node in-degree 
  If id(i)=0, add v to F  // add roots to F
While there is some v in F  
  // expand v  
  For each edge (v,w,kw) in G 
    If v ∈ S, add (v,w,amount(v).kw) to G*
    Else
      For each edge (u,v,kv) in G*
        If there’s no (u,w,kw’) in G*, add (u,w,kv.kw) to G*
        Else, update its weight to kw’+kv.kw
    id(w) ← id(w) - 1
    If id(w)=0 and w has children in G, place w in F
  Remove v from F 
  Delete from G* all edges reaching v
Return G*

Этот алгоритм проходит по всем ребрам в G только один раз, отклоняясь от входного набора S. В каждой итерации ребра (v,w,k) на графе результатов G* представляют окончательное количество w, необходимое для производства каждого продукта. в S для каждого узла w/id(w) = 0 (это означает, что все его входящие ребра уже учтены). Процесс можно рассматривать как распространение фронта F, начиная с входного набора и заканчивая конечными узлами.

Несколько комментариев перед продолжением:

  • Степень вхождения можно легко сохранить и поддерживать в таблице базы данных, которая содержит отношение «сделано из». Это избавляет нас от необходимости вычислять его после загрузки графа, что делает ненужным цикл инициализации.
  • Операция, выполняемая на G, представляет собой поиск сыновей данного узла, в то время как на G* вместо этого нам нужно получить его родителей, поэтому каждый граф может быть реализован по-разному. оптимизировать собственный вариант использования.
  • На последнем шаге основного цикла удаляются ребра, связывающие конечные продукты с промежуточными. При желании этот шаг можно пропустить, чтобы построить график, отображающий количество каждого компонента, необходимого для производства продуктов в S, а не только сырье.

Мы можем проанализировать объем работы, выполняемой алгоритмом, следующим образом:

  • На этапе инициализации каждое ребро рассматривается один раз для вычисления степени входа каждого узла, что требует O(|V|+|E|) операций.
  • Основной цикл рассматривает каждое ребро в G один раз (|E|). Для каждого ребра (v,w) в G ребра (u,v) в G*, ​​поступающие at v считаются обновляющими (u,w) в G*, ​​где u∈ S . Для этого требуется O(|E|.|S|) операций.

Таким образом, общая сложность алгоритма 1 составляет O(|V|+|E|+|E|.|S|).

Теперь предыдущий алгоритм следует всем ребрам в G, даже тем, которые отходят от продуктов, которые нам не нужно производить, и, таким образом, лучше всего подходит для случая, когда S включает все конечные продукты в G. Альтернативный подход — работать с новым графом G’, состоящим только из узлов и ребер, достижимых из S. Алгоритм очень похож, но сначала нам нужно получить G’:

Алгоритм 1.1:

// Obtain G' 
F,G' ← S,(Ø,Ø)
While there is some node v in F
  For each edge (v,w,k) in G
    If w is not in G', set id(w) ← 1
    Else, set id(w) ← id(w)+1
    Add (v,w,k) to G'
    If w is not marked as expanded, add w to F
  Mark v as expanded
  Remove v from F

// Expand S in G'
F,G* ← S,(∅,∅)
While there is some node v in F  
  // expand v  
  For each edge (v,w,kw) in G' 
    If v ∈ S, add (v,w,amount(v).kw) to G*
    Else
      For each edge (u,v,kv) in G*
        If there's no (u,w,kw’) in G*, add (u,w,kv.kw) to G*
        Else, update its weight to kw’+kv.kw
    id(w) ← id(w) - 1
    If id(w)=0 and w has children in G', place w in F
  Remove v from F 
  Delete from G* all edges reaching v
Return G*

Первый цикл строит подграф G’ и одновременно вычисляет степень вхождения его узлов. Поскольку мы инициализируем набор F нашим входным набором S, и во время расширения мы используем только степень вхождения узлов w, так что есть некоторое ребро (v,w) в G', нам не нужно проверять все узлы в G и требуемый объем работы составляет всего O(|V'|+|E'|). Затем основной цикл рассматривает только ребра в G’ со стоимостью O(|E’|.|S|). Таким образом, общая стоимость составляет O(|V'|+|E'|+|E'|.|S|), что делает этот вариант более эффективным, чем алгоритм 1, кроме того, что он применим к любому входному набору.

Как я упоминал ранее, материалы, необходимые для изготовления каждого продукта, определяются путем построения путей между ним и конечными узлами. Если мы подумаем об инварианте в основном цикле алгоритма 1 (когда мы расширяем один узел, мы уже знаем количество этого узла, необходимого для производства каждого из продуктов в S) с этой точки зрения, мы можем видите, мы строим эти пути постепенно, расширяя их по одному ребру за раз, пока не достигнем конечных узлов.

И наоборот, проблема может быть решена путем инвертирования порядка распространения для построения путей, начинающихся с конечных узлов. В этом случае мы придумываем новый инвариант: на каждой итерации все «закрытые» узлы имеют количество каждого конечного узла, необходимое для их создания. Все, что нам нужно сделать, это удлинить пути, пока мы не достигнем узлов во входном наборе S, избегая закрытия узла, пока мы не пройдем все ребра, отходящие от него.

Чтобы построить график результатов из конечных узлов, мы можем использовать рекурсивный алгоритм (любезно предоставленный моим коллегой Серджио Сориа) для обхода исходного графика:

Алгоритм 2

Ввод: G=(V,E); S={s1,…,sn} ⊆ V набор продуктов для производства; сумма(v)/v∈ S, количество каждого продукта, которое нужно сделать.

G* ← (∅,∅)
For each v in S
  expand(G,v,G*) 
For each v in S
  For each edge (v,w,k) in G*
    // multiply by the desired quantities to make
    Update its weight to amount(v).k 
expand (graph G, node u, graph G*)
  For each edge (u,v,k) in G
    If v is a terminal node, accumulate(G*,u,v,k) 
    Else
      If v is not marked, expand(G,v,G*)
      For each edge (v,w,k') in G*
        accumulate (G*,u,w,k*k')
  Mark v as expanded
accumulate (graph G*, node v, node w, amount k)
  If (v,w,k') exists in G*, update its weight to k'+k
  Else, add (v,w,k) to G*

В этом случае результирующий граф G*, возвращаемый алгоритмом, включает ребра для всех путей к конечным узлам в исходном графе G, а не только начиная с узлов в S (конечные продукты), но и из промежуточных узлов. Как и в алгоритме 1, мы можем выбрать, возвращать ли все ребра или только те, которые связывают конечные продукты и сырье. Чтобы сделать последнее, мы можем создать новый граф в последнем цикле, фактически принимая во внимание только ребра, начинающиеся с узлов в S.

Хотя алгоритм 2 является рекурсивным, поскольку порядок, используемый для обхода исходного графа, тот же (мы просто инвертируем смысл, двигаясь снизу вверх, а не сверху вниз), вычислительная стоимость будет по-прежнему аналогична алгоритму 1. , Хотя и DFS, и BFS дают плохие результаты, расширение узлов в топологическом порядке сводит к минимуму объем работы. Мы можем думать о процессе как о следовании частичному порядку, заданному максимальным расстоянием, на котором мы встречаем узел v, если мы отходим от входного набора.

Пара вещей, о которых стоит упомянуть: во-первых, хотя предыдущие алгоритмы строят пути и вычисляют топологический порядок одновременно, независимо от того, в каком смысле происходит обход графа, между обеими задачами нет реальной зависимости. Во-вторых, для каждого входного набора S топологический порядок достижимых из него узлов включается в порядок всего графа, то есть в порядок, построенный с учетом всех конечных продуктов. Оба наблюдения подсказали идею предварительного расчета порядка для ускорения работы алгоритма. Например, это позволило бы нам переписать нисходящий алгоритм следующим образом:

Алгоритм 3

Ввод: G=(V,E); S={s1,…,sn} ⊂ V, множество узлов без входящих ребер ( изделия, которые необходимо изготовить); сумма(v), v∈S, сумма, которую нужно сделать из каждого; order[0..|V|-1], массив, содержащий вершины в V, отсортированные в топологическом порядке.

i,G* ← 0,(∅,∅)
While i < |V|
  v ← order[i]
  // expand v  
  For each edge (v,w,kw) in G 
    If v ∈ S, add (v,w,amount(v).kw) to G*
    Else
      For each edge (u,v,kv) in G*
        If (u,w,kw’) is already in G* update its weight to kw’+kv.kw
        Else, add (u,w,kv.kw) to G*
  Delete from G* all edges reaching v
  i ← i+1
Return G*

В этом случае, поскольку мы уже знаем, какую вершину выбирать на каждой итерации, мы можем пропустить часть инициализации, и нам не нужно отслеживать количество уже учтенных входящих ребер, чтобы решить, когда данный узел готов к работе. быть расширен. Таким образом, вычислительная стоимость снижается до O(|E|.|S|).

Побочным и довольно интересным эффектом этого подхода является то, что благодаря нашему второму наблюдению перед представлением алгоритма 3, поскольку нам не нужно вычислять порядок по мере продвижения, его можно использовать для расширения входного набора S, даже если он не равен набору всех конечных продуктов, без необходимости обхода всего графа, и без необходимости сначала вычислять подграф G'. Это можно сделать с помощью модифицированной версии алгоритма 1 следующим образом:

Алгоритм 3.1:

min_depth,A,G* ← ∞,S,(∅,∅)
While A is not empty
  F ← A
  While there is some v in F
    // expand v
    For each edge (v,w,kw) in G 
      If v ∈ S, add (v,w,amount(v).kw) to G*
      Else
        For each edge (u,v,kv) in G*
          If (u,w,kw’) is already in G*
            update its weight to kw’+kv.kw
          Else, add (u,w,kv.kw) to G*
          If order(w) < min_depth and w isn't a terminal node
            min_depth,A ← order(w),{w}
          Else if order(w) = min_depth and w isn't a terminal node
            Add w to A
    Remove v from F
    Delete from G* all edges reaching v
 Return G*

В этом случае сложность снижается до O(|E'|.|S|), где E' — множество ребер в подграфе G' (подграф, к которому можно получить доступ из входного набора S).

Если топологический порядок не был рассчитан заранее, мы, конечно, можем сделать это перед использованием алгоритма 3.1 со стоимостью O(|V'|+|E'| ), и в этом случае общая сложность оказывается равной O(|V'|+|E'|+|E'|.| S|), как и в алгоритме 1.1. Таким образом, оба подхода эквивалентны с точки зрения работы. Однако может иметь смысл использовать алгоритм 3.1 при выполнении повторяющихся вычислений с разными входными наборами в одном и том же графе, сначала вычисляя топологический порядок всего графа. Этот порядок можно использовать повторно до тех пор, пока топология графа не изменится, что сохраняется при обновлении весов. Однако если ребра добавляются или удаляются, это может потребовать обновления порядка каждого узла, достижимого из дочерней вершины, а это недешево.

Еще одна идея, которую мы сочли интересной, заключалась в возможности сохранения результатов после их расчета. Учитывая G=(V,E), если мы назовем Pij набором всех путей из vi в vj в G, мы хотим получить G+=(V ,E+), где (vi,vj,cij) ∈ E+ тогда и только тогда, когда v j достижим из vi в G, и его вес cij = ∑cost(p) ∀p∈Pij. Путь p в G — это последовательность смежных ребер, а его стоимость, cost(p), — это произведение весов ребер. Используя это определение, мы можем расширить понятие транзитивного замыкания невзвешенного графа, и в соответствии с этим мы можем думать о G+ как о транзитивном замыкании G.

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

Если мы сохраняем транзитивное замыкание исходного графа, возникает вопрос, насколько дорого его обновить по сравнению с выполнением нового расширения на G. Изменения в графе G могут заключаться в добавлении или удалении ребер и вершин. В каждом случае мы хотим видеть влияние этих изменений на G+. Вызов Phil подмножества Phl путей от vh до vl, проходящих через vi, интересное свойство, которое выполняется в G+, заключается в том, что

∑ cost(p) ∀p∈Phil = chi.c иль

В частности, если мы расширим обозначения, позволив Phijl обозначать {p ∈ Phl / (vi ,vj,k) является частью p}, и заметив, что

Phijl = {p'(vi,vj)p' ' / p' ∈ Phi и p'' ∈ Pjl},

мы можем заключить, что

∑ стоимость(p) ∀p∈Phijl = ∑ стоимость(p').k .cost(p'') ∀(p',p'')/p '∈Phi и p''∈Pjl = chi.k.cjl

И это позволяет нам легко определить влияние модификаций. Например, предположим, что мы стираем ребро (vi,vj,k). Затем мы должны:

  • ∀h/(vh,vi) ∈ E+: удалить (vh, vя)
  • ∀l/(vj,vl) ∈ E+: удалить (vj,v л)
  • ∀h,l/(vh,vi) и (vj,vl) ∈ E+ : обновить вес (vh,vl) до chl'= chl-спривет.к.сjl

Этот последний пункт выглядел особенно затратным, так как нам нужно обновить все ребра (vh,vl), чтобы vh был предком из vi и vl является потомком vj. Это если у нас есть a предки vi (имейте в виду, что это все предки, а не только прямые предки в исходном графе!) и d потомки vj, нам потребуется обновить ребра a.d. Компромисс между обновлением замыкания и выполнением расширения с нуля будет зависеть от исходного графа и внесенных в него изменений, но идея не выглядела многообещающей, и мы отказались от нее.

Реализация и результаты

Поскольку данные хранились в базе данных Oracle, а исходным кодом был PL/SQL (с которым разработчики были наиболее знакомы), такой выбор казался естественным. Единственной проблемой было найти подходящий способ представления графиков. Нам нужна была структура данных, которая позволяла бы эффективно извлекать родительские или дочерние элементы, а также добавлять и удалять ребра. PL/SQL предоставляет тип коллекции, который реализует словарь и был очень полезен для этой проблемы: ассоциативные массивы, также известные как индексируемые таблицы. Я использовал его как для реализации словарей, так и для наборов. Вот пакет, реализующий алгоритм 1.1 на основе демонстрационной таблицы:

Мы использовали аналогичный пакет, чтобы переписать программы, которые работали так плохо, и контраст был разительным. Пакеты, выполнение которых занимало два часа, теперь решались примерно за пять секунд. На следующем рисунке показан пример запуска с демонстрационным набором данных:

Послесловие

Работать над этим проектом было весело. Мне удалось пообщаться с людьми из разных слоев общества и узнать об интересном процессе, и, в конце концов, нам удалось изменить ситуацию и применить теорию для решения реальной проблемы. И хотя наша работа не получила приз как лучший проект, надеюсь, Деминг и Оно-сенсей одобрительно кивнули бы нам…