?

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 11:27 am
Полный перебор - это медленное решение. Нужно быстрое. Спортивные программисты это умеют, но у нас ни одного не осталось:(
(Ответить) (Развернуть) (Parent) (Thread)

(Удалённый комментарий)

torrio
Link:(Link)
Time:2010-09-30 11:57 am
Так и запишем: к реальной жизни не подготовлен;)
(Ответить) (Parent) (Thread)

(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)

vgramagin
Link:(Link)
Time:2010-09-30 11:52 am
Я не уверен, что это будет быстро в худшем случае, но в среднем при большом наборе точек будет сильно быстрее полного перебора: найти выпуклую оболочку (алгоритм в любой алгоритмической книжке) и перебирать точки уже изнего
(Ответить) (Thread)


torrio
Link:(Link)
Time:2010-09-30 11:56 am
Выпуклая оболочка сама по себе была бы почти-решением исходной задачи:) (поиск треугольника АВС - это подзадача другой задачи). Правда, сложным в применении - ограничивающих плоскостей может быть сколь угодно много - например в случае, когда все точки изначального множества расположены на его выпуклой оболочке:)))

Пока что я склоняюсь вообще к отказу от геометрии и переходу к теории вероятностей и мат. статистике...
(Ответить) (Parent) (Thread)


gamzov
Link:(Link)
Time:2010-09-30 12:04 pm
Рисуешь кубик, рассекаешь его пополам на две одинаковых трапеции, получаешь равносторонний треугольник максимальной площади. Чтобы не напрягать тебя, то вот пример решения
0,0,0
255,255,0
255,0,255

ЗЫ: Вроде в школе я уроки прогуливал, а геометрию не помнишь ты :)
(Ответить) (Thread)


gamzov
Link:(Link)
Time:2010-09-30 12:06 pm
Перебор, ога:) Математика рулит!
(Ответить) (Развернуть) (Parent) (Thread)


rioman
Link:(Link)
Time:2010-09-30 01:06 pm
А про природу заданного множества точек можно что-то сказать?
(Ответить) (Thread)


torrio
Link:(Link)
Time:2010-09-30 01:07 pm
Можно. Они желтые. Собственно, изначально я хотел назвать эту задачу задачей про Желтого Ублюдка, но потом постеснялся:)
(Ответить) (Развернуть) (Parent) (Thread)


amironenko
Link:(Link)
Time:2010-09-30 02:27 pm
Ну то, что искомые точки лежат на выпуклой оболочке - вроде не так сложно показать. Беда в том, что это мало помогает :) Еще подумаю

Хотя перебор тут и так N^3, надо меньше?
(Ответить) (Thread)


torrio
Link:(Link)
Time:2010-09-30 06:12 pm
Ну вообще я, конечно, и эн куб написал бы, но это неприлично:) Хочется, чтобы в коде были красивые решения, а не глупый брутфорс.
(Ответить) (Parent) (Thread)

usenk0
Link:(Link)
Time:2010-09-30 02:44 pm
Почитал комментарии. Вера в то что РТФ чемпион не уменьшается, но становится как-то не себе . . . :-)
(Ответить) (Thread)


torrio
Link:(Link)
Time:2010-09-30 06:12 pm
РТФ, кстати, чемпион:) Респект факультету!
(Ответить) (Развернуть) (Parent) (Thread)


catflat
Subject:\pulkin
Link:(Link)
Time:2010-09-30 03:19 pm
Построй баунд-бокс исходного множества. Выкинь все внутренние точки, перебери все тройки в том что осталось. Сердито, но дешево.
И кстати, ты не впадаешь ли в грех преждевременной оптимизации?
(Ответить) (Thread)


torrio
Subject:Re: \pulkin
Link:(Link)
Time:2010-09-30 06:29 pm
Впадаю каждодневно, грешен:)
(Ответить) (Parent) (Thread)


vasbur
Link:(Link)
Time:2010-09-30 03:29 pm
А динамисечкие алгоритмы не проканают?
Берем любой треугольник, потом меняем одну из вершин на другю точку. И так до тех пор, пока получем треугоьник, площадь которого нельзя увеличить заменой одной точки.
(Ответить) (Thread)


vasbur
Link:(Link)
Time:2010-09-30 04:45 pm
Я тут подумал - алгоритм не проканает :(
Два треугольника в форме "Звезды Давида" являются контпримером к алгоритму.
(Ответить) (Развернуть) (Parent) (Thread)


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)


codenamed
Link:(Link)
Time:2010-09-30 06:53 pm
Подозреваю, что вы тут имеете в виду не выпуклую оболочку, а составленный из треугольников ограничивающий множество точек полигон с вершинами в точках самого множества :)

Я бы тоже так решал: построил бы mesh, пронумеровал бы вершины и перебирал бы тройки. Но хорошо бы иметь оценку количества точек и примерно представлять, как они угрожают распределяться.

А из эвристик - построил бы bounding rectangle, выбрал бы точку, ближайшую к границе (или несколько). Для каждой такой точки находил бы максимально удаленную (или несколько, скажем, 5) и проходился бы по разу по всем остальным, вычисляя площади. Мне кажется, было бы что-то близкое к правде на выходе. Весь массив перебираем три раза: сортируем (ищем минимум расстояния), для "самой крайней" ищем самую дальню, и для каждой из оставшихся вычисляем площадь :)
(Ответить) (Thread)


torrio
Link:(Link)
Time:2010-09-30 06:59 pm
Ага, такую эвристику уже предложил ze_oboltus... Хорошая идея, мне нравится:-)
(Ответить) (Развернуть) (Parent) (Thread)

serg14
Link:(Link)
Time:2010-10-01 01:46 am
"Farthest segments and extremal triangles spanned by points in R^3," Information Processing Letters. Volume 109, Issue 20, 30 September 2009, Pages 1167-1171

Снова синтез ... велосипедов.

(Ответить) (Thread)


amironenko
Link:(Link)
Time:2010-10-01 05:07 am
Given a set S of n points we consider finding the minimum and maximum area triangles spanned by S. We prove that the minimum area triangle spanned by S can be found in O(n^(2.4) logO(1)n) time and space, and the maximum area triangle spanned by S can be found in O(h^2.4 logO(1)h+nlogn) time and O(h^2.4 logO(1)h+n) space, where h is the number of vertices of the convex hull of S (h=n in the worst case).

Что не так уж лучше перебора за n^3 :) Что тут думать - прыгать надо :)
(Ответить) (Parent) (Thread)


codenamed
Link:(Link)
Time:2010-10-01 03:48 pm
http://lenta.ru/news/2010/10/01/avdey/

Точки... треугольники... уж не радикальным ли экспрессионизмом вы там занимаетесь?! *смотрит подозрительно*
(Ответить) (Thread)


torrio
Link:(Link)
Time:2010-10-01 03:51 pm
Чорт! Придется ТЕПЕРЬ тебя убить:)
(Ответить) (Развернуть) (Parent) (Thread)

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