4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 18: | Строка 18: | ||
Вдохновленные задачами, возникающими в связи с оптимизацией железнодорожного транспорта, Мекке и Вагнер [7] рассматривают случай с экземплярами SET COVER, обладающими свойством «почти C1P». | Вдохновленные задачами, возникающими в связи с оптимизацией железнодорожного транспорта, Мекке и Вагнер [7] рассматривают случай с экземплярами SET COVER, обладающими свойством «почти C1P». Обладающие свойством «почти С1Р» матрицы похожи на матрицы, сгенерированные следующим образом: начиная с матрицы, обладающей свойством С1Р, случайным образом заменяем определенный процент единиц на нули [7]. Напротив, с точки зрения Руфа и Шёбель [8], наличие свойства «почти С1Р» означает, что среднее количество блоков последовательных единиц в строке значительно меньше количества столбцов матрицы. В данной статье будут приведены некоторые полученные ими результаты. | ||
== Нотация == | == Нотация == | ||
Строка 56: | Строка 56: | ||
== Алгоритмы == | == Алгоритмы == | ||
Мекке и Вагнер [7] представили алгоритм, который решает задачу SET COVER | Мекке и Вагнер [7] представили алгоритм, который решает задачу SET COVER с помощью перечисления всех допустимых решений. | ||
Строка 97: | Строка 97: | ||
Алгоритм на каждом шаге рассматривает строку <math>r_i</math> текущей матрицы (которая ранее была редуцирована с помощью правил редукции данных) и | Алгоритм на каждом шаге рассматривает строку <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, чем экземпляр, | На каждом шаге ветвления вновь созданные экземпляры <math>bl_i</math> «ближе» к (сильному) C1P, чем экземпляр, потомками которого они являются. Если экземпляр обладает свойством C1P, то нижнюю и верхнюю границу можно легко вычислить, решив задачу точно. В противном случае используются стандартные эвристики. | ||
== Применение == | |||
Экземпляры SET COVER встречаются, например, при оптимизации | Экземпляры SET COVER встречаются, например, при оптимизации железнодорожной сети, где задача заключается в том, чтобы определить места построения новых железнодорожных станций. Каждая строка в этом случае соответствует существующему населенному пункту, а каждый столбец – точке на существующем пути, где можно было бы построить станцию. Столбец c покрывает строку r, если населенный пункт, соответствующий r, лежит в пределах заданного радиуса вокруг места, соответствующего c. | ||
Строка 109: | Строка 110: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Мекке и Вагнер [7] проводят эксперименты на экземплярах из реального мира, как описано в разделе «Применение», а также на экземплярах, которые были сгенерированы, начиная с матрицы, обладающей свойством C1P, и заменяя случайным образом определенный процент единиц на нули. Реальные данные | Мекке и Вагнер [7] проводят эксперименты на экземплярах из реального мира, как описано в разделе «Применение», а также на экземплярах, которые были сгенерированы, начиная с матрицы, обладающей свойством C1P, и заменяя случайным образом определенный процент единиц на нули. Реальные данные представляют собой граф железных дорог с 8200 вершинами и 8700 ребрами плюс 30 000 населенных пунктов. Сгенерированные экземпляры состоят из 50-50 000 строк с 10-200 единиц на строку. До 20% единиц заменены нулями. | ||
Строка 115: | Строка 116: | ||
Перечисляющий алгоритм демонстрирует почти линейное время работы для реальных и большинства сгенерированных экземпляров. Только у сгенерированных экземпляров с 20% возмущением время выполнения является квадратичным. | |||
правок