Вот образовалась у меня задача, а как решить -- не знаю. Задача полностью из головы, поэтому никаких ссылок нет.
Есть невзвешенный ориентированный граф (мне нужен случай разреженного графа, количество ребер меньше 3*{количество вершин}, но это мало влияет на суть задачи), в графе могут быть циклы. Надо найти самый длинный путь из заданной вершины, который не проходит через одну и ту же вершину больше одного раза.
Я не могу придумать алгоритм, который работал бы за полиномиальное от количества вершин время. И что-то у меня возникли сомнения в его существовании (задача чем-то похожа на задачу о коммивояжере).
Буду благодарен, если кто-то расскажет такой алгоритм, либо подтвердит мои сомнения. Заранее спасибо.
UPD. Действительно, достаточно очевидно, что решение этой задачи равносильно нахождению гамильтонова пути в графе, что, как известно, является NP-полной задачей. Спасибо MikeMirzayanov и Edvard.
Так же большое спасибо goo.gl_SsAhv за предложенное решение. Хотя оно, как видно, и неправильное, но очень интересное и поучительное для меня. Из неправильных решений иногда можно подчерпнуть не меньше, чем из правильных
Ошибочка вышла, прошу прощения, бред написал.
Простой DFS найдет какие-то пути до всех достижимых вершин. Нет никаких оснований считать, что среди этих путей точно найдется требуемый самый длинный.
Граф невзвешенный? т.е. цена всех рёбер еденица, да?
Да. Обновил условие.
А хотя, это не важно. Я нашёл решение и для взвешенного графа. Раздвоим каждую вершину i на две (i * 2, i * 2 + 1), , если было ребро i -> j, стоимостью w, добавим в граф ребро (i * 2 + 1, j * 2, -w). Ребра (i * 2, i * 2 + 1) имеют пропускную способность 1 и стоимость 0, из истока ребро в start * 2 + 1, из i * 2 + 1 рёбра в сток. Найдём поток минимальной стоимости.
Уточняющий вопрос для проверки понимания. Разве ребро из истока не должно идти в start * 2? Мне кажется, что если оно идет в start * 2 + 1, то появляется возможность пройти через start второй раз, что не соответствует постановке задачи.
да, ты прав
чё-то я гоню, ибо мне кажется я решил задачу коммивояжера с подачи MikeMirzayanov: назначим на на рёбра i * 2 -> i * 2 + 1 стоимость -1e30, на остальные рёбра w, будем в самом начале перебирать ребро (x, y), которым путешествие завершится, и исключать его из графа, исток в x * 2, из y * 2 + 1 в сток. Покажите где ошибка?
А, понятно в чем ошибка. Суть в том, что макс поток ищет и нулевые потоки, т.е. если в сети существует отрицательный цикл, то МинКостФлоу пустит по нему поток кругом, не добавив при этом величины к потоку от s к t. Это мешает нам сделать рёбра между раздвоенными вершинами отрицательными. И стоит пересмотреть предложенное мною решение исходной задачи, возможно оно также ошибочно.
Да, решение ошибочное, см. ниже.
Минусующим: я пытаюсь рассуждать, привел идею, потом показал в чем она ошибочна. Да я ошибаюсь, как и мы все, но я пытался помочь с решением, не понимаю вашей ненависти.
Как мне видится, если в построенном таким образом графе найти поток минимальной стоимости, то это решит задачу. Но можно ли его быстро найти? Я совсем не силен в потоках, но первая проблема, которая мне бросается в глаза -- наличие в графе с ценами циклов отрицательного веса. Как в этом случае быстро находить поток? Мне кажется, что при этом мы вернемся к тому, с чего начинали.
Поток минимальной стоимости в графе с отрицательными ценами и циклами строится беллманом фордом. Если есть просто цикл даже не связанный с истоком и стоком (граф несвязный), то мы должны будем пустить по этому циклу поток, чтобы уменьшить стоимость. Отсюда мы видим, найти путь минимальной стоимости в этом графе, и найти единичный поток минимальной стоимости это разные задачи. Вторая решается эффективно беллманом фордом, первая не имеет быстрого решения, иначе мы могли бы решать задачу Коммивояжера как я описал.
Контрпример. Граф c ребрами: 1 2 1 3 3 2
Безусловно, она не решается за полином, если граф взвешенный
Не могли бы Вы пояснить, почему она не решается за полином? Для меня это не так очевидно.
конечно неочевидно, ибо я привел решение.
Upd: я ошибся
Думаю, что как и MikeMirzayanov. Минусовать то за что?
Может быть потому, что если человек задает вопрос, то ему, вероятно, не очевидно.
А если Вам очевидно, то вполне можно было и рассказать.
Разве это не эквивалентно проверке графа на гамильтоновость, что NP-полная задача?
+1. Если решить эту задачу за полином, то перебором стартовой вершины за O(n) можно не просто проверить граф на гамильтоновость, но и найти гамильтонов путь если он существует.
Зачем же такое говорить? Может, в этом обсуждении бы случайно решили проблему Кука :)
К сожалению уже прошли те времена, когда можно было случайно доказать какую-нибудь задачу столетия/тысячелетия.