4551
правка
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
Строка 40: | Строка 40: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Все вышеперечисленные подходы оставляют нерешенными некоторые вопросы. Например, можно ли найти более простое доказательство NP-полноты, которое можно проверить без исполнения компьютерных программ? Было бы желательно улучшить константный коэффициент аппроксимации, который может быть достигнут за полиномиальное время (для упрощения доказательства константа, введенная в работе [ ], не вычисляется явно и может быть достаточно большой, если доказательство проводится не слишком аккуратно). Есть надежда, что временную границу для схемы аппроксимации можно улучшить. Также может оказаться возможным оптимизировать алгоритмы, эффективно вычисляющие точную триангуляцию с минимальным весом для больших случайных наборов точек, таким образом, чтобы они могли эффективно решать более широкий класс задач, а не только задачи с полностью случайными наборами точек. Возможно, этой цели можно достичь при помощи сочетания этого подхода и алгоритмов с фиксированными параметрами, как в работах [2, 4], либо иными способами. Также остается открытым вопрос, можно ли еще больше улучшить субэкспоненциальный точный метод вычисления триангуляции. | Все вышеперечисленные подходы оставляют нерешенными некоторые вопросы. Например, можно ли найти более простое доказательство NP-полноты, которое можно проверить без исполнения компьютерных программ? Было бы желательно улучшить константный коэффициент аппроксимации, который может быть достигнут за полиномиальное время (для упрощения доказательства константа, введенная в работе [7], не вычисляется явно и может быть достаточно большой, если доказательство проводится не слишком аккуратно). Есть надежда, что временную границу для схемы аппроксимации можно улучшить. Также может оказаться возможным оптимизировать алгоритмы, эффективно вычисляющие точную триангуляцию с минимальным весом для больших случайных наборов точек, таким образом, чтобы они могли эффективно решать более широкий класс задач, а не только задачи с полностью случайными наборами точек. Возможно, этой цели можно достичь при помощи сочетания этого подхода и алгоритмов с фиксированными параметрами, как в работах [2, 4], либо иными способами. Также остается открытым вопрос, можно ли еще больше улучшить субэкспоненциальный точный метод вычисления триангуляции. | ||
== Ссылка на код == | == Ссылка на код == |
правка