Може да не се изразявам много ясно, понеже не съм математик.

Имате около 20 вектора. Всички са с общо начало, като са разпределни на еднакви ъгли помежду си в една равнина(за 20 вектора - ъгълът между два съседни е 18 градуса). Имат различна големина.

Всеки вектор може да размени местото си с друг вектор, т. е. могат свободно да си разменят местата. По-ясно казано, може да се променя големината, направленията се запазват. Примерно вектор А може да стане с големината на вектор B. Съответно B ще стане с голимата на A. Още по-ясно казано, има един списък със стойности, който може произволно да се помести във фиксираните равномерно разположени направления, създавайки вектори.

При какво разпределине на стойностите в направленията, при какво разположение на векторите тяхната сума ще е с минимална големина? Кога резултатният вектор ще е най-малък?

Ами по принцип надали е възможно в общия случай да се намери минимумът, без да се пресметнат дължините при всичките пермутации... което при брой на векторите от порядъка на 20 е безнадеждно много.

Задачата действително е трудна, но това не пречи да поразсъждаваме над нея. Без ограничение на общността ще смятае, че всички вектори излизат от началото на координатнта система.
Да започнем с два вектора. Ясно е, че те са противно насочени. И при пермутация (ако това можем да наречем пермутация) нищо не се променя.
Да вземем сега три вектора. Единият насочен по абсцисната ос, а другите два завъртени съответно на 120 и -120 градуса от него. С малко пресмятания - най-удобно в комплексна област, намираме за дължината на резултантата корен квадратен от една форма от втора степен на дължините на трите вектора. (За съжаление в този форум нещата не могат да се описват с обичайните ни формули. Но и Нютон е писал без да ги използва.) В нея веднага се вижда, че размяната на местата на вторите два вектора не води до промяна. Но замяната на всеки от вторите два вектора с пръвия (по абсцисната ос) променя дължината на резултантата. И получаваме три (в общия случай) различни числа.
Тъй като е безразлично дали сравняваме положителни числа или техните квадратни корени, да забравим за коренуването.
Ощ тук можем да направим заключението, че поставената задача се свежда до изследването на ръста на една форма от втора степен на n променливи. Стойностите, които взимат тези променливи не са произволни, а са зададени като съвкупност от числа. Във всеки отделен момент променливите взимат различни стойности по такъв начин, че изчерпват съвкупността от зададени стойности.
Не мога да кажа нищо повече. Само мога да дам на постановката във вид, удобен (надявам се) за изследване. Може би средствата на Оптимирането могат да се дадат някакви резултати. Това е област от математиката, твърде различаваща се и отдалечена от областта, в която аз работя.
Надявам се все пак да съм хвърлил някаква светлинка върху въпроса.

Редактирано от MyзMaт на 24.09.08 22:39.

Идеята да се разгледат подробно случаите с малък брой вектори изглежда добра.

Наистина при 2 вектора дължината на тяхната сума не се променя при размяна на местата им. Това е така и при 3 вектора (обратно на това, което казваш) и е очевидно от съображения за симетрия - даже не е нужно да се пишат формули.

Те стават необходими чак при 4 вектора. Тук в общия случай могат да се направят 3 нееквивалентни подреждания (всички останали могат да се получат от тях чрез ротации и отражения) със съответните 3 суми. Лесно се вижда, че подреждането, минимизиращо дължината на сумата, е следното:
Нека векторите имат дължини L1...L4 и L1<=L2<=L3<=L4. Тогава оптималното подреждане е в реда на съседство L1-L3-L2-L4- (двата най-къси са един срещу друг и двата най-дълги също).

За 5 ще се опитам да помисля утре. Задачата е интересна... и май не чак толкова силова, колкото отначало ми се видя.

Да, добре го даваш!

Съдържаниет е скрито
Влезте за да го видите

Съдържаниет е скрито
Влезте за да го видите

За съжаление при 5 и повече вектора работата става дебела. При 5 има 12 съществено различни пермутации. Оптимизацията може да се сведе до пресмятане на 6 полинома на дължините, от знака и стойността на които да се избере оптималната пермутация. Май обаче нищо повече не може да се направи. Тъй че, ако трябва да се смята за голям брой N, май наистина опираме до (N-1)!/2 пермутации. Лоша работа.

Интересно, дали при много голямо N не може да се измисли нещо - поне сносна евристика?

Иначе може да се използва следният грубиянски метод: пускаш един генератор на случайни пермутации и смяташ дължините на сумите, запазвайки най-доброто получено решение. Оставяш програмата да работи, докато ти писне, и вземаш, каквото се е получило. По всяка вероятност няма да е кой знае колко по-лошо от абсолютния оптимум.

Редактирано от Orнeдишaщ на 25.09.08 12:58.

Много интересна задача! Ако не се намери точно решение, аз бих я решил с генетичен алгоритъм. Обхождаме на всички пермутации е практически невъзможно, броят им e 2432902008176640000.

Освен, че е невъзможно, надали е и нужно (доколкото разбрах от клуб "Физика", задачата е съвсем практическа). Очевидно всички възможни дължини на сумарния вектор (при всички възможни пермутации) принадлежат на интервала [търсения_минимум, нещо_от_порядъка_на_сумата_на_дължините). Струва ми се, че няма причини разпределението им в този интервал да е кой знае колко неравномерно (най-лошият случай е много тънка опашка откъм минимума). Това ми се вижда интуитивно ясно (дано не бъркам). Затова алгоритъмът, който предлагам, би трябвало след 10 или 100 или колкото там ти издържат нервите да го чакаш милиона опита да намери решение, почти неотличимо от оптималното. Поне така си мисля.

аве не може ли тая задача да се атакува в полярни координати.
имаме к вектора (Rk, Ak) kкъдето Rk е дължина, Ak е ъгълът.
сумарният вектор е с дължина X.
X^2 = 2*SUM(m=1..k)SUM(n=1..k) [Rm*Rn*cos(Am-An)] - SUM(i=1..k)[Ri^2]

втората част на сумата е фиксирана така че максимизираме първата част.
Аm = m*2*Pi/k, m=1...k
не съм сигурен дали излиза нещо от тука обаче..

Ами така е. Първата част може мъничко да се съкрати, ако преди събирането скъсим всички вектори с дължината на най-късия (това не променя сумата им). Тогава броят на променливите намалява с 1, а броят на членовете на сумата - с N-1 (голям праз, дето се казва!). Оттук нататък обаче нямам идея, как може да се максимизира... освен с груба сила.