Нахождение минимальной траектории цикла в динамически ориентированном графе
Я недавно сталкивалсяэто (Правка: проблема А) Интересная проблема от хакерской задачи Spotify в начале этого года, которая включает в себя определение переключения на развязках железнодорожных грузовиков, чтобы направить поезд обратно в исходную точку. Поезд должен прибыть в том же направлении, в котором вышел, и поезд никогда не сможет повернуть на рельсы.
Насколько я понимаю, проблему можно смоделировать как неориентированный (?) Граф, где мы должны найти кратчайший цикл из определенной вершины или обнаружить, что такого цикла не существует. Однако интересная часть состоит в том, что для вершины v вершины, смежные с v, зависят от пути, взятого к v, поэтому в некотором смысле граф можно считать направленным, хотя это направление зависит от пути.
Моей первой мыслью было смоделировать каждый узел как 3 отдельные вершины, A, B и C, где A <-> B и A <-> C, а затем использовать поиск в ширину, чтобы построить дерево поиска, пока мы не найдем исходный вершины, но это усложняется оговоркой выше, а именно, что смежность для данной вершины зависит от предыдущей вершины, которую мы посетили. Это означает, что в нашем дереве BFS узлы могут иметь несколько родителей.
Очевидно, что простой поиск BFS не будет достаточным для решения этой проблемы. Я знаю, что существуют алгоритмы для обнаружения циклов в графе. Один из подходов может состоять в том, чтобы обнаружить все циклы, а затем для каждого цикла определить, является ли путь действительным. (т.е. не меняет направление)
Есть ли у кого-нибудь еще идеи о подходах к решению этой проблемы?
ОБНОВИТЬ: Я следовал подходу, предложенному @Karussell в комментариях.
Хитрость заключалась в том, чтобы смоделировать ситуацию с использованием графа на основе ребер, а не традиционного графа на основе вершин. Входной файл, представленный в конкурсе, уже удобно указывать в терминах ребер, поэтому этот файл можно легко использовать для построения графа на основе ребер.
В программе используются два важных класса: Road и Solver. Дорога имеет два целых поля, j1 и j2. j1 представляет исходное соединение, а j2 представляет целевое соединение. Каждая дорога односторонняя, то есть вы можете путешествовать только от j1 до j2. Каждая дорога также включает в себя LinkedList соседних дорог и родительскую дорогу. Класс Road также включает статические методы для преобразования между строками, используемыми во входном файле, и целочисленными индексами, представляющими точки A, B и C на каждом перекрестке.
Для каждой записи во входном файле мы добавляем две дороги в HashMap, по одной дороге для каждого направления между двумя соединениями. Теперь у нас есть список всех дорог, которые проходят между перекрестками. Нам просто нужно соединить дороги вместе на развязках через переключатели A, B и C. Если дорога заканчивается в Junction.A, мы ищем дороги, которые начинаются в Junction.B и Junction.C, и добавляем эти дороги в качестве смежных. Функция buildGraph () возвращает дорогу, целевое соединение (j2) которой равно «1A» == index 0.
На данный момент наш граф построен. Чтобы найти кратчайший путь, я просто использовал BFS для обхода графа. Мы оставляем корень без опознавательных знаков и начинаем с очереди смежности с корнем. Если мы найдем дорогу с целевым перекрестком «1А» (индекс 0), то мы нашли кратчайший цикл через начальную точку. Как только мы реконструируем путь, используя родительское свойство каждой Дороги, тривиально установить соответствующие переключатели в соответствии с требованиями задачи.
Спасибо Karussell за предложенный подход. Если вы хотите оставить свой комментарий в форме ответа с кратким объяснением, я приму его. Благодаря @Origin, а также. Я должен признать, что я не полностью следовал логике вашего ответа, но это, конечно, не означает, что это не правильно. Если кто-нибудь решит эту проблему, используя ваше решение, мне было бы очень интересно увидеть его.