Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Нужна помощь с алгоритмом...
Форум на CrossPlatform.RU > Курилка > Алгоритмы, задачи по программированию, логические игры
ViGOur
Есть хеш документов:
// qint64 - номер документа, CDocument* - сам документ, использую хеш так как нужно быстро находить нужные документы.
QHash<qint64, CDocument*> m_hashDoc;
Документов может быть огромное количество.
Я умею определить, похож один документ на другой или нет:
bool isEqual( CDocument *p1, CDocument *p2);


Нужно, оптимально быстро разбить документы на категории, в каждой категории должны быть только похожие друг на друга документы.
Iron Bug
как-то неполно поставлена задача.
если, к примеру, есть индуктивность (если А похож на B и B похож на C, то из этого следует, что A похож на C) - тогда можно попытаться строить цепочки зависимостей. однако, количество групп заранее неизвестно, поэтому прогнозировать скорость разбиения трудно.
в общем случае, в худшем варианте количество групп будет равно количеству файлов. и если нет индуктивности, то есть только один метод: полный перебор, сравнение каждого с каждым. а как иначе определить похожесть?
ViGOur
Цитата(Iron Bug @ 16.3.2010, 19:32) *
если А похож на B и B похож на C, то из этого следует, что A похож на C
Что-то вроде этого, без перебора для составления списка похожих документов не обойтись.

Но вот как быть с разбиением на категории, после получения списка похожих документов для каждого документа?
Если есть примерно следующее:
Цитата
д1 - д3, д5, ...
д2 - д4, д7, ...
д3 - д1, д8, ...
... - ...
Iron Bug
я думаю, просто от первого элемента строить дерево зависимостей и как-то помечать уже задействованные вершины. как только весь список закончится - множество построенных деревьев и будет искомым. вероятно, можно чуть-чуть оптимальнее что-то придумать, удалять вершины из списка и т.п. - это уже чисто техническая сторона вопроса, но по сравнению с затратами на сравнение файлов это будет ноль :)

да, кстати, в boost::algorithms в BGL есть алгоритм Connected Components. но тут надо подумать, удобно ли тебе будет под него подстраиваться или быстрее "на коленке" написать.
ViGOur
Такс, более менее картинка отрисовывается как это делать.
Проект на Qt и честно говоря не хотелось бы еще boost туда подключать, да и насколько я слышал у BGL свои заморочки, в которые нужно отдельно вникать, а мне как говориться нужно было сделать еще вчера. :)

Так что подумаю как реализовать мини графы для моих нужд...
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Форум IP.Board © 2001-2022 IPS, Inc.