Алгоритм: минимальный путь чередования цветов

Question

Пусть G - ориентированный взвешенный граф с узлами, окрашенными в черный или белый цвет, и все веса неотрицательны.Никакая другая информация не указана - нет начальной или конечной вершины.

Мне нужно найти путь (не обязательно простой) минимального веса, который чередует цвета не менее n раз.Моя первая мысль - запустить алгоритм Kosaraju, чтобы получить граф компонентов, а затем найти минимальный путь между компонентами.Затем вы можете выбрать узлы с градусами, равными нулю, поскольку у них будет как минимум столько же чередований цветов, сколько у путей, начинающихся с компонентов с положительным градусом.Однако это также означает, что у вас может быть неоправданно длинный путь.

Я думал о том, что, возможно, пытался каким-то образом изменить график, возможно, создавая копии графика, на которые указывают чёрные или белые ребра, или копируя или удаляя ребра, ноничто из того, что я мозговой штурм, кажется, не работает.

Answer 1

В комментариях упоминается использование алгоритма Дейкстры, и на самом деле есть способ сделать эту работу.Если мы создадим новую «корневую» вершину в графе и соединим каждую другую вершину с ней направленным ребром, мы сможем запустить модифицированный алгоритм Дейкстры от корня наружу, который завершится, когда инверсии данного пути превысят n.Важно отметить, что мы должны разрешить повторное посещение каждой вершины в реализации, поэтому ключ каждой вершины в нашей приоритетной очереди будет не просто node_id, а кортежем (node_id, inversion_count), представляющим эту вершину на i th.визит.При этом мы неявно делаем n копий каждой вершины, по одной на каждое потенциальное посещение.Визуально мы фактически создаем n копий нашего графа и переводим ребра между каждой парой (black_vertex, white_vertex), чтобы соединиться между i и i+1 графами инверсий.Мы запускаем алгоритм, пока не достигнем пути с инверсиями n.В качестве альтернативы, мы можем соединить каждую вершину на n-м графе инверсии с «вершиной» вершины и запустить любой обычный алгоритм поиска пути на этом графе без изменений.Это будет выполнено в O(n(E + Vlog(nV))) время.Вы могли бы довольно сильно оптимизировать это, а также рассмотреть возможность использования A * вместо эвристического smallest_inversion_weight * (n - inversion_count).

Кроме того, меня поразила другая идея об использовании знания требования инверсии для ускорения поиска, но яне смог найти способ реализовать его без превышения O(V^2) времени.Идея состоит в том, что вы можете использовать цепочку сложений (например, двоичное возведение в степень), чтобы разложить кратчайший путь n -инверсии на два меньших пути, а также промыть и повторить в режиме «разделяй и властвуй».Проблема в том, что вам нужно будет построить таблицы для кратчайшего пути i -инверсии из любых двух вершин, который будет O(V^2) записей на i и O(V^2logn) в целом.Чтобы построить каждую таблицу, для каждой записи в предыдущей таблице вам нужно добавить V других путей, так что общее время будет O(V^3logn).Может быть, кто-то еще найдет способ объединить эти две идеи в O((logn)(E + Vlog(Vlogn))) алгоритм времени или что-то в этом роде.