Close Topic Options

как без перебора вариантов решить задачу я не знаю,но как увеличить быстроту решения и уменьшить количество переборов есть идея:

перебераешь все слова во фразах и находишь те,которые встречаются максимальное количество раз,например,если фо фразах 1000 слов,то выбираешь 100 наиболее часто встречающихся слов и 100 наименее часто встречающихся слов и уже с этими словами делаешь телодвижения,описанные в предыдущем посте,вобщем время решения уменьщается в 5 раз

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

если еще придумаю оптимизаций,отпишусь

Added @ 20:05:
подправил немного вариант,хотя ,вариант дающий 100% правильное решение - это полный перебор,т.к могут быть некоторые исключения из правил,хотя это очень долгий вариант

This post has been edited by sdandrey on 22-08-2006, 20:04

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

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

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

Added @ 21:11:
Хм, это случаем не задача минимального покрытия из комбинаторики...

Added @ 21:24:
http://en.wikipedia.org/wiki/Hitting_set Есс, вот оно... моя задача.

Added @ 21:26:
Только мне надо минимальное "k"

Added @ 21:28:
minimum hitting set problem

Added @ 21:37:
obaldin рулит!

http://cs.nyu.edu/~cil217/Thesis/algorithm.html#hitting_set_solver

матрицу построить не проблема,проблема будет,если матрица не окажется квадратной,что скорее всего, и будет
другими словами,если количество слов не будет равно количеству фраз,то решения с матрицами не будет

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

Ну, если уж доказано, что задача NP-полная, то тут возникают нюансы. "Жадный" алгоритм может не дать теоретического оптимума. С другой стороны, он должен быть очень быстрым, поэтому надо смотреть на практике, насколько удовлетворительные решения он будет давать. Если качество решения удовлетворять не будет, то придется прибегать к методам эвристического поиска, например к генетическим алгоритмам, как уже предложил SonyBrother. Кстати, при всей моей любви к генетическим алгоритмам, не уверен, что на этой задаче будет легко добиться от них хороших результатов, очень уж неприятное будет здесь пространство поиска.

(проходя мимо) вот оно, это чувтсво.... слоган топика - почувствуй себя идиотом