Помогите определить, является ли конкретная проблема классической проблемой Comp Science

Question

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

Я обрисую это в общих чертах ниже:

Скажем, существуют разные типы виджетов .... называйте их ...

Виджет типа A

Виджет типа B

Widget-Type A имеет различные серийные число

Widget-Type B имеет различные серийные число

Кроме того,

Вы можете сказать, что такое тип виджета (A или Б) на основании серийного номера в одиночестве. Серийные номера прилагаются дата сборки (т.е. 2010-08-10) ... если серийный номер существует, но дата отсутствует, Виджет существует, но не закончен строится.

Виджет типа B может содержать (один или несколько из) детали из виджета типа А; следовательно, Widget-Type B серийный номер может иметь список субсерийного числа от того из A.

Аналогично, виджет типа A может содержать (одна или несколько) частей из Виджет-Тип B; следовательно, Widget-Type Серийный номер А может иметь список субсерийные номера от B.

Наконец,

Существует виджет типа C

Виджет типа C может существовать только (быть встроенный), если дан виджет типа A, что Виджет типа А имеет дату сборки добавлен в сериал, и все это соответствующие субсерийные номера (от Виджеты типа B) имеют даты сборки добавлен в сериал.

Опять же, вы можете иметь другой случай что виджет типа C может существовать только построен), если дан виджет типа B, что Виджет B Типа имеет дату сборки добавлен в сериал, и все это соответствующие субсерийные номера (от Widget-Type As) имеет даты сборки добавлен в сериал.

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

Я знаю, что это было довольно скучное описание, но есть ли идеи, если это вариант какой-либо распространенной проблемы информатики?

Answer 1

Я не думаю, что это решение, но идея того, как вы могли бы решить эту проблему. Справедливо ли предположить, что проблема заключается в упорядоченной зависимости? Для создания виджета C необходимо создать виджет A и виджет B. А для создания виджета A может существовать зависимость от виджета B (и, возможно, существуют также циклы, но, конечно, с разными значениями серийных номеров).

Учитывая вышесказанное, вы можете представлять виджеты как ациклический ориентированный граф, не так ли? Направленное ребро между двумя узлами (виджетами) определяет зависимость. Например, Wdget C <- {Виджет A, Виджет B}. Затем вы можете использовать <a href="http://www.brpreiss.com/books/opus5/html/page555.html#SECTION0017330000000000000000" rel="nofollow noreferrer"> топологический обход , чтобы получить правильный порядок производства.

Опять же, я не уверен, что это ответ, который вы ищете, но из того, что я понял из определения проблемы, я думаю, что это возможно.