Close Topic Options

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

Подскажите, куда смотреть?

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

Гм... ниасилил...

ну типа так:
считываешь слова всех фраз
n=0
m=0
и т.д
дальше пишешь условие:

если слово = медвед значит n=n+1
если слово равно превед значит m=m+1
и так условия по всем словам ,которые встречаются во фразах
дальше,та переменная,которая будет наименьшей скажет,какое слово встречается реже всех

например, если m окажется наименьшей,значит редчайшее слово-превед

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

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

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

This post has been edited by SonyBrother on 22-08-2006, 19:12

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

на сколько я понял ,надо найти слово,которое наименьшее количество раз встречается во всех фразах,иначе условие не имеет смысла

превед
превед sdandrey
медвед

превед = 2
sdandrey = 1
медвед = 1

и дальше что?

в данном случае задача не имеет решения,т.к нет ни одного слова,встречающегося во всех фразах

Фразы состоят из слов, значит наименьшее множество - множество слов, из которых сосят эти фразы

Фразы состоят из нескольких слов, т.ч. могут быть множества разных размеров, нужно минимальное.

превед
превед sdandrey
медвед

1. {превед, sdandrey, медвед}
2. {превед, медвед}

Второе множество и есть минимальное.


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

Added @ 19:20:
Мне не нужно слово, мне нужно множество слов.

Added @ 19:21:
Причём минимальное.

Все, понял! Лови решение:

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

This post has been edited by SonyBrother on 22-08-2006, 19:26

кажется я понял о чем ты тут глаголишь

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

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

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

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

Кстати эта задачка решается элементарно и быстро при помощи генетического алгоритма

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

У меня есть предчувствие, что подобная задача имеет решение, только вот в какой области?