Я пытаюсь написать максимальный алгоритм сопоставления графиков для моей диссертации. Я застрял на том, как сохранить путь дополнения на шаге алгоритма. Сначала я напишу реальную проблему, которую пытаюсь решить. Тогда я постараюсь упростить это.
Предположим, у вас есть график, где узел может быть сопоставлен с одним из его соседей, а вы пытаетесь вычислить максимальное совпадение. Каждый узел связан ровно с тремя другими узлами. Вы сделали все возможное, но некоторые узлы остались непревзойденными, поэтому вам нужно сделать дополнения. На данный момент вы уже знаете совпадения и список узлов, которые остаются несопоставленными. Процесс дополнения работает следующим образом: Вы выбираете два узла из списка несопоставленных узлов и находите альтернативный путь между ними. альтернативный путь состоит из двух упомянутых узлов и списка соответствующих узлов между ними. Он называется чередующимся путем, потому что совпадающие и несопоставленные ребра между узлами чередуются вдоль пути.
Вы можете найти альтернативный путь между любыми двумя несопоставленными узлами, но выбор более близких лучше для производительности алгоритма. Поэтому вместо этого вы выбираете несопоставленный узел и выполняете BFS , пока не достигнете другого несопоставленного узла. Когда вы найдете один такой путь (который удовлетворяет правилу чередующегося пути), вы поменяете местами совпадения, чтобы теперь были сопоставлены несопоставленные узлы.
Короче говоря, мне нужно запустить какой-то алгоритм BFS, в котором есть два типа ребер (скажем, красного и черного), и эти ребра будут чередоваться по пути, пока я не достигну своего пункта назначения. В конце мне нужен путь от моего источника до ближайшего из возможных пунктов назначения, которые удовлетворяют правилу красного / черного.
Мне удалось придумать псевдокод алгоритма, но я не знаю, как сохранить альтернативный путь, который находит алгоритм. Как это можно сделать? Любые альтернативные стратегии также приветствуются.