Есть ли название для такого поиска по графику?

Question

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

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

Согласно моей математике, график, соответствующий указанной выше проблеме, будет иметь 2 ^ N узлов, с каждым шагом S в процессе сборки (поэтому 0 <= S <=N) состоящий из N!/ (S! * (NS)!) Узлы.Таким образом, существует N способов размещения первого компонента, (N ^ 2 - N) / 2 способа размещения второго компонента и так далее.Каждый узел будет иметь столько же родителей, сколько он имеет элементов в своем подмножестве N, а количество родителей и дочерних узлов, которое имеет узел, будет равно количеству элементов в N. </p>

O (2 ^ N)не решаемо ни для чего, кроме очень маленького N, но мне интересно, есть ли название для такого рода проблемы, чтобы я мог прочитать об этом подробнее.

(Заранее извиняюсь за плохое использование технической терминологии.)

Answer 1

Кажется, что это можно решить с помощью алгоритма топологической сортировки .

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

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

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