?

Log in

No account? Create an account

[icon] Задача из реальной жизни - Lorem Ipsum igitur, juvenes dum sumus — ЖЖ
View:Свежие записи.
View:Архив.
View:Друзья.
View:Личная информация.
View:Website (Мой сайт).

Tags:,
Security:
Subject:Задача из реальной жизни
Time:05:13 pm
Есть набор точек в пространстве RGB (подмножество декартова с ограничением на каждую координату: 0<=x<=255, x-целое).
Нужно найти три наиболее удаленные друг от друга точки A, B, C. Критерий удаленности - максимальная площадь треугольника ABC.

Есть идеи как написать очень быстрое и близкое к оптимальному решение? Нужна помощь, в общем.
comments: Оставить комментарий Previous Entry Поделиться Next Entry


torrio
Link:(Link)
Time:2010-09-30 06:18 pm
Ограничения на количество точек, конечно, есть... И всё не так плохо: слава богу, поставленная задача является только первым, подготовительным шагом другого алгоритма, и не нужно будет решать её 25 раз в секунду.

Генетический алгоритм здесь, как мне кажется, не подошел бы. Может быть Юра Окуловский меня и зачморит прочитав следующие строки, но в моём понимании мутация одного гена при условии, что всего их в геноме 3 - это катаклизм и ненаучно: метод будет сходиться медленнее, чем полный перебор:)
(Ответить) (Parent) (Thread)


a_quantum
Link:(Link)
Time:2010-10-02 01:36 am
Да, для 3 параметров гонять ГА тупо. При малом числе параметров simulated annealing работает лучше, чем ГА. При большом - наоборот. :)
(Ответить) (Parent) (Thread)

[icon] Задача из реальной жизни - Lorem Ipsum igitur, juvenes dum sumus — ЖЖ
View:Свежие записи.
View:Архив.
View:Друзья.
View:Личная информация.
View:Website (Мой сайт).