Аннотация:
Доказана NP-полнота некоторых задач выбора подпоследовательности из последовательности векторов евклидова пространства, состоящей из конечного числа членов. Предполагается, что искомая подпоследовательность содержит фиксированное число векторов, близких между собой по критерию минимума суммы квадратов расстояний, причем выбор векторов подчинен условию: разность между номерами последующего и предыдущего выбираемых векторов ограничена сверху и снизу некоторыми константами. Библ. 9.
Полный текст:
PDF файл (380 kB)