Покрытие множества почти последовательными подмножествами: различия между версиями

Экземпляры SET COVER встречаются, например, при оптимизации железнодорожного транспорта, где задача заключается в том, чтобы определить места построения новых железнодорожных станций. Каждая строка в этом случае соответствует существующему населенному пункту, а каждый столбец – точке на существующем пути, где можно было бы построить станцию. Столбец c покрывает строку r, если населенный пункт, соответствующий r, лежит в пределах заданного радиуса вокруг места, соответствующего c.

Мекке и Вагнер [7] проводят эксперименты на экземплярах из реального мира, как описано в разделе «Применение», а также на экземплярах, которые были сгенерированы, начиная с матрицы, обладающей свойством C1P, и заменяя случайным образом определенный процент единиц на нули. Реальные данные состоят представляют собой граф железных дорог с 8200 вершинами и 8700 ребрами плюс 30 000 населенных пунктов. Сгенерированные экземпляры состоят из 50-50 000 строк с 10-200 единиц на строку. До 20% единиц заменены нулями.

Перечислительный алгоритм демонстрирует почти линейное время работы для реальных и большинства сгенерированных экземпляров. Только у сгенерированных экземпляров с 20% возмущением время выполнения является квадратичным.