Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Последний раз редактировалось Delphist 10.01.2011, 00:16, всего редактировалось 1 раз.
Здравствуйте. По роду деятельности я программист и сейчас свою проблему записал в математическом виде 1) Есть множество свойств {ФП} 2) Есть множество компонентов {K} Каждый K обладает свойствами из множества {ФП}, а также каждому К соответствует один элемент P, где P - это положительное число
Задача: Найти набор (подмножество) {k}, которые в результате дадут строго заданное подмножество {фп}, но при этом сумма Р полученных К должна быть минимальна.
Вопрос: Как решаются подобного рода задачи, симплексом (если да, то как будет выглядеть целевая ф-ция и ограничения) или быть может что-нибудь из теории множеств?
Здравствуйте. ... свою проблему записал в математическом виде
Это вы так думаете что в математическом виде, математики так не думают (отвечу за всех)
deep blue
Re: Возник вопрос по множеству и их оптимизации
10.01.2011, 01:43
У каждого компонента задано подмножество свойств и его вес P. Нужно покрыть все множество свойств его допустимыми подмножествами (компонентами), при этом суммарный вес должен быть минимален. Это известная задача о покрытии, а точнее о разбиении множества на допустимые подмножества, она NP-трудная, но решается достаточно быстро (как правило). Есть много переборных алгоритмов ее решения, для ознакомления с самой задачей можно глянуть “Теория графов: алгоритмический подход. Кристофидес”, а чтобы эффективно ее решать- лучше почитать что-нибудь на английском, но Кристофидеса скорее всего будет достаточно.
Delphist
Re: Возник вопрос по множеству и их оптимизации
10.01.2011, 16:02
а симплексом нельзя ли как-нить решить?
deep blue
Re: Возник вопрос по множеству и их оптимизации
10.01.2011, 17:57
Обычным симплексом (без отсекающих плоскостей) нельзя, это задача ЦЛП, а не ЛП. Симплексом можно получить оценку снизу, решая ЛП вместо ЦЛП, а далее использовать ее в переборе. В Кристофидесе похожий алгоритм, но без симплексной оценки, а в статьях на тему set covering problem чего только нет.