Есть ориентированный граф, в вершинах которого стоят волшебные ящики. В волшебных ящиках либо лежат фрукты, либо пусто. В каждом ящике могут лежать фрукты только одного вида и определенного свойства (например, только красные яблоки или только зеленые бананы). В каждой вершине графа стоит по одному ящику для каждого вида фруктов (в итоге, в каждой вершине могут быть, например, зеленые яблоки и желтые бананы, но не может быть зеленых и красных яблок). Ящик умеет реплицировать фрукты, то есть, если в ящик положить один зеленый банан, то из ящика потом можно доставать их до бесконечности. Есть вершина, которая считается начальной. По определению любая вершина графа из нее достижима. В начальную вершину помещается обкуренный ёжик. Обкуренный ёжик действует по следующему алгоритму:
1. Случайным образом выбирает в какую из сопряженных вершин ему идти.
2. Придя в нее, случайным образом решает идти ему дальше или возвращаться.
3. Если он решает возвращаться, он берет по одному фрукту из каждого волшебного ящика и идет назад.
4. Придя назад, он проверяет ящик для каждого из принесенных фруктов, если он пустой, ежик кладет туда фрукт, иначе он фрукт выкидывает. После этого, если он снова решает возвращаться, он снова берет по фрукту из каждого ящика.
5 Процесс повторяется до стабилизации в исходной вершине (т.е. до тех пор, пока состояние исходной вершины не будет оставаться постоянным, вне зависимости от действий ежика).
Очевидно, что стабилизация достижима (т.к. ящиков конечное число, а состояние ящика, где уже что-то лежит не может измениться). Очевидно, что существуют системы, для которых стабильные состояния исходной вершины зависят от порядка действий обкуренного ёжика и системы, для которых порядок действий обкуренного ёжика не важен.
Задача: написать алгоритм, определяющий, зависит ли стабилизированное состояние исходной вершины от порядка действий обкуренного ёжика, и если такой зависимости нет, вычисляющий стабилизированное состояние исходной вершины.
Предложения по более простой формулировке данной задачи тоже будут очень полезны.
Здравствуйте, Начинающий программист, Вы писали:
НП>Задача: написать алгоритм, определяющий, зависит ли стабилизированное состояние исходной вершины от порядка действий обкуренного ёжика, и если такой зависимости нет, вычисляющий стабилизированное состояние исходной вершины.
Если из исходной вершины достижимы две вершины с фруктами одинаковых типов, но разных свойств, то зависит. Иначе нет.
Здравствуйте, Vintik_69, Вы писали:
V_>Если из исходной вершины достижимы две вершины с фруктами одинаковых типов, но разных свойств, то зависит. Иначе нет.
Дополнение: "достижимы" означает "достижимы через вершины, в которых ящики данного типа пусты".
Нужно как-нибудь минимизировать хождения по графу. Хотелось бы вообще обойтись одним проходом. И еще мы не знаем наперед сколько там вообще видов фруктов. И еще есть большая вероятность, что алгоритм будет вызываться несколько раз с одним и тем же графом, но другой начальной вершиной... Спасибо за подсказку, пойду вспоминать дискретную математику.
Кажется очевидным, что ситуации с видами фруктов не зависят друг от друга (действительно: ёжик каждый раз оперирует с векторами, и нигде нет межкомпонентных зависимостей).
Поэтому можно свести задачу к такой (срез по одному фрукту):
— имеется орграф, каждая из вершин которого помечена как несущая цвет или бесцветная
— ёжик путешествует по графу во всех направлениях, причём "по ходу" он не переносит цвет, а "по противоходу" переносит из покрашенной в непокрашенную
Заметим, что единожды покрашенная вершина (изначально или на каком-то шаге) сохраняет свой цвет.
Если все вершины достижимы по ходу, то вопрос о единственности стабильного состояния сводится к следующему: есть ли пустая вершина, к которой в противоходе можно придти из двух разноцветных вершин через прозрачные. Это выясняется с помощью заливки.
— Берём покрашенную вершину и от неё заливаем все пустые (помечая их как вторичные).
— Берём следующую покрашенную — и тоже заливаем... и так далее.
— Как только мы в ходе заливки наталкиваемся на свежепокрашенную (т.е. вторичную) вершину — всё, стоп. Это значит, что варианты возможны (мы эту вершину можем покрасить тем или другим способом).
Заливать можно от каждой вершины по-отдельности, или же единым фронтом ото всех вершин сразу.
А вот если некоторые вершины достижимы только по противоходу... тут надо мало-мало подумать.
спасибо. Все вершины по ходу достижимы (условие). Единственная сложность, что нет явного представления графа -- находясь в какой либо вершине мы можем только получить список вершин, достижимых по ходу, и хочется как-нибудь избежать явного построения графа. Кроме того, все хочется сделать за один проход (но тут, как я понимаю, не имеет значения, оперировать с вектором цветов или со скаляром, тонкость только в том, что размерность вектора априори не задана -- ёжик укурен и не в состоянии сосчитать кол-во ящиков).
Здравствуйте, Начинающий программист, Вы писали:
НП>спасибо. Все вершины по ходу достижимы (условие). Единственная сложность, что нет явного представления графа -- находясь в какой либо вершине мы можем только получить список вершин, достижимых по ходу, и хочется как-нибудь избежать явного построения графа. Кроме того, все хочется сделать за один проход (но тут, как я понимаю, не имеет значения, оперировать с вектором цветов или со скаляром, тонкость только в том, что размерность вектора априори не задана -- ёжик укурен и не в состоянии сосчитать кол-во ящиков).
Можно ли узнать оригинальную задачу, а не её вольную метафору про укуренного ёжика?
Потому что — в принципе, можно выполнить два прохода: за первый полностью собрать информацию о графе и сделать удобное представление с прямым доступом, а также посчитать размерности. И уже вторым проходом — по нашей собственной структуре.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Начинающий программист, Вы писали:
К>Можно ли узнать оригинальную задачу, а не её вольную метафору про укуренного ёжика? К>Потому что — в принципе, можно выполнить два прохода: за первый полностью собрать информацию о графе и сделать удобное представление с прямым доступом, а также посчитать размерности. И уже вторым проходом — по нашей собственной структуре.
Это связано с множественным наследованием и атрибутами.
Правила такие: есть базовые сущности, их члены могут быть помечены атрибутами. В дочерних сущностях члены можно перегружать и добавлять новые атрибуты. Атрибуты могут наследоваться. При определении атрибута на члене дочерней сущности, в случае, если атрибут того же типа определен на базовой, он будет замещен. Из-за множественного наследования один и тот же член в дочерней сушности может соответствовать нескольким членам в базовой. Есть механизмы, позволяющие получить базовые сущности для данной. Есть механизмы, позволяющие получить список атрибутов (не унаследованных!) для данной сущности. Задача: получить полный список атрибутов, включая унаследованные.
Пример (атрибуты в скобках, тип атрибута — буква, значение — слово, наследование "<-"):
должны получить:
(A3 [перегружен], B1 [унаследован], C1 [новый])
определение
Base1 (A1, B1)
Base2 (A2)
Successor : Base1, Base2 (C1)
должны получить:
ошибка -- не возможно вычислить атрибут А
Про структуру графа пока ничего сказать не могу. Думаю, это будут DAG-и но не уверен, поэтому допустил наличие циклов.
Есть некоторая вероятность, что запрос на атрибуты будет не только к Successor, но и к Base, поэтому, если алгоритм подразумевает вычисление всех атрибутов на Base, этот результат имеет смыслс кешировать.
Здравствуйте, Начинающий программист, Вы писали:
НП>Это связано с множественным наследованием и атрибутами.
Ну это же другое дело. Сразу становится понятно. А то ёжик... обкурка...
НП>Правила такие: есть базовые сущности, их члены могут быть помечены атрибутами. В дочерних сущностях члены можно перегружать и добавлять новые атрибуты. Атрибуты могут наследоваться. При определении атрибута на члене дочерней сущности, в случае, если атрибут того же типа определен на базовой, он будет замещен. Из-за множественного наследования один и тот же член в дочерней сушности может соответствовать нескольким членам в базовой. Есть механизмы, позволяющие получить базовые сущности для данной. Есть механизмы, позволяющие получить список атрибутов (не унаследованных!) для данной сущности. Задача: получить полный список атрибутов, включая унаследованные.
Нужно ли получить список атрибутов (или хотя бы сообщение об ошибке) для произвольного объекта по запросу, или же для всех объектов сразу?
Для графа целиком можно выполнить топологическую сортировку и затем пробежаться по сортированной последовательности, запоминая атрибуты каждого объекта.
В случае запроса про один объект — можно рекурсивно оббежать его базы.
НП>Про структуру графа пока ничего сказать не могу. Думаю, это будут DAG-и но не уверен, поэтому допустил наличие циклов.
А что делать с циклическими графами? Каков их сермяжный смысл?
Мне кажется, проще диагностировать наличие циклов и сообщать об этом как об ошибке.
НП>Есть некоторая вероятность, что запрос на атрибуты будет не только к Successor, но и к Base, поэтому, если алгоритм подразумевает вычисление всех атрибутов на Base, этот результат имеет смыслс кешировать.
Как говорится, время-деньги. Если объектов немного (или глубина наследования невелика), то можно не кешировать, а перевычислять.
Но это зависит от объёма предметной области и требований по скорости и объёму памяти.
Перекуём баги на фичи!
