Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Поиск в графе одинаковых подграфов, необходимо найти одинаковые участки  
:(
    Опции темы
qw84
Дата 19.4.2007, 14:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 22
Регистрация: 3.4.2007
Где: Воронеж

Репутация: нет
Всего: нет



Возникла проблемка. Есть гиперграф, содержащий до 500000 вершин. Необходим алгоритм поиска одинаковых участков с целью дальнейшей разбивки этого графа на подграфы. Одно из требований задачи - размеры этих участков (одинаковых) должны быть максимальным. 
Помогите пожалуйста с этой проблемой! Существует куча алгоритмов поиска по эталону, но в этой задачи эталонов нет. Рыл уже в направлении гинетических алгоритмов - тоже не очень успешно.

ЗЫЖ на http://algolist.manual.ru не посылайте!!!!

Спасибо
PM MAIL ICQ   Вверх
MBo
Дата 19.4.2007, 15:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 5
Всего: 18



>Необходим алгоритм поиска одинаковых участков 
Это похоже на задачу определения эквивалетности графов, а она NP-Hard
http://en.wikipedia.org/wiki/Graph_isomorphism_problem

Хотя возможно, что для данной задачи существуют методы, например, похожие на поиск в строках (только с поиском в ширину, например)
PM MAIL   Вверх
qw84
Дата 20.4.2007, 14:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 22
Регистрация: 3.4.2007
Где: Воронеж

Репутация: нет
Всего: нет



Работаю дальше в этом направлении... во вложении - что нарыл(генетический алгоритм). Вот собствуенно, никто не сталкивался с упоминаемыми Evolution v3.01 и    Graph Builder v4.04?  В инете найти не получается.  

Спасибо 

Присоединённый файл ( Кол-во скачиваний: 14 )
Присоединённый файл  Met_graph.part1.rar 117,19 Kb
PM MAIL ICQ   Вверх
qw84
Дата 20.4.2007, 14:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 22
Регистрация: 3.4.2007
Где: Воронеж

Репутация: нет
Всего: нет



Вторая часть архива  (как не бился  smile  с разными форматами - меньше 120К не получилось )

Присоединённый файл ( Кол-во скачиваний: 21 )
Присоединённый файл  Met_graph.part2.rar 17,43 Kb
PM MAIL ICQ   Вверх
esperant0
Дата 20.4.2007, 18:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 4
Всего: 14



Цитата(MBo @ 19.4.2007,  15:41)
>Необходим алгоритм поиска одинаковых участков 
Это похоже на задачу определения эквивалетности графов, а она NP-Hard
http://en.wikipedia.org/wiki/Graph_isomorphism_problem

 

Путаеты вы насчет NP-HARD


Тривиально эта задача в классе NP.

Но никто не доказал, и думаю что нельзя доказать, что эта задача NP-HARD

разве, что вы доказали smile


--------------------
 
 Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer 

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором  а затем стерто и которое он - пользователь не мог видеть. 
PM MAIL   Вверх
MBo
Дата 21.4.2007, 11:38 (ссылка) |    (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 5
Всего: 18



esperant0
Да, с Hard для изоморфизма графов я переборщил ;)



PM MAIL   Вверх
qw84
Дата 27.4.2007, 08:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 22
Регистрация: 3.4.2007
Где: Воронеж

Репутация: нет
Всего: нет



Господа! Ваша помощь все еще нужна. Вопрос остается открытым!!!! Очень нужно решить эту задачу, вопрос конечно не жизни или смерти, но около того.......


Спасибо
PM MAIL ICQ   Вверх
MBo
Дата 27.4.2007, 09:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 5
Всего: 18



PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0667 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.