?

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


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


torrio
Link:(Link)
Time:2010-09-30 12:08 pm
Это решение какой-то другой задачи:) Мне нужно построить треугольник АВС из точек, входящих в исходное множество, а не во всем пространстве RGB...
(Ответить) (Parent) (Thread)


gamzov
Link:(Link)
Time:2010-09-30 12:15 pm
Блин, это еще проще. По координатам площадь посчитать - задача для 2го класса. Смешно однако :)
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2010-09-30 12:17 pm
Да-да, формула Герона, векторное произведение - это всё понятно. Вопрос - площадь чего считать будем? Точек много. цэ из эн по три?
(Ответить) (Parent) (Thread)


gamzov
Link:(Link)
Time:2010-09-30 12:32 pm
Вариант:
1. Строим первый треугольник
2. Добавим одну точку,попытаемся подменить каждую из существующих. Если в результате площадь увеличилась, то получаем новую тройку точек.
3. И так до конца, увеличивая на каждом шаге площадь

Корректность такого подхода непонятна пока что
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2010-09-30 12:35 pm
1. это почти полный перебор, 2. можно придумать такое множество точек, в котором такой алгоритм даст результат не менее чем в два раза хуже, чем точное решение:(
(Ответить) (Parent) (Thread)


gamzov
Link:(Link)
Time:2010-09-30 12:38 pm
Это не полный перебор. Сложность N. Кинь, пожалуйста, в почту пример точек, где такой алгоритм не сработает.
(Ответить) (Parent) (Thread)


gamzov
Link:(Link)
Time:2010-09-30 12:41 pm
Ну да, можно придумать. Но если сделать несколько проходов, то, увеличив сложность, наверное добьемся результата.
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2010-09-30 12:52 pm
Уфф... Рад, что не пришлось писать пример:) Понятно, что он существует, и что построить его не так сложно.

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


gamzov
Link:(Link)
Time:2010-09-30 12:57 pm
Можно попытаться прооптимизировать старт. Важен начальный треугольник. Можно взять на кубе три максимально удаленные точки, поискать к каждой точки ближайшую и взять их за основу. Сложность в худшем случае, наверное, не изменится, но в среднем улучшится.
(Ответить) (Parent) (Thread)

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