Проблема заключается в следующем: Учитывая подмножество ч.у.м. в S найти максимальные элементы S.Нахождение максимальных элементов подмножества ч.у.м. в
Для примера рассмотрим Хасс схему посета в http://ndp.jct.ac.il/tutorials/Discrete/node34.html. Учитывая его подмножество ex: {12, 2, 8}, максимальные элементы равны 12 и 8.
Я не знаю, насколько я точно описываю проблему. Я думаю, что проблема может заключаться в некоторой сортировке или вычислении транзитивного закрытия, но я немного смущен.
Не могли бы вы дать мне некоторый подход к быстрому алгоритму? Я хотел бы сохранить его в O (n^2)
Спасибо.
Немного разъяснений. Мое приложение использует графики RDF. Два узла сравнимы, если существует конкретное ребро, которое представляет отношение <. Два узла могут быть сопоставимыми, если существует такое явное отношение или неявное транзитивное.
Предположим, что диаграмма hass - это точно мой график RDF. Если я начну с 2, сделав поиск по глубине, как я узнаю, что 8 и 12 не сопоставимы? Они могут быть не явными, но они могут быть неявно.
Если два узла сопоставимы по порядку. отношение упорядочения, то по крайней мере один из них должен иметь узел-преемник, который «передает» отношение упорядочения, правильно? –
Да, это правильно. Однако, если у вас есть путь a-b-c, a и c «неявно» сопоставимы. Исходя из этого, я подозреваю, что мне приходится вычислять транзитивное замыкание каждого узла подмножества и производить «очистку» сопоставимых элементов. – Alex
Предполагая, что a-b подразумевает a