Решение задачи оптимизации в направленном графе

Сегодня расскажу о решении задачи №1857 с литкода, которая называется как «Largest Color Value in a Directed Graph».

Суть задачи: дан направленный граф, при этом каждый узел имеет еще один параметр — его в задаче называют цвет. Спектр цветов ограничен, т.к. разные цвета обозначены в задаче разными латинскими буквами, т.е. максимальная палитра составляет всего 26 «цветов».

Требуется найти путь по графу, который собирает максимальное число узлов одного цвета. Дополнительно говорится, что если в графе есть петля, то нужно вернуть -1.

Подготовительные операции

Весь код далее написан на TS (typescript).

На входе мы получаем строку colors, которая задаёт цвет colors[i] для узла i. А также «ребра» направленного графа, массив элементов [j, k], который описывает переходы из узла j в узел k

Почти всегда, когда граф задан подобным образом, приходится подготавливать данные, группируя информацию о переходах.

Это делается для того, чтобы не сканировать весь массива edges каждый раз, когда нам нужно будет установить куда можно перейти из текущего узла. Длина массива colors помогает определить число узлов.

Обход графа

Начальная идея очень проста — давайте начнем обход с узлов, у которых нет входящих переходов. Если таких узлов не обнаружится, то в графе имеются петли, мы вернем -1.

Процедура «обхода» будет использовать стек, который хранит историю пути и его статус. У нас получается такая структура:

Для каждого узла со стека мы будет смотреть, куда нам можно из него перейти, и выполнять переход, обновляя статус.

Если перейти можно в узел, который уже есть в пути, то вернем -1 (петля).

Посмотрим реализацию идеи:

Алгоритм работает, но довольно медленно для сложно разветвленных графов, т.к. то и дело проходит через одни и те же узлы. Фактически, это типичное слабое место рекурсивных алгоритмов.

Любое разветвление заставит алгоритм пройти дважды оставшийся путь: — 0->1->2->3 или 0->1->4->2->3. Соответственно, если у нас есть 3 или более вариантов выхода из узла, то это служит как бы множителем числа вариантов обхода.

Топологическая сортировка

Чтобы не обходить узлы многократно, используем прием, который фактически является своего рода сортировкой узлов графа.

Мы уже начали прошлый алгоритм с того, что выделили узлы, в которые нет переходов из других узлов. А что если каждый раз искать подобные узлы, удаляя уже «отработанные переходы»?

На рисунке расписано 4 итерации такого «обхода».

Над каждым узлом подписано число входящих переходов. Такой обход как бы «съедает» граф, удаляя отработанные узлы.

Отбор путей

Какую информацию нам нужно накапливать о состоянии обхода при переходе в очередной узел? Ответ на этот вопрос — основная сложность задачи.

Когда мы переходим в узел из пары других, то у нас как бы получается коллекция из двух состояний. Например, один родитель даёт цепочке цвет «a», а другой цвет «b». И далее цепочки должны это как то учитывать. Но нужно ли нам в данной задаче собирать коллекцию?

Т.к. речь идет о максимальном количестве узлов цвета в одном из путей, то достаточно собирать максимумы цветов.

Сбор коллекции состояний тоже будет работать, но гораздо медленнее и с большими затратами оперативной памяти.

Рассмотрим реализацию алгоритма.

Написать комментарий

Мало букафф? Читайте есчо !

Задача о подсчете количества путей в словаре

Апрель 16, 2023 г.

Разбираем задачу № 1639 Number of Ways to Form a Target String Given a Dictionary c leetcode.com. Дан словарь, где слова имеют одинаковую длину - words. Также дано дополнительно слово - target, которое нужно составить из словарных слов по следующим правилам: ...

Читать

Игра в камни

Май 27, 2023 г.

Серия задач StoneGame на leetcode - образец игры, где требуется просчитать оптимальную стратегию. Выигрыш/проигрыш начинающего партию предопределен, и второй участник лишь может надеяться на ошибку первого. Но это не наш случай, т.к. по условию ...

Читать

 

Комментарии к «Решение задачи оптимизации в направленном графе»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: