КвантоФорум :: Recent Posts Голосов: 1 Адрес блога: http://quantoforum.ru Добавлен: 2013-05-02 14:40:55

алгоритмические задачки

2016-08-11 09:28:45 (читать в оригинале)

Рассмотрим облако из конечного числа точек. Возьмем шпагу и проткнем его насквозь. Какое-то число точек нанижется на шпагу. Спрашивается, минимум сколько раз надо протыкать облако шпагой, чтобы нанизать его полностью?

Это случай классической задачи о покрытии. Имеется конечное множество точек и некоторая совокупность его подмножеств. Требуется покрыть это множество, использовав минимальное количество указанных подмножеств. В нашем случае совокупность подмножеств состоит из отрезков. Если решать эту задачу с помощью жадного алгоритма, который на каждом шаге выбирает подмножество, покрывающее максимальное число точек, то решение, как известно, не всегда минимально, чему имеется стандартный контрпример с 5 подмножествами.



А в случае со шпагой, т.е. с отрезками, такой пример можно придумать? Конечно, не обязательно с 5 подмножествами. ))