Задать вопрос
@rshruslan

Каким образом можно сделать рекурсивную функцию кластеризации объектов?

Всем привет, у меня имеется такой объект с тегами где ключ - тег, а значение объект тегов (где ключ - тег, а значение это кол-во пересечения этих двух тегов)
6057602c06276485361962.jpeg
60576038de32f883508154.jpeg
6057604439f98060269916.jpeg

Каким образом можно рекурсивно сделать так, чтобы искалась цепочка всех несовместных тегов (чтобы в группе каждые теги были не совместны никак) вот как пример 1 группа:

6057605f7e810360822466.jpeg

Был бы благодарен за псевдокод или хотя бы алгоритм.
  • Вопрос задан
  • 108 просмотров
Подписаться 1 Простой Комментировать
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
У вас есть граф, где вершины - теги, и есть ребра между ними. Если брать ребро там, где два тега не совместимы, то у вас задача поиска клик.

Во первых, тут есть неоднозначность. Может быть так что теги A,B,C попарно несовместимы, но заодно попарно несовместимы теги A,D,E - куда относить тег A, в какую группу?

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

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

Еще есть Алгоритм Брона — Кербоша. Он перебирает все максимальные клики.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы