?

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


queueman_as
Link:(Link)
Time:2010-09-30 04:46 pm
Походу тебе нужно во миллионы раз быстрее перебора, ого. Если искать точные решения, то даже O(n) - это уже 256^3, т. е. несколько миллионов. Как при таких условиях написать хоть что-то "быстрое" (десятые доли секунды) - я не представляю. Ты уверен, что нет более жестких ограничений на количество точек?

Скорее всего придется уходить в приближенные решения - оставить только точки, которые ближе к "границе", например, далеко от центра масс. А там взять какое-то решение и пытаться его итерациями улучшать - локальными оптимизациями, а лучше отжигом (придется погуглить). Чевдарь сказал, что может неплохо работать генетический алгоритм, но ты в них явно разбираешься лучше меня.
(Ответить) (Thread)


queueman_as
Link:(Link)
Time:2010-09-30 04:55 pm
О, уже привели мощный пример со звездой Давида - все и правда плохо. Либо разрешить изменять за итерацию более одной вершины, либо паниковать, либо несколько раз запускать алгоритм, случайно выбирая стартовое решение. Эх :(
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2010-09-30 06:06 pm
Что же делать:-( Неужели мировой разум пасует, и опять решение придется придумывать и писать самому?..
(Ответить) (Parent) (Thread)


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 (Мой сайт).