4551
правка
Покрытие множества почти последовательными подмножествами: различия между версиями
Перейти к навигации
Перейти к поиску
Покрытие множества почти последовательными подмножествами (посмотреть исходный код)
Версия от 16:52, 5 февраля 2021
, 5 февраля 2021→Алгоритмы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 58: | Строка 58: | ||
== Алгоритмы == | == Алгоритмы == | ||
Мекке и Вагнер [ ] представили алгоритм, который решает задачу SET COVER, перечисляя все допустимые решения. | Мекке и Вагнер [ ] представили алгоритм, который решает задачу SET COVER, перечисляя все допустимые решения. | ||
Мекке и Вагнер [ ] представили алгоритм, который решает задачу SET COVER, перечисляя все допустимые решения. | |||
Пусть дан ряд ri матрицы A. Частичное решение для строк r 1.. ri представляет собой подмножество C'CC столбцов A, такое, что для каждой строки rj с j 2 f1.. ig существует столбец в C0, покрывающий строку rj. | |||
Основная идея алгоритма заключается в том, чтобы найти оптимальное решение путем итерации по строкам матрицы A и обновления на каждом шаге структуры данных S, которая сохраняет все частичные решения для рассмотренных до этого момента строк. Точнее, на каждом шаге итерации алгоритм рассматривает первую строку A и обновляет структуру данных S соответственно. После этого первая строка A удаляется. Алгоритм выглядит следующим образом. | |||
1 Повторить m раз: { | |||
2 for каждого частичного решения C0 в S, не покрывающего первую строку матрицы A: { | |||
3 for каждого столбца c матрицы A, покрывающего первую строку A:{ | |||
4 Добавить fcg[ C 0 в S; } | |||
5 Удалить С из S;} | |||
6 Удалить первую строку A;} | |||
Этот простой алгоритм перечисления способен создать множество S экспоненциального размера. Поэтому при помощи приведенных выше правил редукции данных после каждого шага итерации выполняется удаление ненужных более частичных решений. С этой целью матрица B ассоциируется с множеством S, где каждая строка соответствует строке матрицы A, а каждый столбец – частичному решению в S: значение ячейки bi;j матрицы B равно 1 в том и только том случае, если j-ое частичное решение B содержит столбец A, покрывающий строку ri. Алгоритм использует матрицу | |||
A A в 0...0 С := | |||
, которая обновляется вместе с S на каждом шаге итерации. | |||
2 Последняя строка C позволяет отличить столбцы, принадлежащие матрице A, от принадлежащих B. | |||
Строка 6 вышеприведенного алгоритма заменяется двумя следующими строками: | |||
6 Удалить первую строку матрицы C; | |||
7 Выполнить редукцию матрицы C и соответствующим образом изменить S;} | |||
По окончании работы алгоритма множество S содержит ровно одно решение, и это решение является оптимальным. Более того, если экземпляр SET COVER хорошо структурирован, то алгоритм имеет полиномиальное время работы: | |||
Теорема 2 [7]. Если матрица A обладает сильным свойством C1P, является редуцированной, а ее строки отсортированы в лексикографическом порядке, то время работы алгоритма составляет O(M3n), где M – максимальное число единиц в строке и в столбце. | |||
Теорема 3 [7]. Если расстояние между первой и последней единицами в каждом столбце не превышает k, то в любой момент времени в любой точке алгоритма количество столбцов в матрице B равно O(2kn), а время работы – O(22kkmn2). | |||
Руф и Шобель [ ] представляют алгоритм на основе метода ветвей и границ для экземпляров задачи SET COVER, среднее количество блоков последовательных единиц в строке у которых невелико. | |||
Алгоритм на каждом шаге рассматривает строку ri текущей матрицы (которая ранее была редуцирована с помощью правил редукции данных) и ветви в Ы случаев, когда Ы – это количество блоков последовательных единиц в ri. В каждом случае выбирается по одному блоку последовательных единиц в ri, а единицы во всех остальных блоках в этой строке заменяются нулями. После этого вычисляются нижняя и верхняя границы веса решения для каждого полученного экземпляра. Если нижняя граница более чем на 1 + e, для заданной константы ", отличается от достигнутой на данный момент наилучшей верхней границы, соответствующий экземпляр подвергается дальнейшему разветвлению. Наконец, возвращается найденная лучшая верхняя граница. | |||
На каждом шаге ветвления Ы вновь созданные экземпляры «ближе» к (сильному) C1P, чем экземпляр, из которого они вышли. Если экземпляр обладает свойством C1P, то нижнюю и верхнюю границу можно легко вычислить, точно решив задачу. В противном случае используются стандартные эвристики. | |||
Экземпляры SET COVER встречаются, например, при оптимизации железныдорожного транспорта, где задача заключается в том, чтобы определить места построения новых железнодорожных станций. Каждая строка в этом случае соответствует существующему населенному пункту, а каждый столбец – точке на существующем пути, где можно было бы построить станцию. Столбец c покрывает строку r, если населенный пункт, соответствующий r, лежит в пределах заданного радиуса вокруг места, соответствующего c. | |||
Если бы сеть железных дорог состояла только из одной прямой рельсовой колеи, то соответствующий экземпляр SET COVER обладал бы свойством C1P; экземпляры, возникающие на базе реальных данных, близки к C1P [7,8]. | |||
== Экспериментальные результаты == | |||
Мекке и Вагнер [ ] проводят эксперименты на экземплярах из реального мира, как описано в разделе «Применение», а также на экземплярах, которые были сгенерированы, начиная с матрицы, обладающей свойством C1P, и заменяя случайным образом определенный процент единиц на нули. Реальные данные состоят представляют собой граф железных дорог с 8200 вершинами и 8700 ребрами плюс 30 000 населенных пунктов. Сгенерированные экземпляры состоят из 50-50 000 строк с 10-200 единиц на строку. До 20% единиц заменены нулями. | |||
В реальных экземплярах правила редукции данных уменьшают количество единиц до 1-25% от исходного количества единиц без применения расширенного правила редукции столбцов и до 0,2-2,5% – с применением расширенного правила редукции. В случае сгенерированных экземпляров, обладающих свойством C1P, количество единиц уменьшается примерно до 2% без применения и до 0,5% с применением расширенного правила редукции по столбцам. Для экземпляров с 20% возмущением количество единиц снижается до 67% без применения правила и до 20% с применением расширенного правила редукции по столбцам. | |||
Перечислительный алгоритм демонстрирует почти линейное время работы для реальных и большинства сгенерированных экземпляров. Только у сгенерированных экземпляров с 20% возмущением время выполнения является квадратичным. | |||
Руф и Шобель [ ] рассматривают три типа экземпляров: экземпляры из реального мира, экземпляры, возникающие из троек Штейнера, и экземпляры, сгенерированные случайным образом. Последние имеют размер 100 x 100 и содержат либо 1-5 блоков последовательных единиц в каждой строке, каждый из которых включает от одной до девяти единиц, либо вероятность наличия единицы в любой ячейке составляет 3% или 5%. | |||
Правила редукции данных, используемые Руфом и Шобель, оказываются достаточно мощными для реальных экземпляров (размер матрицы сокращается в среднем примерно с 1100 x 3100 до 100 x 800), в то же время для остальных типов экземпляров значительного уменьшения размеров не наблюдается. | |||
Алгоритм на основе метода ветвей и границ способен решить почти все реальные экземпляры задач вплоть до оптимальных значений за время от секунды до часа. Во всех случаях, когда оптимальное решение было найдено, первая сгенерированная подзадача уже обеспечивала нижнюю границу, равную весу оптимального решения. | |||
== См. также == | |||
[[Жадные алгоритмы покрытия множества]] | |||
== Литература == | |||
1. Atkins, J.E., Middendorf, M.: On physical mapping and the consecutive ones property for sparse matrices. Discret. Appl. Math. 71(1-3),23-40(1996) | |||
2. Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335-379 (1976) | |||
3. Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835-855 (1965) | |||
4. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979) | |||
5. Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2(1), 139-152(1995) | |||
6. Hsu, W.L., McConnell, R.M.: PC trees and circular-ones arrangements. Theor. Comput. Sci. 296(1), 99-116 (2003) | |||
7. Mecke, S., Wagner, D.: Solving geometric covering problems by data reduction. In: Proceedings of the 12th Annual European | |||
Symposium on Algorithms (ESA '04). LNCS, vol. 3221, pp. 760-771. Springer, Berlin (2004) | |||
8. Ruf, N., Schobel, A.: Set covering with almost consecutive ones property. Discret. Optim. 1(2), 215-228 (2004) | |||
9. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester(1986) | |||