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

Алгоритм на каждом шаге рассматривает строку ri текущей матрицы (которая ранее была редуцирована с помощью правил редукции данных) и ветви в Ы случаев, когда Ы – это количество блоков последовательных единиц в ri. В каждом случае выбирается по одному блоку последовательных единиц в ri, а единицы во всех остальных блоках в этой строке заменяются нулями. После этого вычисляются нижняя и верхняя границы веса решения для каждого полученного экземпляра. Если нижняя граница более чем на 1 + e, для заданной константы ", отличается от достигнутой на данный момент наилучшей верхней границы, соответствующий экземпляр подвергается дальнейшему разветвлению. Наконец, возвращается найденная лучшая верхняя граница.

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

Если бы сеть железных дорог состояла только из одной прямой рельсовой колеи, то соответствующий экземпляр SET COVER обладал бы свойством C1P; экземпляры, возникающие на базе реальных данных, близки к C1P [7,8].