Нужна помощь с алгоритмом..., математика и программирование! Опции Подписка на тему Сообщить другу Версия для печати Скачать тему Подписка на этот форум Режимы отображения Древовидный Переключить на: Стандартный Переключить на: Линейный

[ViGOur]

Есть хеш документов:

// qint64 - номер документа, CDocument* - сам документ, использую хеш так как нужно быстро находить нужные документы.
QHash<qint64, CDocument*> m_hashDoc;

Документов может быть огромное количество.
Я умею определить, похож один документ на другой или нет:

bool isEqual( CDocument *p1, CDocument *p2);

Нужно, оптимально быстро разбить документы на категории, в каждой категории должны быть только похожие друг на друга документы.

[Iron Bug]

я думаю, просто от первого элемента строить дерево зависимостей и как-то помечать уже задействованные вершины. как только весь список закончится - множество построенных деревьев и будет искомым. вероятно, можно чуть-чуть оптимальнее что-то придумать, удалять вершины из списка и т.п. - это уже чисто техническая сторона вопроса, но по сравнению с затратами на сравнение файлов это будет ноль

да, кстати, в boost::algorithms в BGL есть алгоритм Connected Components. но тут надо подумать, удобно ли тебе будет под него подстраиваться или быстрее "на коленке" написать.

Сообщение отредактировал Iron Bug - 16.3.2010, 20:54