IPB
Новое на форумах
Подписка на тему | Сообщить другу | Версия для печати
4 Страницы  1 2 3 > »  
Reply to this topic Start new topic Start Poll 

Древовидный · [ Стандартный ] · Линейный

> Нужен совет по модели, Ночь в тоскливом октябре

Jolaf
post Root
Jul 21 2011, 07:33 PM
Отправлено #1

[информация]
Нужно сделать модельку а ля Игра из "Ночи в тоскливом октябре" Желязны.

Задачка формулируется так. На карте полигона (и на самом полигоне) есть N точек (порядка 5-30). Нужно придумать алгоритм, позволяющий раcчитать местонахождение на карте (и на полигоне) точки "центра".

Ключевые требования к алгоритму следующие:
- Для любого заданного расположения точек решение должно существовать и быть единственным.
- Решение должно быть устойчиво к малым отклонениям положения исходных точек. То есть, если исходные точки смещаются незначительно, или при расчёте допускаются незначительные геометрические или численные ошибки, отклонение полученного решения от правильного тоже должно быть незначительным.
- Расчёт решения по алгоритму с использованием карты должен быть выполним человеком без помощи компьютера за время от десятков минут до нескольких часов.

Крайне желательные свойства алгоритма:
- Алгоритм должен быть геометрическим. Расчёт должен проводиться на карте с помощью карандаша и линейки без делений, может быть циркуля.
- Алгоритм должен быть НЕ устойчив к добавлению новых исходных точек или удалению с карты существующих исходных точек. То есть, при добавлении новой точки в любое место или удалении любой из существующих, решение должно меняться существенно.
- Перерасчёт при удалении или добавлении новых точек должен занимать существенное время.
- Расчёт должен быть выполним с помощью компьютерной программы (с заранее вбитыми исходными данными) не более чем за несколько минут.

Желательные свойства алгоритма:
- Расчёт должен быть хотя бы теоретически выполним на полигоне без помощи карты при хорошем глазомере и пространственном воображении за время от часов до десятков часов.

Замеченные проблемы:
- Учитывая потенциально большое количество исходных точек, напрашивается идея использовать рекурсию, то есть, посчитать по N исходных точек M < N новых точек (центры каких-нибудь отрезков или треугольников и т. п.), после чего повторить расчёт для этих M и так далее, пока их не останется 2 или 3 и ответ не станет очевидным. К сожалению, все алгоритмы, которые я придумал и запрограммировал к данному моменту, при N > 6 дают не уменьшение, а увеличение числа точек с каждой итерацией.

В общем, нужны свежие оригинальные идеи, сколь угодно безумные. smile.gif


Сообщение отредактировано: Jolaf, Jul 21 2011, 07:36 PM
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Юра
post  Reply to Jolaf
Jul 21 2011, 09:02 PM
Отправлено #2
[информация]
Я правильно понял, что все простые геометрические алгоритмы тебя не устраивают именно в силу того, что простые алгоритмы достаточно устойчивы к добавлению новых точек?
Т.е. если игрок найдет 29 точек из 30, то его рассчетный "центр" будет очень близко к "центру" карты, построенной по всем 30 точкам? А по сути модели, он конечно должен очень сильно ошибиться в такой ситуации.

Если это основная причина, по которой тебя не устраивают геометрические алгоритмы, то можно сделать несколько видов точек. Например:
точки типа А имеют "вес", по которому находится "центр" полигона.
точки типа Б "веса" не имеют; зато они "выключают" все точки типа А на опредленном расстоянии от себя. Т.е. точка А не имеет веса, если в радиусе R от нее есть точка типа Б.
В такой ситуации единственная пропущенная точка Б, которая выключает сразу несколько точек типа А, значительно влияет на итоговый результат.

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

Это конечно если я правильно понял всю совокупность причин, по которой тебя не устраивает простая геометрическая модель, в которой нужно найти "центр тяжести" точек на полигоне.

Сообщение отредактировано: elraen, Jul 21 2011, 09:02 PM
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
pasha
post  Reply to Jolaf
Jul 22 2011, 06:55 AM
Отправлено #3
[информация]
QUOTE(Jolaf @ Jul 21 2011, 10:33 PM)
- Алгоритм должен быть НЕ устойчив к добавлению новых исходных точек или удалению с карты существующих исходных точек. То есть, при добавлении новой точки в любое место или удалении любой из существующих, решение должно меняться существенно.

Общего алгоритма не предложу, но вот именно это свойство я бы моделировал заданием двух разных алгоритмов - для четного и нечетного числа точек.
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Jolaf
post  Reply to pasha
Jul 22 2011, 07:45 AM
Отправлено #4

[информация]
QUOTE(pasha @ Jul 22 2011, 09:55 AM)
Общего алгоритма не предложу, но вот именно это свойство я бы моделировал заданием двух разных алгоритмов - для четного и нечетного числа точек.

О, крутая мысль, спасибо!

User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Фёдор
post  Reply to Jolaf
Jul 22 2011, 08:05 AM
Отправлено #5

[информация]
Ещё к предложению Юры можно добавить, что вес точки может быть как положительным, так и отрицательным.
А четность количества точек, например, меняет все знаки для определённого набора точек.


--------------------
user posted image
На людей я полагаться не хочу, они часто все портят. © Ритор
У меня есть свое видение клуба, и я не собираюсь менять его просто от того, что мне что-то сказал какой-то лысый мужик в очках! © Даша Тайрен
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Jolaf
Jul 22 2011, 08:24 AM
Отправлено #6

[информация]
QUOTE(elraen @ Jul 22 2011, 12:02 AM)
Я правильно понял, что все простые геометрические алгоритмы тебя не  устраивают именно в силу того, что простые алгоритмы достаточно устойчивы к добавлению новых точек?

Да, это одна из причин.

Вторая - большое количество операций и накапливающаяся ошибка при ручном расчёте.

QUOTE(elraen @ Jul 22 2011, 12:02 AM)
можно сделать несколько видов точек

Идея крутая, спасибо, подумаю её. Пока вижу две проблемы.

Во-первых, по условию задачи (сейчас допишу) выключать точки из расчёта нельзя, каждая должна влиять на результат.

Во-вторых:

QUOTE(elraen @ Jul 22 2011, 12:02 AM)
Это конечно если я правильно понял всю совокупность причин, по которой тебя не устраивает простая геометрическая модель, в которой нужно найти "центр тяжести" точек на полигоне.

Найти "центр тяжести" тоже непросто без компьютера, тем более геометрически.
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Jolaf
Jul 22 2011, 08:26 AM
Отправлено #7

[информация]
QUOTE(lotren @ Jul 22 2011, 11:05 AM)
Ещё к предложению Юры можно добавить, что вес точки может быть как положительным, так и отрицательным.
А четность количества точек, например, меняет все знаки для определённого набора точек.

Ага, тоже круто.

Вопрос в том, что дальше делать с этими весами? На компе-то, понятно, можно посчитать физический центр тяжести и всё. А на бумаге, карандашом и линейкой?
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Юра
post  Reply to Jolaf
Jul 22 2011, 08:39 AM
Отправлено #8
[информация]
Ну про выключение точек - это была просто одна из мыслей, как можно реализовать идею нескольких видов точек. Основная идея - это именно несколько видов точек.

Центр тяжести геометрически как раз ищется не очень сложно, но при большом количестве точек ошибка конечно будет накапливаться очень заметно.
Но как раз разными видами точек по идее можно бороться с накапливающейся ошибкой - т.к. алгоритм фактически бьется на несколько частей, в каждой из которых точек меньше.
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Юра
post  Reply to Jolaf
Jul 22 2011, 08:40 AM
Отправлено #9
[информация]
С циркулем центр тяжести ищется легко. Только с линейкой - тоже, но точность будет существенно ниже.

Сообщение отредактировано: elraen, Jul 22 2011, 08:40 AM
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Jolaf
Jul 22 2011, 08:41 AM
Отправлено #10

[информация]
QUOTE(elraen @ Jul 22 2011, 11:39 AM)
Центр тяжести геометрически как раз ищется не очень сложно

Например как? (вдруг я не вижу чего-то очевидного)
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Юра
post  Reply to Jolaf
Jul 22 2011, 08:51 AM
Отправлено #11
[информация]
При равных весах точек:
Центр тяжести отрезка - его середина.
Центр тяжести треугольника - пересечение медиан.

Это значит, если количество точек - степень двойки, тройки или их комбинации (2*3^2 например) решаются вообще не особенно задумываясь.
При другом количестве точек тоже, в общем, ищется. В конце концов, всегда можно лишние точки (больше, чем ближайшая комбинация степеней двойки и тройки) учитывать, находя центр тяжести отрезка с центром тяжести между всей остальной системой и конкретной лишней точкой - просто у центра тяжести всей остальной системы считать как точку с весом всех тех точек, чьим центром тяжести она является.

Короче, с циркулем, линейкой и ровной поверхностью за 20 минут можно посчитать центр тяжести любого разумного количества (штук до 50 точно) точек.

Сообщение отредактировано: elraen, Jul 22 2011, 08:53 AM
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Jolaf
Jul 22 2011, 08:58 AM
Отправлено #12

[информация]
QUOTE(elraen @ Jul 22 2011, 11:51 AM)
можно лишние точки (больше, чем ближайшая комбинация степеней двойки и тройки) учитывать, находя центр тяжести отрезка с центром тяжести между всей остальной системой и конкретной лишней точкой

Окей, вот у тебя есть центр тяжести остальной системы с весом, скажем, 28. И есть ещё одна точка, с весом, очевидно, 1. Как будем искать центр тяжести?

Сообщение отредактировано: Jolaf, Jul 22 2011, 08:58 AM
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Юра
post  Reply to Jolaf
Jul 22 2011, 09:03 AM
Отправлено #13
[информация]
Делим отрезок на 29 равных частей и берем ближайшую часть к тяжелой точке.
Да, на 29 частей циркулем и линейкой делить невесело, но это нужно сделать один раз. Кроме того, тебе нужны не все 29 одинаковых отрезков, а только первый с нужной стороны, так что все вообще не так плохо.

Более того, если точек 30, то ты сначала ищешь центр тяжести двух оставшихся точек, а потому отрезок между ним и цетром масс остальной системы делится уже не на 29 частей, а на 15, что уже лучше.

Сообщение отредактировано: elraen, Jul 22 2011, 09:04 AM
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Фёдор
post Root
Jul 22 2011, 09:20 AM
Отправлено #14

[информация]
на бумаге это делается элементарно например, на миллиметровке -
ставим точки с весами по координатам.
по каждой координате берём сумму (координата точки * вес точки)
делим на общее кол-во точек
получаем координаты центра масс

на обычной бумаге - сложнее, но тоже можно упростить, введя координаты(просто нарисовав оси)

без бумаги/ручки, а в уме - тяжело, да.


--------------------
user posted image
На людей я полагаться не хочу, они часто все портят. © Ритор
У меня есть свое видение клуба, и я не собираюсь менять его просто от того, что мне что-то сказал какой-то лысый мужик в очках! © Даша Тайрен
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Юра
Jul 22 2011, 09:26 AM
Отправлено #15
[информация]
Как я понял, Йолаф хочет делать это прямо на карте, так что миллиметровка вроде не очень подходит. Хотя, в общем, тоже можно перенести с карты на миллиметровку.
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Фёдор
Jul 22 2011, 09:39 AM
Отправлено #16

[информация]
для примерного подсчёта достаточно срисовать путём налоожения с карты на клетчатую (5 мм) бумагу и проделать то же самое. Точность - +- 5 мм на карте, что конечно немало, но зависит от масштаба.


--------------------
user posted image
На людей я полагаться не хочу, они часто все портят. © Ритор
У меня есть свое видение клуба, и я не собираюсь менять его просто от того, что мне что-то сказал какой-то лысый мужик в очках! © Даша Тайрен
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Jolaf
Jul 22 2011, 09:46 AM
Отправлено #17

[информация]
QUOTE(elraen @ Jul 22 2011, 12:03 PM)
Да, на 29 частей циркулем и линейкой делить невесело

То-то и оно. Очень громоздко получается, и занудно. Хочется элегантного решения. Грубо говоря, больше думать и меньше считать.

Я вот сейчас думаю в сторону алгоритма, в котором нужно правильно (анализ может занять приличное время, но требует смотреть и измерять, а не рисовать) выбрать первую точку, потом вторую, как первую из оставшихся, и из этой последовательности потом как-то высчитывать центр...
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Askold
post  Reply to Jolaf
Jul 22 2011, 11:05 AM
Отправлено #18

[информация]
Может быть, скажу бред, но тем не менее, такая идея:

1. Найти самую внешнюю и самую внутреннюю ломанную фигуру, т.е. внешний и внутренний "круги силы"

2. Найти их центры тяжестей.

3. Искомый центр системы находится на прямой, соединяющей центры тяжестей внутренней и внешней фигур, его расположение зависит от количества внутренних фигур - "кругов силы" и количества точек во внешней и внутренней.
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Флоран
Jul 22 2011, 11:11 AM
Отправлено #19

[информация]
Идея прикольная -- вся сложность в том, как эти круги провести однозначно.
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post
Юра
post  Reply to Jolaf
Jul 22 2011, 11:18 AM
Отправлено #20
[информация]
С учетом того, что такое занудство - разовое, это не так уж и плохо.

QUOTE
Я вот сейчас думаю в сторону алгоритма, в котором нужно правильно (анализ может занять приличное время, но требует смотреть и измерять, а не рисовать) выбрать первую точку, потом вторую, как первую из оставшихся, и из этой последовательности потом как-то высчитывать центр...


Это довольно хорошая мысль.

Тебе это для "Ночи в тоскливом октябре" или ты это просто в качестве примера привел?

Есть вот какие идеи, которые могут подойти, а могут и не подойти:
1. Учитывать возраст точки. Скажем, нужно идти от старых точек к новым, или у старых точек могут быть какие-то дополнительные свойства (другой тип точек для самых старых точек?).
2. Добавить к точкам связи. Скажем, у каждой точки есть направленные связи. Дальше считаем направленные связи как векторную сумму и получаем финальную точку. А как точку начала отсчета, от которой будет откладываться векторная сумма, можно взять центр тяжести точек другого типа, которых будет немного.

Такие дополнительные свойства точек могут добавить интереса игре, так как нужно не только локализовать точки, но и проанализировать разное. Например данные о том, как строятся связи между точками, могут быть размазаны по командам (открывающих и закрывающих, если мы все еще о НвТО), что потребует какой-то дополнительной кооперации, нельзя будет в одиночку установить все доп. данные о точках.
User is offline
Profile Card PM
   Go to the top of the page
+Quote Post

Fast Reply Reply to this topic Topic Options Start new topic 
1 чел. читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:

 

Упрощённая версия Сейчас: 28th March 2024 - 02:48 PM