с разными форматами - меньше 120К не получилось )| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск в графе одинаковых подграфов |
| Автор: qw84 19.4.2007, 14:58 |
| Возникла проблемка. Есть гиперграф, содержащий до 500000 вершин. Необходим алгоритм поиска одинаковых участков с целью дальнейшей разбивки этого графа на подграфы. Одно из требований задачи - размеры этих участков (одинаковых) должны быть максимальным. Помогите пожалуйста с этой проблемой! Существует куча алгоритмов поиска по эталону, но в этой задачи эталонов нет. Рыл уже в направлении гинетических алгоритмов - тоже не очень успешно. ЗЫЖ на http://algolist.manual.ru не посылайте!!!! Спасибо |
| Автор: MBo 19.4.2007, 15:41 |
| >Необходим алгоритм поиска одинаковых участков Это похоже на задачу определения эквивалетности графов, а она NP-Hard http://en.wikipedia.org/wiki/Graph_isomorphism_problem Хотя возможно, что для данной задачи существуют методы, например, похожие на поиск в строках (только с поиском в ширину, например) |
| Автор: qw84 20.4.2007, 14:46 |
| Работаю дальше в этом направлении... во вложении - что нарыл(генетический алгоритм). Вот собствуенно, никто не сталкивался с упоминаемыми Evolution v3.01 и Graph Builder v4.04? В инете найти не получается. Спасибо |
| Автор: qw84 20.4.2007, 14:49 |
| Вторая часть архива (как не бился с разными форматами - меньше 120К не получилось ) |
| Автор: esperant0 20.4.2007, 18:10 | ||
Путаеты вы насчет NP-HARD Тривиально эта задача в классе NP. Но никто не доказал, и думаю что нельзя доказать, что эта задача NP-HARD разве, что вы доказали  |
| Автор: MBo 21.4.2007, 11:38 |
| esperant0, Да, с Hard для изоморфизма графов я переборщил ;) |
| Автор: qw84 27.4.2007, 08:59 |
| Господа! Ваша помощь все еще нужна. Вопрос остается открытым!!!! Очень нужно решить эту задачу, вопрос конечно не жизни или смерти, но около того....... Спасибо |
| Автор: MBo 27.4.2007, 09:11 |
| http://amalfi.dis.unina.it/graph/old/ |