|
Страници по тази тема: 1 | 2 | 3 | (покажи всички)
|
Виж какво, не искам случайни търсения. Аз примерно направих в моята програма пълна пермутация на елементите и изследване на всяко възможно състояние, като накрая се намира най-доброто разположение. Само че, това работи до примерно 12 елемента, след което компютърът започва сериозно да се бави. Въпреки това, анализирайки резултатите, стигнах до определени зависимости в подреждането. Само че, аз търся математически доказано решение на задачата, чрез което да направя правилна методика за решение.
| |
|
Да, разбирам, че търсиш точно решение. Но това, което аз казвам е, че точно решение няма, защото проблема изглежда да е NP complete, а при тях не съществтува решение с което да е полиномна сложност, вместо това сложността е експоненциална и за решаването на този вид задачи се използват различни евристични методи, като например случайно търсене.
В момента още не съм намерил строго доказателство, че това е NP complete проблем, но сега тук ще представя един доста интуитивен подход с който ще сведа този проблем до Проблема на Търговския Пътник, за който вече знаем, че е NP complete:
Да приемем, че всеки вектор е град през който трябва да мине търговския пътникм а пък позицията на всеки вектор е реда в който търговския пътник ще обикаля градовете. Последователната сума от векторите нека бъде сумата от последователните разстояния между градовете. Задачата ни е да минимизиране тази сума.
Както виждате сведох проблема с подреждането на оптимално положение на векторите към проблема на редуването на градовете при търговския пътник. Доказателството ми далече не е строго издържано и мисля, че строгото доказателство ще бъде нещо ново и интересно в NP областта, защото търсих и не намерих точно този проблем в списъка на NP complete, проблемите:
| |
|
Може и да си прав, ама може и да не си. Ще почакам още за други мнения.
| |
|
Да опитаме да намерим кординатите на сумата. Поправете ме, ако бъркам (доста е вероятно).
1) Да приемем, че имаме декартова координатна система, такава, че началото й съвпада с общата точка на векторите, а абсцисната ос Оx - с някой от векторите.
2) Да номерираме векторите по посока обратна на часовниковата стрелка.
3) Нека векторите са 20 на брой.
Тогава имаме вектори съответно с координати
r1(x1,y1)
r2(x2,y2)
r3(x3,y3)
...
...
r19(x19,y19)
r20(x20,y20)
Е, пита се в задачата какви са координатите на вектора
s=r1+r2+r3+...+r19+r20
Вярно ли е, че
s(x1+x2+...+x20,y1+y2+...+y20)
?
Примерно доказателство
а) събираме първите два вектора
б) към резултата от точка а) добавяме третия
в) към резултата от точка б) добавяме четвъртия вектор
и така нанатък.
Редактирано от ДъpвeнФилocoф на 03.06.09 21:10.
| |
Тема
|
Re: Задача с вектори
[re: Пaньo Дoнeв]
|
|
Автор | Heдeв (Нерегистриран) |
Публикувано | 03.06.09 21:36 |
|
Паньо, и аз мисля че в общия случай задачата е np-сложна, като под общ случай разбирам да са ти зададени посоките, а ти да трябва да разпределиш дължините. Обаче в случая с равномерното разпределение се чуда няма ли как да се вкара трансформация на Фурие, примерно. Непрекъснатия случай също мож'да се окаже интересен.
| |
|
Всичко това е вярно, но не това се пита в задачата. Предполагам, че всеки тук знае как се събират вектори в декартова координатна система.
| |
|
... предното ми мнение е вярно и не съм допуснал грешка някъде по пътя, мисля че съм стигнал до решение на задачата.
Ако знаем координатите на сумата, можем да намерим дължината й. Питаш как да разположим векторите по направленията така, че да получим минимална дължина на сумата. Отговор - все едно, дължината на сумата не зависи от разположението на векторите по направленията.
| |
|
Явно мястото ти не е в този клуб. Само ми загуби времето да те чета!
| |
|
ще си го запазя като ценен пример срещу рационалистите вярващи в Силата на Разума
NE SUTOR ULTRA CREPIDAM
| |
|
Ти кажи прав ли съм или греша, не ми определяй дали съм за тоя клуб или не. И с доказателство, моля, все пак става дума за математика.
| |
|
Страници по тази тема: 1 | 2 | 3 | (покажи всички)
|
|
|