2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задачка на оптимизацию
Сообщение16.11.2006, 11:52 
Такая вот задачка на оптимизацию.
Есть множество наборов векторов $N_i = \{{V_1^i ..  V_{n_i}^i}, P^i  \} $ , размер вектора 10^5 примерно, векторов в наборе до ста, наборов несколько тысяч.
надо найти вектор X для которого $\forall\ j  ({X P^i > X V_j^i}) $ для как можо большего числа наборов. Есть алгоритм, который решит за разумное время без суперпуперкомпьютера?

 
 
 
 
Сообщение16.11.2006, 13:13 
Аватара пользователя
Для начала для каждого набора векторов $N_i$ рассмотрите конус
$$\{ X : X (P^i - V_j^i) > 0,\ j=1,\dots,n_i\}$$
и найдите его базис.

 
 
 
 
Сообщение16.11.2006, 15:32 
maxal писал(а):
Для начала для каждого набора векторов $N_i$ рассмотрите конус
$$\{ X : X (P^i - V_j^i) > 0,\ j=1,\dots,n_i\}$$
и найдите его базис.


Векторы $ V_j^i $ скорее всего независимы, и $\{ P^i - V_j^i \}$ сами базис конуса.

А в общем мне кажется, что тут подошло бы что то вроде GA.
Кто скажет, GA для поиска в пространстве такого размера ($ 10^5  $) вообще применяют?
Примеры в сети смешные какие - то, вроде функцию сложения по модулю 2 найти.

 
 
 
 
Сообщение16.11.2006, 19:31 
Аватара пользователя
:evil:
alexvs писал(а):
Кто скажет, GA для поиска в пространстве такого размера ($ 10^5 $) вообще применяют?

Еще как применяются.

Примеры в сети — это смешно. Это примеры, а не отчет о применении.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group