Каким образом получить такой набор? Какие методы использовать?

Question

[namelessanonymous]

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

Comments

[dollar]

Зависит от того, нужна ли оптимизация и какая: память, процессор, сеть (если на разных компах). Оптимизация также зависит от того, где какие порядки, сколько в среднем ожидается слов на документ, сколько может быть документов и сколько всего слов примерно. А также важно понимать, нужно ли вам идеальное решение (математически точное), или хватит близкого к идеальному.

Кроме того, не ясно, как соотносятся максимум и минимум. Что лучше: а) 2 документа, в которых 10 слов, или б) 3 документа, в которых 15 слов? В первом меньше документов, а во втором больше слов. Везде свои есть плюсы и минусы. Так что не ясно, по какому критерию сравнивать.

Answer 1

[Руслан .]

Возможно жадный алгоритм подойдет.
Например выбираем документ с самым большим числом уникальных слов.
Затем выбираем документ с самым большим числом уникальных слов непокрытых предыдущим.
И т.д. повторяем до тех пор пока не покроем все слова.

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

Answer 2

[Wataru]

Это похоже на задачу set cover. Легких алгоритмов тут нет. Только полный перебор с отсечениями. Еще всякие методы отжига и эволюционные алгоритмы могут найти хорошее решение. Ну и, задачу можно переформулировать в виде integer linear programming и решать какой-то из существующих библиотек.

Если количество слов маленькое (типа 25-30), то можно решать динамическим программированием по маске покрытых слов.

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