Пусть задан направленный граф вида (может иметь очень большой размер):
С вершинами 3 типов:
+ — Nor
* — Nand
! – Not
Таблицы истинности:
a | b |a+b|a*b| !a|
--------------------
0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 1 | 0 | 0 | 0 |
На каждом ребре в определенный момент времени содержится значение 0 или 1.
Инициализирующее значение подается на входы (обозначенные треугольником).
Каждое ребро имеет имя — имя вершины графа из которого оно выходит.
Пусть на этом графе задан путь и тип переключения каждого ребра пути.(Рисунок 2)
Переключение может быть либо из 0 в 1 либо из 1 в 0. Причем из за типов
элементов каждое переключение пути имеет разное направление. Также для каждого
ребра пути (жертва) задан набор ребер с некоторым весом от 0 до 100 (агрессоры),
которые переключаются в противоположном жертве направлении.
Списки агрессоров у всех жертв пути могут иметь общие элементы с разными
или одинаковыми весами.
--------------------------------------------------------------------------------------------------
n1 (1->0) : n11(86), n9(91) – сумма (177)
n6 (0->1): n1(24), n3(21), n2(27) – сумма (72)
n9 (1->0): n7(89), n5(96), n11(67), n6(76), n1(34), n12(40), n4(19) – сумма (421)
n12(0->1): n11(72), n6(17), n7(28), n3(25), n8(28), n10(93), n5(94), n4(84) — сумма (441)
Полный начальный вес пути равен: 1111
где n1(1->0) – жертва n1 переключающаяся из 1 в 0
n11(86) – агрессор воздействующий на ребро n1 с весом 86
Пример 1
--------------------------------------------------------------------------------------------------
Если все заданные агрессоры для данной жертвы переключатся в противоположном
ей направлении, то суммарный вес воздействия на жертву составит сумму весов
каждого из агрессоров.
Суть задачи
раздельного анализа состоит в нахождении максимального
возможного
веса суммарного воздействия агрессоров на одну жертву. Но для большинства случаев
все агрессоры не могут переключиться одновременно, в силу определенной структуры графа.
Например для графа на рисунке 1 не существует такой последовательности входных
сигналов что бы n1 – переключался из 0 в 1, а n11 при этом переключился из 1 в 0.
Следовательно для вершины n1 из примера 1. Максимальный вес будет равен не n11(86)+n9(91)=177,
а n9(91) = 91.
--------------------------------------------------------------------------------------------------
Результаты раздельного расчета жертв для примера 1:
n1(1->0): n1(91) – сумма (91)
n6(0->1): n1(24), n3(21), n2(27) – сумма (72)
n9(1->0): n7(89), n5(96), n6(76), n12(40) – сумма (301)
n12(0->1): n3(25), n8(28), n4(84) — сумма (137)
Полный вес для раздельного анализа пути: 601
--------------------------------------------------------------------------------------------------
В случае заданного пути общий вес ищется как сумма всех возможных агрессоров на
каждую из жертв пути. Очевидно, что общий анализ пути всегда дает результат либо равный,
а в большинстве случаев гораздо лучший, чем раздельный анализ. К тому же в
некоторых случаях путь может и вовсе не существовать. (тоже интересная задача
алгоритм проверки существования пути)
--------------------------------------------------------------------------------------------------
Результаты общего анализа пути для примера 1:
n1 = 0
n6 = n1, n2, n3 – сумма 72
n9 = n5, n7, n6, n12 – сумма 301
n12 = n3, n4, n8 – сумма 137
Общий вес для общего анализа пути: 510
Максимум достигается при переключении входов таким образом:
n1(1->0) n2(1->0) n3(1->0) n4(1->0) n5(0->1)
--------------------------------------------------------------------------------------------------
Данный пример решался методом полного перебора, что не является приемлемым решением для
больших графов (графов с большим числом входов). Поэтому ставится задача придумать решение
наиболее оптимальное по отношению эффективность – время. Прежде всего, интересуют любые
мысли по поводу полного анализа пути, но также интересуют побочные задачи такие как:
Способы определить существует ли путь или нет и раздельный анализ жертв.
