Имеется энное количество фраз и каждая фраза состоит из одного или более слов. Задача: найти наименьшее множество слов, такое, чтобы в каждой фразе содержалось по крайней мере одно слово из этого множества.
Подскажите, куда смотреть? :)
sdandrey
@ 22-08-2006, 18:33
Людоедка Эллочка тебе поможет :D
а если по существу,напиши обычную програмку по поиску минимума,пусть переберает все фразы и суммирует все попадающиеся одинаковые слова,сумма которая будет наименьшей - наименьшее множество слов
sdandrey
@ 22-08-2006, 18:53
| QUOTE (Set @ 22-08-2006, 15:46) |
| Гм... ниасилил... :D |
ну типа так:
считываешь слова всех фраз
n=0
m=0
и т.д
дальше пишешь условие:
если слово = медвед значит n=n+1
если слово равно превед значит m=m+1
и так условия по всем словам ,которые встречаются во фразах
дальше,та переменная,которая будет наименьшей скажет,какое слово встречается реже всех
например, если m окажется наименьшей,значит редчайшее слово-превед
:D
Нужно не редчайшее слово, а наименьшее множество слов, встречающихся во всех фразах. Т.е. какую бы фразы ни взять в ней обязательно есть слово из этого множества.
sdandrey
@ 22-08-2006, 19:03
| QUOTE (Set @ 22-08-2006, 15:57) |
| Нужно не редчайшее слово, а наименьшее множество слов, встречающихся во всех фразах. Т.е. какую бы фразы ни взять в ней обязательно есть слово из этого множества. |
тогда в начале пишешь условие: выбираешь слова,встречающиеся во всех фразах,а потом с этой выборкой делаешь то,что я писал в предыдущем посту
SonyBrother
@ 22-08-2006, 19:11
| QUOTE (Set @ 22-08-2006, 15:57) |
| Нужно не редчайшее слово, а наименьшее множество слов, встречающихся во всех фразах. Т.е. какую бы фразы ни взять в ней обязательно есть слово из этого множества. |
Фразы состоят из слов, значит наименьшее множество - множество слов, из которых сосят эти фразы, а вообще бредовая задача. Это твой пересказ условия или она такая и есть? Сказал бы из какой области эта задача, чтобы хоть как-то понять чего хочут
sdandrey
@ 22-08-2006, 19:12
| QUOTE (SonyBrother @ 22-08-2006, 16:11) |
| QUOTE (Set @ 22-08-2006, 15:57) | | Нужно не редчайшее слово, а наименьшее множество слов, встречающихся во всех фразах. Т.е. какую бы фразы ни взять в ней обязательно есть слово из этого множества. |
Фраза состоит слов, значит наименьшее множество - любое множество слов, а вообще бредовая задача. Это твой пересказ условия или она такая и есть? Сказал бы из какой области эта задача, чтобы хоть как-то понять чего хочут |
на сколько я понял ,надо найти слово,которое наименьшее количество раз встречается во всех фразах,иначе условие не имеет смысла
превед
превед sdandrey
медвед
превед = 2
sdandrey = 1
медвед = 1
и дальше что?
sdandrey
@ 22-08-2006, 19:18
| QUOTE (Set @ 22-08-2006, 16:14) |
превед
превед sdandrey
медвед
превед = 2
sdandrey = 1
медвед = 1
и дальше что? |
в данном случае задача не имеет решения,т.к нет ни одного слова,встречающегося во всех фразах
| QUOTE (SonyBrother @ 22-08-2006, 19:11) |
| QUOTE (Set @ 22-08-2006, 15:57) | | Нужно не редчайшее слово, а наименьшее множество слов, встречающихся во всех фразах. Т.е. какую бы фразы ни взять в ней обязательно есть слово из этого множества. |
Фразы состоят из слов, значит наименьшее множество - множество слов, из которых сосят эти фразы
|
Фразы состоят из нескольких слов, т.ч. могут быть множества разных размеров, нужно минимальное.
превед
превед sdandrey
медвед
1. {превед, sdandrey, медвед}
2. {превед, медвед}
Второе множество и есть минимальное. ;)
Это не задача в прямом смысле, мне нужен алгоритм для обработки текстовой базы.
Added:
Мне не нужно слово, мне нужно множество слов.
Added:
Причём минимальное. :)
SonyBrother
@ 22-08-2006, 19:22
Все, понял! Лови решение:
Выбираем сначала все фразы с одним словом и заносим слова в искомое множество. Вычеркиваем все фразы из исходного набора с этими словами. Получаем новый исходный набор фраз и повторяем все сначала. Если однословных фраз нет, то мы должны рассматривать несколько вариантов, выбирая отдельные слова из самых короткиз фраз. Примерно так
sdandrey
@ 22-08-2006, 19:28
| QUOTE (Set @ 22-08-2006, 15:57) |
| Нужно не редчайшее слово, а наименьшее множество слов, встречающихся во всех фразах. Т.е. какую бы фразы ни взять в ней обязательно есть слово из этого множества. |
кажется я понял о чем ты тут глаголишь :)
вобщем делай так: сначала берёшь и делаешь выборку из слов,которые ,вообще, встречаются во фразах
дальше берёшь каждое слово и проверяешь встречается оно во всех фразах или нет,если попадаются несколько слов,встречающихся во всех фразах,выбираешь то,которое встречается минимальное количество раз и получаешь,что твоё множество состоит из одного слова
если нет слов,которые встречаются во всех фразах,то начинаешь перебирать все возможные варианты из двух слов,опять же если встречаются две пары,присутствующие во всех фразах,то выбираешь ту пару,которая присутствует минимальное количество раз и твоё множество будет состоять из двух слов
ежели нет пары,встречающейся во всех фразах,то берёшь три слова и т.д,пока не найдёшь минимальное количество слов,которые встречаются во всех фразах и эти сами слова
SonyBrother
@ 22-08-2006, 19:31
Кстати эта задачка решается элементарно и быстро при помощи генетического алгоритма
Перебор вариантов в связи с огромным объёмом данных не представляется возможным, а генетический алгоритм тоже базируется на своего рода переборе.
У меня есть предчувствие, что подобная задача имеет решение, только вот в какой области?
sdandrey
@ 22-08-2006, 19:59
| QUOTE (Set @ 22-08-2006, 16:52) |
Перебор вариантов в связи с огромным объёмом данных не представляется возможным, а генетический алгоритм тоже базируется на своего рода переборе.
У меня есть предчувствие, что подобная задача имеет решение, только вот в какой области? |
как без перебора вариантов решить задачу я не знаю,но как увеличить быстроту решения и уменьшить количество переборов есть идея:
перебераешь все слова во фразах и находишь те,которые встречаются максимальное количество раз,например,если фо фразах 1000 слов,то выбираешь 100 наиболее часто встречающихся слов и 100 наименее часто встречающихся слов и уже с этими словами делаешь телодвижения,описанные в предыдущем посте,вобщем время решения уменьщается в 5 раз
как другой вариант берёшь все слова которые в 5 или 10 раз чаше встречаются и которые в 5 или 10 раз реже,чем все остальные слова во фразах и уже с этими словами делаешь телодвижения,описанные в предыдущем посте,вобщем время решения уменьщается ,опять же, в какое-то количество раз
если еще придумаю оптимизаций,отпишусь :)
Added:
подправил немного вариант,хотя ,вариант дающий 100% правильное решение - это полный перебор,т.к могут быть некоторые исключения из правил,хотя это очень долгий вариант
obaldin
@ 22-08-2006, 20:35
Назовем "жадным" следующий алгоритм: берем слово, встречающееся в наибольшем количестве фраз и добавляем его в результирующее множество, вычеркиваем фразы, в которых это слово встречалось, повторяем процесс. Кто-нибудь может предложить контрпример для этого алгоритма? А то у меня с ходу что-то не придумалось.
Кстати, это задача из области теории или практики? Т.е. нужен обязательно глобальный оптимум, или достаточно достичь "приемлемого" решения за приемлемое время?
Это практика. А если построить бинарную матрицу, слова - строки, фразы - столбцы, задача преобразовать матрицу так, чтобы осталось минимальное количество строк при неизменном числе ненулевых столбцов ... нет ли решений для такого случае?
Added:Хм, это случаем не задача минимального покрытия из комбинаторики...
Added:http://en.wikipedia.org/wiki/Hitting_set Есс, вот оно... моя задача. :)
Added:Только мне надо минимальное "k"
Added:minimum hitting set problem :D
Added:obaldin рулит! :actu:
http://cs.nyu.edu/~cil217/Thesis/algorithm.html#hitting_set_solver
sdandrey
@ 22-08-2006, 21:47
| QUOTE (Set @ 22-08-2006, 17:57) |
А если построить бинарную матрицу, слова - строки, фразы - столбцы, задача преобразовать матрицу так, чтобы осталось минимальное количество строк при неизменном числе ненулевых столбцов ... нет ли решений для такого случае?
|
матрицу построить не проблема,проблема будет,если матрица не окажется квадратной,что скорее всего, и будет
другими словами,если количество слов не будет равно количеству фраз,то решения с матрицами не будет
по моему, вариант ,который предложил obaldin оптимальный из всех предложенных ранее
obaldin
@ 22-08-2006, 22:44
Ну, если уж доказано, что задача NP-полная, то тут возникают нюансы. "Жадный" алгоритм может не дать теоретического оптимума. С другой стороны, он должен быть очень быстрым, поэтому надо смотреть на практике, насколько удовлетворительные решения он будет давать. Если качество решения удовлетворять не будет, то придется прибегать к методам эвристического поиска, например к генетическим алгоритмам, как уже предложил SonyBrother. Кстати, при всей моей любви к генетическим алгоритмам, не уверен, что на этой задаче будет легко добиться от них хороших результатов, очень уж неприятное будет здесь пространство поиска.
(проходя мимо) вот оно, это чувтсво.... слоган топика - почувствуй себя идиотом :diablo: