4551
правка
Покрытие множества почти последовательными подмножествами: различия между версиями
Материал из WEGA
Покрытие множества почти последовательными подмножествами (посмотреть исходный код)
Версия от 18:32, 5 февраля 2021
, 5 февраля 2021→Алгоритмы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Алгоритмы) |
||
| Строка 98: | Строка 98: | ||
Алгоритм на каждом шаге рассматривает строку | Алгоритм на каждом шаге рассматривает строку <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, то нижнюю и верхнюю границу можно легко вычислить, точно решив задачу. В противном случае используются стандартные эвристики. | ||
| Строка 107: | Строка 107: | ||
Если бы сеть железных дорог состояла только из одной прямой рельсовой колеи, то соответствующий экземпляр SET COVER обладал бы свойством C1P; экземпляры, возникающие на базе реальных данных, близки к C1P [7,8]. | Если бы сеть железных дорог состояла только из одной прямой рельсовой колеи, то соответствующий экземпляр SET COVER обладал бы свойством C1P; экземпляры, возникающие на базе реальных данных, близки к C1P [7, 8]. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
