На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Максимальный цикл в графе
    Подскажите пожалуйста алгоритм решения задачи: дан неориентированный граф, нужно найти максимальный цикл в графе.
      Какая сложность? Можно back tracking'ом. Больше пока ничего на ум не приходит.
        Совершенно очевидно, что это NP-complete задача, ибо если бы за полиномиальное время можно было бы найти максимальный простой цикл, то мы бы автоматически решили бы и TSP (задачу коммивояжера). Просто путем проверки, гамильтонов ли цикл.
        Так что про точный алгоритм можно забыть (если конечно P != NP). Лучшее что придумало человечество на сегодняшний день - H.N. Gabow. Finding Paths and Cycles of Superpolylogarithmic Length, In Proceedings of the 36th ACM Symposium on the Theory of Computing (STOC), 2004, 407-416
        Но и там циклы далеки от максимальных. Правда время полиномиально
          Расшифровывая сказанное выше: перебор, перебор и только полный перебор всех циклов. Приведенная ссылка позволяет оптимизировать перебор, но ценой того, что находятся не самые длинные циклы, а просто "немного длинные"
            Цитата shadeofgray @
            Расшифровывая сказанное выше: перебор, перебор и только полный перебор всех циклов. Приведенная ссылка позволяет оптимизировать перебор, но ценой того, что находятся не самые длинные циклы, а просто "немного длинные"

            Ага, именно так, спасибо :) Я извиняюсь, у меня иногда возникают сложности с объяснением на русском того, что я на русском никогда не изучал...
              Цитата kl @
              Просто путем проверки, гамильтонов ли цикл.

              А при чём здесь гамильтонов цикл? Гамильтонов цикл - это цикл, который проходит через все вершины графа, но не обязательно, что этот цикл максимальный.
                Цитата vek21 @
                А при чём здесь гамильтонов цикл? Гамильтонов цикл - это цикл, который проходит через все вершины графа, но не обязательно, что этот цикл максимальный.

                Скажем, так:
                сделаем следующее преобразование графа:
                Пусть M --- максимальное ребро. Для каждого ребра (u,v) преобразуем его вес w следующим образом: w'=M-w. Для полученного графа найдем максимальный цикл. Этот же цикл будет являться решением задачи коммивояжера для исходного графа.
                Цитата vek21 @
                Подскажите пожалуйста алгоритм решения задачи: дан неориентированный граф, нужно найти максимальный цикл в графе.

                Если граф эйлеров, то максимальным циклом, не проходящим по ребру дважды в одном направлении, будет эйлеров цикл.
                  Цитата mo3r @
                  Гамильтонов цикл - это цикл, который проходит через все вершины графа, но не обязательно, что этот цикл максимальный.

                  Я, конечно, не спорю, что гамильтонов цикл здесь не при чем, но есть небольшая поправка - гамильтонов цикл всегда минимален для данного графа.
                    Цитата Arsuit @
                    Я, конечно, не спорю, что гамильтонов цикл здесь не при чем, но есть небольшая поправка - гамильтонов цикл всегда минимален для данного графа.

                    Гамильтонов цикл здесь очень даже причем. mo3r достаточно ясно показал, то о чем я говорил в первом посте, а именно, как задача нахождения гамильтонова цикла сводится к исходной задаче. Сводится по Куку. Отсюда автоматически следует, что либо вам удается показать, что P = NP, либо вы не сможете решить свою задачу точно и за приемлемое время. Вот и все.
                    Любую другую NP-полную задачу тоже можно свести к максимальному циклу. Например поиск максимальной клики в графе, satisfiability, задачу о сумме подпоследовательности и еще пару сотен задач. Но для гамильтонова цикла это показывается наиболее легко.
                      Цитата Arsuit @
                      гамильтонов цикл всегда минимален для данного графа.

                      Это почему?
                        по опредилению вроде.
                          Цитата Arsuit @
                          по опредилению вроде.

                          Прочитай определение еще разок.
                            Цитата kl @
                            Совершенно очевидно, что это NP-complete задача,

                            Судя по вашим словам, совершенно очевидно, что задача NP=HARD.

                            Добавлено
                            так на вскидку, я бы сказал что задача скорей всего из класса Р-Space
                              Да, я согласен, что термин NP-complete тут надо употреблять аккуратнее, потому что он строго определен только для decision problems (а TSP в классической формулировке таковой не является). Тем не менее ее можно перевести в класс decision problems. Но мне не хотелось вдаваться в эти детали, я просто имел в виду, что задача поиска максимального цикла - как минимум так же сложна как и TSP. И наоборот.
                                Вот мне надо как-то было найти минимальный цикл в графе. Была у меня идея пробежаться по всем вершинам и для каждой вершины найти кратчайший путь из нее в нее же. Только вот я не знаю, как это сделать :(
                                Может, здесь тоже можно так попробовать, только искать длиннейший путь?
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0338 ]   [ 15 queries used ]   [ Generated: 23.06.24, 14:06 GMT ]