Поиск «положительного цикла»

Question

Предположим, что E - это матрица nxn, где E [i, j] представляет собой обменный курс из валюты i в валюту j. (Сколько валюты j можно получить с 1 валютой i). (Замечание: E [i, j] * E [j, i] не обязательно 1).

Придумайте алгоритм для поиска положительного цикла, если он существует, где положительный цикл определяется: если вы начинаете с 1 валюты i, вы можете продолжать обмен валюты, чтобы в конечном итоге вы могли вернуться и иметь больше чем 1 валюты i.

---

Я долгое время думал об этой проблеме, но я не могу ее получить. Единственное, что я могу придумать, это представить все как ориентированный граф с матрицей E в качестве матрицы смежности, где log (E [i, j]) - вес между вершинами i и j. И тогда вы будете искать цикл с отрицательным путем или что-то в этом роде. Это даже имеет смысл? Есть ли более эффективный/более простой способ подумать об этой проблеме?

Answer 1

Прежде всего, возьмите журналы обменных курсов (это не обязательно, но это означает, что мы можем говорить о «добавлении длин», как обычно). Затем вы можете применить небольшую модификацию Floyd-Warshall algorithm, чтобы найти длину , возможно, непростого пути (т. Е. Путь, который может зацикливаться на себе несколько раз и в разных местах) между каждой парой вершин, которая не менее до тех пор, пока самый длинный простой путь между ними. Единственное изменение, которое необходимо изменить, - это перевернуть знак сравнения, так что мы всегда ищем самый длинный путь (подробнее см. Ниже). Наконец, вы можете просмотреть все пары O (n^2) вершин u и v, взяв сумму длин двух путей в каждом направлении (от u до v и от v до u). Если какое-либо из них> 0, то вы нашли (возможно, не простой) цикл с общим обменным курсом> 1. В целом часть FW алгоритма доминирует, делая это O (n^3) -time.

В общем, проблема с попыткой использовать такой алгоритм, как FW, найти максимум -weight paths состоит в том, что он может объединить 2 подпапки, разделяющие одну или несколько вершин, и мы обычно этого не хотим. (Этого не может быть, если вы ищете минимум - пути длины в графе без отрицательных циклов, так как такой путь обязательно должен содержать положительный вес, который может быть удален, поэтому он никогда не будет выбран как оптимальный.) Это было бы проблемой, если бы мы искали максимум - простой простой цикл; в этом случае, чтобы обойти это, нам нужно будет рассмотреть отдельную подзадачу для каждого подмножества вершин, что подталкивает сложность времени и пространства до O (2^n). К счастью, однако, мы имеем дело только с поиском некоторого положительного веса, и достаточно легко увидеть, что если путь, найденный FW, использует несколько вершин более одного раза, тогда он должен содержать цикл неотрицательного веса - - который может быть удален (если он имеет вес 0), или (если он имеет вес> 0) сам по себе является «правильным ответом»!

Если вы хотите найти простой цикл, это легко сделать на последнем этапе, который является линейным по длине пути, сообщенного FW (что, кстати, может быть O (2^| V |) - если все пути имеют положительную длину, тогда все «оптимальные» длины удваиваются с каждой внешней итерацией, но это вряд ли произойдет здесь). Возьмите пару оптимальных путей, подразумеваемую результатом FW (каждый путь может быть вычислен обычным способом, сохраняя таблицу «оптимальных предшественников» значений k для каждой пары вершин (i, j)) и просто ходить по ней , присваивая каждой вершине, которую вы посещаете в настоящее время, пока вы не достигнете вершины, которую вы уже посетили.На этом этапе либо currentTotal - totalAtAlreadyVisitedVertex > 0, и в этом случае цикл, который вы только что нашли, имеет положительный вес, и вы закончили, или это различие равно 0, и в этом случае вы можете удалить ребра, соответствующие этому циклу, из пути и продолжить, как обычно.