|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Alex Semenyaka 2:461/64 24 Nov 2002 18:11:01 To : sl@sl.spb.su Subject : Помогите тупому ... -------------------------------------------------------------------------------- [19 Nov 02 23:27], Stanislav Latishko (2:5030/949) -> All: SL> Чего-то я отупел совсем :( Задачка элементарная, как решать - SL> не соображаю :( Имеется набор 60-мерных векторов A, B, C, ... и вектор Мож, я чего не понимаю, но, кажется, тут примерно так: 1) Ортогонализуем набор A,B,C... (дял удобства лучше, наверное, сразу ортонормировать). Выкидываем линейно зависимые векторы (один фиг от них никакой пользы). 2) Проецируем X на каждый полученный вектор 3) Остаток (обзовем его V) у тебя ортогонален любому вектору в исходном наборе, так что минимизировать его, наверное, уже не получится. Скажем, если |V| = sqrt(V^2), то для ненулевого W, ортогонального V, имеем |V+W| = sqrt(V^2 + 2VW + W^2) = sqrt(V^2 + W^2) > sqrt(V^2) = |V| то есть "домешав" к V любую ненулевую комбинацию векторов своего небора A,B,C... ты добъешься только роста |V|. Дальше из проекции, полученной в пункте 2), получаешь исходные вектора нужным (см. ниже) способом. Сложность - O(n^3), n - число векторов в исходной системе. Если бы исходная система была хотя бы независимой - было бы все однозначно. Увы: SL> считая этой дельты) - от 1 до 3. Hабор А,В,С,итд - "наиболее мерзкий" SL> - в том смысле, что в нем могут быть и "перепендикулярные" пары, а SL> могут быть и такие как C=k3*D+k4*E ... Т.е. единственность решения, SL> вообще говоря, совсем не очевидна... Ок, формализовать можно так: - при неоднозначном наборе решение будет достоверно неединственным. При этом SL> ищем все решения, для которых |delta| меньше любого из слагаемых. Тогда бери ортогонализацию по Левдину, а набор A, B, C... усортируй сначала по уменьшению. Тогда в 0 будут обращаться более короткие вектора. Составь набор исходных векторов, которые не обнулились при этой процедуре. Соответственно, сравнивай потом |V| с самым коротким вектором в этом наборе. IMHO, лучшего не добъешься: уменьшить |V| ты не можешь, векторы ты взял по построению самые длинные. Окажется "шум" больше, чем какой-то из векторов - сорри, таковы были исходные данные. SY, Alex --- IMHO в последней инстанции * Origin: Show must go on... and off. (2:461/64) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/14433de10d29.html, оценка из 5, голосов 10
|