Задан неориентированный граф. Найти количество путей проходящие через k вершин, начинающиеся и заканчивающиеся в одной и той же вершине, но не проходящие два раза через любую другую вершину.
Я пробовал написать поиск в глубину, но у меня находилось больше путей, т.к. у меня получилось что 1-2-3-4-1 и 1-4-3-2-1 — разные пути.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
Вероятно, каждый путь получился посчитан одинаковое количество раз (например, два раза или 2k раз). В этом случае можно просто поделить ответ на это число.
Да, спасибо.
Вот здесь задача и моё решение (писалось на PascalABC): http://pastebin.com/9XCpcqW9
1) Если запустить dfs не циклом из всех а один раз из первой то res = 6 (Ответ res/2)
2) Где в условие сказано что нужно искать пути из первой точки?
3) Верное ли решение? Есть ли более оптимальное?
Честно говоря, я не верю в это решение, мне кажется, поиск в глубину не найдет все циклы. Хотя могу и ошибаться. Есть 100% решение за O(n(n-1)(n-2)(n-3)...(n-k+1)*k)=O(k*n^k): перебрать все возможные множества из k вершин и проверить, являются ли они циклами. Тогда ответ надо будет поделить на 2*k, ибо каждый цикл будет посчитан именно столько раз. Но при n=300 и k=4 это будет очень много итераций, так что, думаю, есть и более простое решение :\
Логика решения такова — идём из вершины(или из всех вершин,что я и делал) по соседям(записав вершину,с которой начали), изменяя длину пути и записывая каждую вершину в сет, чтобы проверить не были ли мы на данной вершине. Как только длина достигает нужного значения — проверяем куда мы пришли.
Этот алгоритм переберёт (должен перебрать, т.к. я впервые написал алгоритм на графах) все пути, начинающиеся в вершине,из которой он был запущен.
p.s. Задача с муниципального этапа РОИ. Поэтому вопрос номер 2 (выше) всё же актуален.
Можно по идее сделать так: перебираем все пары вершин. Пересекаем их списки смежности. Считаем количество вершин в пересечении. К ответу прибавляем x * (x — 1) / 2. Итого: алгоритм за N^3. Будет быстрее если списки смежности хранить как битовую маску, тогда пересечение можно сделать за N / 32, а подсчет битов в числе за 2 операции. В конце ответ надо будет поделить на что-то еще, так как все циклы учтутся одинаковое количество раз.
А разве, если k = n, это не задача о гамильтоновом цикле? :)
Не совсем в явном виде, конечно. Но, если мы решим данную, мы узнаем, существует ли в графе гамильтонов цикл.
Burunduk1: Как следует действовать если k<>n ?
Я так и не понял, что у Вас не получается. DFS -- правильная идея. Gassa уже сказал, что, чтобы пути не учитывались несколько раз, нужно поделить на 2k.
Запускать DFS нужно, конечно, от всех вершин по очереди. DFS должен перед выходом из рекурсии снимать пометку с вершины.
P.S. Задача коротко формулируется так: кол-во простых циклов длины k в неориентированном графе.
UPD1: О! В ссылке оказывается другое условие задачи :-) Да, для 4-х все несколько проще. FOR FOR FOR FOR ? :-)
UPD2: Видимо, хорошим тоном было бы с самого начала дать ссылку на условие задача. Например, оказывается, N < 300.
O(n^4), при n=300 кол-во операций более 8,1*10^9 — такое решение должно пройти? Ссылки на задачу у меня самого не было. Условие изменил — хотел узнать решение для более общего случая.
Но у меня видимо проблема ещё и с пониманием задачи. У нас же есть пути (тест из условия): 1-2-3-4-1 1-4-3-2-1 1-4-2-3-1 3-2-1-4-3 и т.д.
А правильный ответ — 3. Что я неправильно понимаю?
1) Если аккуратно писать, там не N4, а N4 / 4. Так что может зайти :-)
2) ValenKof уже сказал, как сделать O(N3). Попробую объяснить подробнее. Цикл = A-B-C-D-A. Зафиксируем A и C. Пока N2. Теперь B и D -- любые две вершины, которые соединены и с A, и с C. Нужно найти кол-во таких вершин. Если у нас есть матрица смежности, нас интересует кол-во таких i: g[A,i] and g[C,i]. Теперь ок?
Выше был код тс с вбитым условием задачи. В условии K = 4. Я и рассказал решение для K = 4.
Извиняюсь, я как-то не догадался, что автор под ссылкой указал другое условие.
Wackloner, можешь подробнее объяснить, как для данных 4-ёх вершин за O(k) определить, что они образуют цикл?
Я могу ошибаться, но разве нельзя взять алгоритм отсюда и посчитать количество путей длиной k от i-той вершины до нее самой?
Т.е. нужно кол-во простых циклов (путей). По ссылке кол-во непростых циклов (путей).
Вроде как непростой цикл длины 4 через вершину v — это содержащий петли(которые можно нафиг выкинуть вначале) или состоящий из двух циклов длины 2, а это что-то около deg(v)^2
Насколько я понял, BekzhanKassenov имел в виду случай произвольного k.
Ну да. Только теперь прочитал что k == 4. Но ведь n^4 не проходит?
Думаю, можно по аналогии выкидывать повторения для всех разложений k=mp. Но это уже не полином, кажется.
какой-то хаотичный пост. каждый что-то отвечает но все подразумевают разные задачи, где-то похоже присутсвовал код с условием и ссылкой, но я не обнаружил его...
полагаю речь идет об этой задаче ссылку на которую я скопировал из сообщения выше от Burunduk1. Я думаю можно найти количество циклов(не обязательно простых) длины 4 каким-нибудь тупым способом, например умножением матрицы смежности нужное число раз. затем порисовать всевозможные непростые циклы, какие они вообще бывают. найти для каждой вершины какие и в каком количестве присутствуют. это можно сделать за O(n^3) т.к. в непростых циклах число различных вершин не более 3-х, а количество типов константное (вроде 2, но лень думать). Теперь вычитаем одно из другого, и получаем количество простых циклов.