Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Задача о покрытии

Есть множество элементов и множество подмножеств , состоящих из элементов . Необходимо найти минимальное число подмножеств из таких, чтобы объединение этих подмножеств содержало все элементы множества . Задача имеет простую экономическую интерпретацию: пусть, например, имеется некоторое количество клиентов и для их обслуживания необходимо выбрать некоторое количество сервисных центров.

Очевидно, здесь решение можно также представить двоичным вектором

X= (x₁,…, x_n), где:

x_i=1, подмножество входит в покрытие;

x_i=0, если не входит в покрытие;

При этом:

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