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

Мекке и Вагнер [ ] проводят эксперименты на экземплярах из реального мира, как описано в разделе «Применение», а также на экземплярах, которые были сгенерированы, начиная с матрицы, обладающей свойством C1P, и заменяя случайным образом определенный процент единиц на нули. Реальные данные состоят представляют собой граф железных дорог с 8200 вершинами и 8700 ребрами плюс 30 000 населенных пунктов. Сгенерированные экземпляры состоят из 50-50 000 строк с 10-200 единиц на строку. До 20% единиц заменены нулями.

Руф и Шобель [ ] рассматривают три типа экземпляров: экземпляры из реального мира, экземпляры, возникающие из троек Штейнера, и экземпляры, сгенерированные случайным образом. Последние имеют размер 100 x 100 и содержат либо 1-5 блоков последовательных единиц в каждой строке, каждый из которых включает от одной до девяти единиц, либо вероятность наличия единицы в любой ячейке составляет 3% или 5%.

Правила редукции данных, используемые Руфом и Шобель, оказываются достаточно мощными для реальных экземпляров (размер матрицы сокращается в среднем примерно с 1100 x 3100 до 100 x 800), в то же время для остальных типов экземпляров значительного уменьшения размеров не наблюдается.