Здравствуйте, _DAle_, Вы писали:
_DA>Она же вроде только в случае неориентированного графа сводится к паросочетанию минимальной стоимости. Тут ошибаются?
Нет не ошибаются. Действительно, направленный вариант дает обычный поток, а ненаправленный -- кососимметрический (который можно дальше трактовать в терминах недвудольных взвешенных паросочетаний).
Может тебе кажется, что ненаправленная задача сводится к направленной?
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, _DAle_, Вы писали:
_DA>>Она же вроде только в случае неориентированного графа сводится к паросочетанию минимальной стоимости. Тут ошибаются?
Mab>Нет не ошибаются. Действительно, направленный вариант дает обычный поток, а ненаправленный -- кососимметрический (который можно дальше трактовать в терминах недвудольных взвешенных паросочетаний).
Mab>Может тебе кажется, что ненаправленная задача сводится к направленной?
Здравствуйте, _DAle_, Вы писали:
_DA>Что-то я потерял нить разговора Я говорил про это: "Finding an optimal solution in a graph with both directed and undirected edges is NP-complete. " и спрашивал, ошибаются ли они. Может я не так трактую термин топикстартера "направленный граф", я под этим понимаю ориентированный граф, в котором как раз могут быть "both directed and undirected edges".
В моем понимании "направленный" и "ориентированный" -- это синонимы. А mixed -- это смешанный.
_DA>Да, если у нас для любых i, j не может быть обеих дуг (i,j) и (j,i), то задача решается потоком.
Да пусть даже и есть встречные дуги, чем это плохо?
Здравствуйте, Mab, Вы писали:
_DA>>Да, если у нас для любых i, j не может быть обеих дуг (i,j) и (j,i), то задача решается потоком. Mab>Да пусть даже и есть встречные дуги, чем это плохо?
Да вроде бы на первый взгляд ничем. Просто я не понимаю, почему по приведенным ссылкам написано про NP-полноту, вот и задаю в очередной раз тот же вопрос: "Они ошибаются?".
Здравствуйте, _DAle_, Вы писали:
_DA>Просто я не понимаю, почему по приведенным ссылкам написано про NP-полноту, вот и задаю в очередной раз тот же вопрос: "Они ошибаются?".
Раз написано, то наверное задача действительно NP-трудна. В чем противоречие?
Здравствуйте, _DAle_, Вы писали:
_DA>Понятно. Я просто неправильно понял смысл "both directed and undirected edges", почему-то решил, что это просто ориентированный граф имеется ввиду.
Нет, там все хитрее. На части ребер есть направление (их нужно проходить в указанную сторону), а на части нет (их можно проходить в любую).
"Definition: Find a minimum length closed walk that traverses each edge at least once. Finding an optimal solution in a graph with both directed and undirected edges is NP-complete. "
направленный граф и ориентированный граф это одно и то же. ориентированный и неориентированный графы являются частными случаями смешанного. силлогизм: для смешанного графа — Chinese postman problem NP-hard, следовательно для ориентированного(направленного), частного случая смешанного, Chinese postman problem так же NP-hard.
"In the first half of the talk I will discuss several algorithmic results affecting whole genome assembly -- the problem of assembling a genome from short pieces (called reads). This problem is often reduced to various path problems on graphs. We will first show that the problem of finding the Shortest Chinese Superwalk on a de Bruijn graph is NP-complete/hard, hence demonstrating the computational equivalence of two methods for sequenceassembly: the String Graph approach of Myers et al and the Eulerian Superpath approach of Pevzner et al. We will also demonstrate a simple polynomial time algorithm separating complimentary paths on a graph, which is...
"
de Bruijn graph — ориентированный(направленный), по нему Chinese postman problem (Shortest Chinese Superwalk) это NP-hard.
Здравствуйте, True2008, Вы писали:
T>кстати, не знаете, где найти статью "Кибернетический сборник, новая серия, вып.6 М., Мир, 1969, С.33-40." ?
Может в ленинке есть. А вообще не знаю.
T>http://www.nist.gov/dads/HTML/chinesePostman.html
T>"Definition: Find a minimum length closed walk that traverses each edge at least once. Finding an optimal solution in a graph with both directed and undirected edges is NP-complete. "
Здесь написано, что задача для mixed graph является NP-hard.
T>для смешанного графа — Chinese postman problem NP-hard, следовательно для ориентированного(направленного), частного случая смешанного, Chinese postman problem так же NP-hard.
Да ну? Если задача NP-hard, то ее частный случай тоже NP-hard? Это неправда.
T>http://www.youtube.com/watch?v=-m7PFnSvmJM
T>"In the first half of the talk I will discuss several algorithmic results affecting whole genome assembly -- the problem of assembling a genome from short pieces (called reads). This problem is often reduced to various path problems on graphs. We will first show that the problem of finding the Shortest Chinese Superwalk on a de Bruijn graph is NP-complete/hard, hence demonstrating the computational equivalence of two methods for sequenceassembly: the String Graph approach of Myers et al and the Eulerian Superpath approach of Pevzner et al. We will also demonstrate a simple polynomial time algorithm separating complimentary paths on a graph, which is... T>" T>de Bruijn graph — ориентированный(направленный), по нему Chinese postman problem (Shortest Chinese Superwalk) это NP-hard.
А это вообще к делу не относится. Скорее всего здесь речь про какую-то вариацию shortest common superstring.
В общем, у Вас какая-то путаница со сложностными классами, сведениями задач итд.
Здравствуйте, Mab, Вы писали:
T>>http://www.nist.gov/dads/HTML/chinesePostman.html
T>>"Definition: Find a minimum length closed walk that traverses each edge at least once. Finding an optimal solution in a graph with both directed and undirected edges is NP-complete. " Mab>Здесь написано, что задача для mixed graph является NP-hard.
T>>для смешанного графа — Chinese postman problem NP-hard, следовательно для ориентированного(направленного), частного случая смешанного, Chinese postman problem так же NP-hard. Mab>Да ну? :) Если задача NP-hard, то ее частный случай тоже NP-hard? Это неправда.
см. ниже
T>>http://www.youtube.com/watch?v=-m7PFnSvmJM
T>>"In the first half of the talk I will discuss several algorithmic results affecting whole genome assembly -- the problem of assembling a genome from short pieces (called reads). This problem is often reduced to various path problems on graphs. We will first show that the problem of finding the Shortest Chinese Superwalk on a de Bruijn graph is NP-complete/hard, hence demonstrating the computational equivalence of two methods for sequenceassembly: the String Graph approach of Myers et al and the Eulerian Superpath approach of Pevzner et al. We will also demonstrate a simple polynomial time algorithm separating complimentary paths on a graph, which is... T>>" T>>de Bruijn graph — ориентированный(направленный), по нему Chinese postman problem (Shortest Chinese Superwalk) это NP-hard. Mab>А это вообще к делу не относится. Скорее всего здесь речь про какую-то вариацию shortest common superstring.
А de bruijn graph, который на рисунке выше, это mixed graph (смешанный) или ориентированный(направленный)?
Здравствуйте, True2008, Вы писали:
T>>>для смешанного графа — Chinese postman problem NP-hard, следовательно для ориентированного(направленного), частного случая смешанного, Chinese postman problem так же NP-hard. Mab>>Да ну? Если задача NP-hard, то ее частный случай тоже NP-hard? Это неправда. T>см. ниже
Что значит "см. ниже"? Ваши рассуждения ошибочны, разве нет?
T>А de bruijn graph, который на рисунке выше, это mixed graph (смешанный) или ориентированный(направленный)?
Направленный, конечно. Только это к делу не относится -- сформулируйте для начала точно, какая задача там решается, тогда и посмотрим. А то ведь граф этот эйлеров, так что искать в нем shortest chinese walk не слишком сложно, правда ведь?
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, True2008, Вы писали:
T>>>>для смешанного графа — Chinese postman problem NP-hard, следовательно для ориентированного(направленного), частного случая смешанного, Chinese postman problem так же NP-hard. Mab>>>Да ну? :) Если задача NP-hard, то ее частный случай тоже NP-hard? Это неправда. T>>см. ниже Mab>Что значит "см. ниже"? Ваши рассуждения ошибочны, разве нет?
T>>А de bruijn graph, который на рисунке выше, это mixed graph (смешанный) или ориентированный(направленный)? Mab>Направленный, конечно. Только это к делу не относится -- сформулируйте для начала точно, какая задача там решается, тогда и посмотрим. А то ведь граф этот эйлеров, так что искать в нем shortest chinese walk не слишком сложно, правда ведь? :)
Для поиска de bruijn sequences есть два пути? первый — решить на de bruijn графе shortest chinese walk, так? второй путь, приводящий к такому же результату, это решить задачу shortest common superstring для строк, например, 000,001,010,011,100,101,110,111; так? но известно, что найти shortest common superstring это NP-hard, так? т.е. идти по второму пути NP-сложно. по Вашему, идти по первому пути — не NP-сложно, т.е. просто, так?
т.е. по первому сложно, по второму просто? Ваши рассуждения ошибочны, разве нет?
Здравствуйте, True2008, Вы писали:
T>Для поиска de bruijn sequences есть два пути? первый — решить на de bruijn графе shortest chinese walk, так? второй путь, приводящий к такому же результату, это решить задачу shortest common superstring для строк, например, 000,001,010,011,100,101,110,111; так? но известно, что найти shortest common superstring это NP-hard, так? т.е. идти по второму пути NP-сложно. по Вашему, идти по первому пути — не NP-сложно, т.е. просто, так? T>т.е. по первому сложно, по второму просто? Ваши рассуждения ошибочны, разве нет?
NP-сложными бывают не "пути", по которым надо идти, а языки. Говоря прямо (no offense), написанное выше -- бессмыслица. Вы же жонглируете понятиями, смысл которых, по-видимому, понимаете не до конца хорошо. Отсюда и возникают противоречия.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, True2008, Вы писали:
T>>Для поиска de bruijn sequences есть два пути? первый — решить на de bruijn графе shortest chinese walk, так? второй путь, приводящий к такому же результату, это решить задачу shortest common superstring для строк, например, 000,001,010,011,100,101,110,111; так? но известно, что найти shortest common superstring это NP-hard, так? т.е. идти по второму пути NP-сложно. по Вашему, идти по первому пути — не NP-сложно, т.е. просто, так? T>>т.е. по первому сложно, по второму просто? Ваши рассуждения ошибочны, разве нет?
Mab>NP-сложными бывают не "пути", по которым надо идти, а языки. Говоря прямо (no offense), написанное выше -- бессмыслица. Вы же жонглируете понятиями, смысл которых, по-видимому, понимаете не до конца хорошо. Отсюда и возникают противоречия.
Mab>В общем, если хотите разобраться, то надо начинать с азов: Mab>http://en.wikipedia.org/wiki/Decision_problem Mab>http://en.wikipedia.org/wiki/Polynomial-time_Turing_reduction Mab>http://en.wikipedia.org/wiki/NP-hard
Здравствуйте, True2008, Вы писали:
T>вот результат работы программы. но мой взгляд, его получить очень сложно. или я ошибаюсь? Если это вопрос, то я не понимаю, в чем конкретно он состоит.
Я говорил про это: "Finding an optimal solution in a graph with both directed and undirected edges is NP-complete. " и спрашивал, ошибаются ли они. Может я не так трактую термин топикстартера "направленный граф", я под этим понимаю ориентированный граф, в котором как раз могут быть "both directed and undirected edges". Да, если у нас для любых i, j не может быть обеих дуг (i,j) и (j,i), то задача решается потоком. А иначе No solution for the remaining case for mixed networks with some odd-degree vertices has been found. Papadimitriou has shown that this unsolved case is a difficult problem and is NP complete.
