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

Мекке и Вагнер [7] представили алгоритм, который решает задачу SET COVER с помощью перечисления всех допустимых решений.

Алгоритм на каждом шаге рассматривает строку <math>r_i</math> текущей матрицы (которая ранее была редуцирована с помощью правил редукции данных) и производит ее ветвление на <math>bl_i</math> случаев, где <math>bl_i</math> – это количество блоков последовательных единиц в <math>r_i</math>. В каждом случае выбирается по одному блоку последовательных единиц в <math>r_i</math>, а единицы во всех остальных блоках в этой строке заменяются нулями. После этого вычисляются нижняя и верхняя границы веса решения для каждого полученного экземпляра. Если нижняя граница более чем на <math>1 + \epsilon</math> (для заданной константы <math>\epsilon</math>) отличается от достигнутой на данный момент наилучшей верхней границы, соответствующий экземпляр подвергается дальнейшему ветвлению. Наконец, возвращается найденная лучшая верхняя граница.

На каждом шаге ветвления вновь созданные экземпляры <math>bl_i</math> «ближе» к (сильному) C1P, чем экземпляр, потомками которого они являются. Если экземпляр обладает свойством C1P, то нижнюю и верхнюю границу можно легко вычислить, решив задачу точно. В противном случае используются стандартные эвристики.

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