Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачи о покрытии множества, нужна библиотека или функция / 11 сообщений из 11, страница 1 из 1
10.01.2011, 16:40
    #37051223
DelphiLexx
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачи о покрытии множества, нужна библиотека или функция
Нужна библиотека (dll-файл) или модуль/функция (желательно на Delphi) для решения задачи о покрытии множества, суть которого:
1) Есть множество свойств {F}
2) Есть множество компонентов {K}
Каждый K обладает свойствами из множества {F}, а также каждому К соответствует один элемент P (вес), где P - это положительное число

Задача: Найти подмножество K, которое должно обладать подмножеством {F}, но при этом сумма Р полученных К должна быть минимальна.
Переводя на русский (хоть мы и программисты можем на разных балакать ), это звучало бы так:
Пример:
представим себе, что для выполнения какого-то задания необходим некий набор навыков S. Так же, есть группа людей, владеющих некоторыми из этих навыков. Причем каждый чел. стоит разных денег.
Необходимо сформировать минимальную группу для выполнения задания, включающую в себя носителей необходимых навыков, но при этом по цене чтобы выходило минимально.
...
Рейтинг: 0 / 0
11.01.2011, 17:01
    #37052979
Multy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачи о покрытии множества, нужна библиотека или функция
Т.е. если есть например есть чуваки владеющие знаниями:

1 2 цена 10
2 4 цена 10
5 6 цена 10
и
1 2 3 цена 14
4 5 6 цена 14
нам брать вторых, а если
есть 1 2 3 4 5 6 цена 25 то этого?

Типа того что ли?
...
Рейтинг: 0 / 0
11.01.2011, 18:42
    #37053238
DelphiLexx
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачи о покрытии множества, нужна библиотека или функция
MultyТ.е. если есть например есть чуваки владеющие знаниями:

1 2 цена 10
2 4 цена 10
5 6 цена 10
и
1 2 3 цена 14
4 5 6 цена 14
нам брать вторых, а если
есть 1 2 3 4 5 6 цена 25 то этого?

Типа того что ли?
угу
...
Рейтинг: 0 / 0
11.01.2011, 20:53
    #37053430
Multy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачи о покрытии множества, нужна библиотека или функция
DelphiLexx,
Не знаю есть ли подобные функции. Поищи ресурсов много:

http://ru.wikipedia.org/wiki/Список_алгоритмов
http://ru.wikipedia.org/wiki/Boost
http://algolist.manual.ru/
http://alglib.sources.ru/
http://www.sources.ru/
http://www.codenet.ru/
http://www.delphikingdom.com/
и т.д.

Без извратов можно решить просто перебором.
...
Рейтинг: 0 / 0
12.01.2011, 22:06
    #37055578
DelphiLexx
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачи о покрытии множества, нужна библиотека или функция
MultyDelphiLexx,
Не знаю есть ли подобные функции. Поищи ресурсов много:

http://ru.wikipedia.org/wiki/Список_алгоритмов
http://ru.wikipedia.org/wiki/Boost
http://algolist.manual.ru/
http://alglib.sources.ru/
http://www.sources.ru/
http://www.codenet.ru/
http://www.delphikingdom.com/
и т.д.

Без извратов можно решить просто перебором.
Спасибо
...
Рейтинг: 0 / 0
13.01.2011, 00:15
    #37055692
DelphiLexx
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачи о покрытии множества, нужна библиотека или функция
Но к сожалению, я не нашел в этих пакетов решение задач поиска наименьшего покрытия множества.
...
Рейтинг: 0 / 0
13.01.2011, 22:13
    #37057861
Multy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачи о покрытии множества, нужна библиотека или функция
DelphiLexxНо к сожалению, я не нашел в этих пакетов решение задач поиска наименьшего покрытия множества.

Не удивительно, чем специализированнее задача, тем менее вероятно найти для неё готовое решение.

Если тебе надо просто решить, то можно простым перебором. Если именно по теории множеств - видимо придётся думать...
...
Рейтинг: 0 / 0
14.01.2011, 01:49
    #37058065
ShSerge
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачи о покрытии множества, нужна библиотека или функция
Сюръективное, инъективное, биективное или гомоморфное, эпиморфное или изоморфное покрытие?
...
Рейтинг: 0 / 0
14.01.2011, 02:19
    #37058087
Multy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачи о покрытии множества, нужна библиотека или функция
ShSergeСюръективное, инъективное, биективное или гомоморфное, эпиморфное или изоморфное покрытие?

Я только два слова понял "или" и "покрытие"...
...
Рейтинг: 0 / 0
14.01.2011, 15:27
    #37059249
DelphiLexx
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачи о покрытии множества, нужна библиотека или функция
ShSerge,

обычное
...
Рейтинг: 0 / 0
15.01.2011, 02:42
    #37060143
coffeesnake
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Задачи о покрытии множества, нужна библиотека или функция
Ну это вариант задачи о комивояжоре (NP-полной), решается, например, методом ветвей и границ и пр. Я бы делал полным перебором в несколько потоков, т.к. в этих методах не силён.
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачи о покрытии множества, нужна библиотека или функция / 11 сообщений из 11, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]