Не знаю как назвать
Добавлено: 19 ноя 2009, 00:20
Hi, All.
К сожалению, я плохой математик Задачу наверняка кто-то когда-то решал, но я не представляю где искать решение... Если кто знает - ткните носом, плиз.
Единичная окружность, на ней непредсказуемым образом расположены N (от 3 до 10**4) точек (заданы массивом углов), задающие соответственно N векторов V. Необходимо найти массив коэффициентов при векторах K, таких чтобы сумма Ki*Vi по i от 1 до N была бы =0 . (С заранее заданной точностью, поскольку решаем в цифре)
Понятно, что задача либо не имеет решения (если все точки поместились на одной полуокружности), либо имеет их бесконечно много.
Не интересуют решения, где хоть один Ki=0 - ибо это эквивалентно уменьшению N .
Предпочтительно, чтобы соседние коэффициенты были "близки". Это пожелание, а не требование - решение, где "соседние" Ki отличаются на 10% - оно "лучше" чем то решение, где они отличаются в 100 раз. Ну и "для порядку" пусть 0<=Ki<=1 ;
Я набросал довольно тупой алгоритм: сначала присвоили всем Ki=1, подсчитали отдельно сумму Sin и Cos, затем с "выпирающей стороны" слегка уменьшили коэффициенты, посмотрели удовлетворяет ли нас результат по точности, if not - повторить. Принципаиально - работает, но медленно - ошибка уменьшается в 2-3 раза за цикл, крутить его 10-20 раз - долговато получается...
Проблема -
а) в большом диапазоне N. Понятно, что при N=3 можно и аналитически решать, но при 1000 это неоправданный расход ресурсов, как мне кажется.
б) в характеристике распределения этих точек - оно непредсказуемо, но НЕ случайно, т.е. даже при максимальных N нельзя расчитывать на какую-либо равномерность. Могут распределиться равномерно, а могут - две на одной стороне и все остальные напротив.
А алгоритм должен работать при любом из таких крайних вариантов.
Подайте идеек, кто сколько может
К сожалению, я плохой математик Задачу наверняка кто-то когда-то решал, но я не представляю где искать решение... Если кто знает - ткните носом, плиз.
Единичная окружность, на ней непредсказуемым образом расположены N (от 3 до 10**4) точек (заданы массивом углов), задающие соответственно N векторов V. Необходимо найти массив коэффициентов при векторах K, таких чтобы сумма Ki*Vi по i от 1 до N была бы =0 . (С заранее заданной точностью, поскольку решаем в цифре)
Понятно, что задача либо не имеет решения (если все точки поместились на одной полуокружности), либо имеет их бесконечно много.
Не интересуют решения, где хоть один Ki=0 - ибо это эквивалентно уменьшению N .
Предпочтительно, чтобы соседние коэффициенты были "близки". Это пожелание, а не требование - решение, где "соседние" Ki отличаются на 10% - оно "лучше" чем то решение, где они отличаются в 100 раз. Ну и "для порядку" пусть 0<=Ki<=1 ;
Я набросал довольно тупой алгоритм: сначала присвоили всем Ki=1, подсчитали отдельно сумму Sin и Cos, затем с "выпирающей стороны" слегка уменьшили коэффициенты, посмотрели удовлетворяет ли нас результат по точности, if not - повторить. Принципаиально - работает, но медленно - ошибка уменьшается в 2-3 раза за цикл, крутить его 10-20 раз - долговато получается...
Проблема -
а) в большом диапазоне N. Понятно, что при N=3 можно и аналитически решать, но при 1000 это неоправданный расход ресурсов, как мне кажется.
б) в характеристике распределения этих точек - оно непредсказуемо, но НЕ случайно, т.е. даже при максимальных N нельзя расчитывать на какую-либо равномерность. Могут распределиться равномерно, а могут - две на одной стороне и все остальные напротив.
А алгоритм должен работать при любом из таких крайних вариантов.
Подайте идеек, кто сколько может