Сообщение Re: Breadth-First Search от 10.01.2017 6:39
Изменено 10.01.2017 6:41 Qbit86
Re: Breadth-First Search
Здравствуйте, Arsen.Shnurkov, Вы писали:
AS>И не только граф, но и алгоритм поиска в направленном графе
AS>подграфа с заданной раскраской (в частном случае не подграфа, а цепочки).
AS>Как нужный мне алгоритм называется и как его искать?
Тебе нужен обход в ширину (breadth-first traversal) в том варианте, который принимает несколько исхоных вершин. Перед началом ты перебираешь все вершины, и те, которые помечены так же, как начало пути-паттерна, складываешь в FIFO-очередь.
AS>граф с вершинами разных типов (видимо это называется "окрашенные вершины").
Скорее, «помеченные» («labeled») вершины. Дополнительно окрашены они будут в процессе обхода чтобы различать впервые встреченные (белые); те, для которых work in progress (серые) и они в очереди; и полностью рассмотренные (чёрные).
AS>Перебираем все вершины графа, для каждой смотрим — есть ли исходящий из этой вершины путь, полностью совпадающий с цепочкой.
Поиск в ширину займёт O(E + V), быстрее способа не вижу. От упомянутого наивного перебора BFS отличается тем, что не пойдёт по путям с общим постфиксом, потому что в процессе обхода вершины раскращиваются, и повторный заход можно задетектить — встретим не белую вершину.
AS>И не только граф, но и алгоритм поиска в направленном графе
AS>подграфа с заданной раскраской (в частном случае не подграфа, а цепочки).
AS>Как нужный мне алгоритм называется и как его искать?
Тебе нужен обход в ширину (breadth-first traversal) в том варианте, который принимает несколько исхоных вершин. Перед началом ты перебираешь все вершины, и те, которые помечены так же, как начало пути-паттерна, складываешь в FIFO-очередь.
AS>граф с вершинами разных типов (видимо это называется "окрашенные вершины").
Скорее, «помеченные» («labeled») вершины. Дополнительно окрашены они будут в процессе обхода чтобы различать впервые встреченные (белые); те, для которых work in progress (серые) и они в очереди; и полностью рассмотренные (чёрные).
AS>Перебираем все вершины графа, для каждой смотрим — есть ли исходящий из этой вершины путь, полностью совпадающий с цепочкой.
Поиск в ширину займёт O(E + V), быстрее способа не вижу. От упомянутого наивного перебора BFS отличается тем, что не пойдёт по путям с общим постфиксом, потому что в процессе обхода вершины раскращиваются, и повторный заход можно задетектить — встретим не белую вершину.
Re: Breadth-First Search
Здравствуйте, Arsen.Shnurkov, Вы писали:
AS>И не только граф, но и алгоритм поиска в направленном графе
AS>подграфа с заданной раскраской (в частном случае не подграфа, а цепочки).
AS>Как нужный мне алгоритм называется и как его искать?
Тебе нужен обход в ширину (breadth-first traversal) в том варианте, который принимает несколько исхоных вершин. Перед началом ты перебираешь все вершины, и те, которые помечены так же, как начало пути-паттерна, складываешь в FIFO-очередь. В процессе складываешь в очередь только те вершины, которые помечены так же, как очередная вершина на пути-паттерне (то есть на том же расстоянии от начала).
AS>граф с вершинами разных типов (видимо это называется "окрашенные вершины").
Скорее, «помеченные» («labeled») вершины. Дополнительно окрашены они будут в процессе обхода чтобы различать впервые встреченные (белые); те, для которых work in progress (серые) и они в очереди; и полностью рассмотренные (чёрные).
AS>Перебираем все вершины графа, для каждой смотрим — есть ли исходящий из этой вершины путь, полностью совпадающий с цепочкой.
Поиск в ширину займёт O(E + V), быстрее способа не вижу. От упомянутого наивного перебора BFS отличается тем, что не пойдёт по путям с общим постфиксом, потому что в процессе обхода вершины раскращиваются, и повторный заход можно задетектить — встретим не белую вершину.
AS>И не только граф, но и алгоритм поиска в направленном графе
AS>подграфа с заданной раскраской (в частном случае не подграфа, а цепочки).
AS>Как нужный мне алгоритм называется и как его искать?
Тебе нужен обход в ширину (breadth-first traversal) в том варианте, который принимает несколько исхоных вершин. Перед началом ты перебираешь все вершины, и те, которые помечены так же, как начало пути-паттерна, складываешь в FIFO-очередь. В процессе складываешь в очередь только те вершины, которые помечены так же, как очередная вершина на пути-паттерне (то есть на том же расстоянии от начала).
AS>граф с вершинами разных типов (видимо это называется "окрашенные вершины").
Скорее, «помеченные» («labeled») вершины. Дополнительно окрашены они будут в процессе обхода чтобы различать впервые встреченные (белые); те, для которых work in progress (серые) и они в очереди; и полностью рассмотренные (чёрные).
AS>Перебираем все вершины графа, для каждой смотрим — есть ли исходящий из этой вершины путь, полностью совпадающий с цепочкой.
Поиск в ширину займёт O(E + V), быстрее способа не вижу. От упомянутого наивного перебора BFS отличается тем, что не пойдёт по путям с общим постфиксом, потому что в процессе обхода вершины раскращиваются, и повторный заход можно задетектить — встретим не белую вершину.