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

Сумма(1/(r(i) - r(0))**2)

Т.к. есть основания полагать что максимумы будут "не очень далеко" от минимума этой ф-ии.

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

RatTail роль границы прямоугольника - ограничить область поиска
это ненамного меняет задачу (-4 условия из ~1004). Но приводит к необходимости дополнительно обследовать границу - как область возможных решений.

RatTail
>я бы отминимизировал ф-ю вида Сумма(1/(r(i) - r(0))**2)
А что мешает?
палиномы (при приравнивании ч.п. 0-ю) получается балшой степени. В аналитике не решается, к линейности не сводятся.

Хотя, возможно можно найти ф-ю поудачнее дифференцируемую, но с той же надеждой оценить области примерного расположения предполагаемых решений. Типа Сумма(Ln((r(i) - r(0))**2) не шибко помогает... но кажется степеня ур-й на экстремум будут чуть помельче Но это только определение точек ~ подходящих. А не сами точки.

White Owl 3) Если проколов больше чем два, то для каждой тройки проколов ищем центр окружности проведеной через эти три прокола. Проверяем есть ли какой-либо прокол внутри этой окружности и находится ли центр окружности внутри многоугольника? Если есть проколы внутри или центр вышел за пределы многоугольника - отбрасываем и переходим к следующей тройке проколов. Иначе проверяем радиус найденой окружности на максимальность найденых расстояний.

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

White Owl 4321можно сразу брать только тройки, в треугольник, натянутый на которые, не попадает ни один прокол. Меньше центров искать.
Нельзя.
"ну и дура" (с не мой).

RatTailДико извиняюсь, но то, что ты предлагаешь, это какая-то чушь.
Ты готов перебрать и просчитать ВСЕ возможные комбинации из трех точек
из множества 1000 точек. Типа, за пару секунд на машине mmx 266MHz.
Я уже молчу о том, что совершенно непонятно куда эти просчеты совать.

Вопрос: зная координаты центра и радиус макс. круга, который можно вписать
в прямоугольник и который (этот круг) не содержит внутри себя дыр, можешь ли
ты сходу сказать, где расположена наша самая безопасная точка? Я - не могу.
ну зачем перебирать ~10**9? Накрой прямоугольник сеткой стартовых точек ~ 10*3. Найди для каждой стартовой 3 ближайшие "ямы" (или 2 ямы и границу, или 2 границы и яму) (это, если есть некий двумерный индекс по ямам, будет быстрее (10**3)*(10**3), врать неохота, но наверное ~ln(10**3)*10**3 ) И опиши на этих тройках окружности (для 2х и границы - полуокружность с центром на границе, для 1 и 2-х границ - окружность с центром в угле). Сравни радиусы. Центр самой большой - примерно "самая безопасная" (одна из множества "самых безопасных")

(скорее всего можно доказать, что количество стартовых точек должно быть сравнимо с N величин, что-то ~ (2-3)*N, для строгого совпадения найденного решения с искомым. Удивлюсь, если гарантия ~N**2)

RatTailПо-моему, все это будет называться "пальцем в небо".
вапшета пальцем не нада.те паче - неббу. Ано не аценит.

если серьезно, то накрыв прямоугольник сеткой чуть больше чем в N квадратиков (со сдвигом на границе в полквадратца), получим заведомо какое то количество квадатов, не содержащих точек. (т.е. надо ~ [sqrt(N)] +1 "ячеек" для квадратной области, для прямоугольной тоже что - то в этом роде, главное, чтобы ячеек разбиения было > N - числа проколов). Очевидно, что точки, лежащие в их центрах, безопаснее точек, лежащих в центрах содержащих проколы ячеек.

если теперь грубо разбить ячейки еще скажем на 3*3, то будем иметь ячейки, которые имеют только пустые смежные, и ячейки, которые имеют непустые смежные. Подобрав разбиение (из оценок мин и макс расстояний), можно будет утверждать что все точки некоторых несмежных (в зависимости от "конфигурации" несмежной области) с проколотыми заведомо безопасней всех точек ячеек имеющих проколотые и (даже) точек ячеек, смежных с проколотыми. Т.е. решения надо искать в таких ячейках "центровых в ряду несмежных". (До сих пор количество вычислений ~N). Вот дальше чуть хуже: гуляя по точкам ячейки мы можем получить массу троек "наиближайших точек", расстояния до которых будут отличаться с точностью до ~1/2 диагонали ячейки. Какую из троек выбрать, и какова сложность алгоритма выборки (в смысле зависимости от N) сказать, не придумав алгоритма, трудно. Тут я действительно соврал, в том смысле, что недостаточно взять только тройки проколов, ближайших к центрам областей. Но если нас интересуют решения с некоторой заданной точностью, то можно будет ограничиться достаточно мелким разбиением (в зависимости от точности, т.е. от 1/2 диагонали "ячеек погрешности", т.е количество ячеек разбиения останется ~N), и выбирать в качестве кандидатов (т.е. троек, служащих для вычисления безопасно точки) только тройки, ближайшие к центрам ячеек, все смежные к которым в некоторой окружности (с радиусом ~ ребра ячеки площадью 1/N от площади прямоугольника) не имеют проколов (решения, лежащие в отй же ячейке будут отличаться с точночтью не больше 1/2 диагонали).

Понятно, что большую часть этого бреда можно даже доказать. Лениво, однако. Опять же, не совсем понятно, интересуют ли нас решения "с некоторой точностью"? Но со сложностью ~N.

(А то ить троек то ~ 10**9, как White Owl , задолбаишься просто перебирать в лоб)

4321 (т.е. надо ~ [sqrt(N)] +1 "ячеек"
читать "делений" вместо "ячеек" (имеется в виду разбиения сторон).

Ленифф, аднако, каюс.

mayton
1) Подойти формально к проблеме нахождения минимума функции многих
переменных. То есть определить однозначно, как должна выглядеть
целевая функция

1 ф-я, в общем случае (т.е. если не заботиться специально о расположении ловушек), будет иметь дикое количество практически равнозначных локальных екстремумов. Генетический алгоритм упадет в первый попавшийся и там успокоится. Если же мутации будут частыми - будет периодически прыгать между ~~равнозначностью.

mayton
2) Считать переборные подходы неверными. Нет гарантии что мы можем
перебрать n-е количество координат в реальные сроки в общей постановке
данной задачи (без конкретных цифр). Методы сеток считать приемлемыми
только в том случае, когда аналитическое решение в принципе невозможно.

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

mayton
3) Использовать типовой набор методов поиска минимума:

- аналитические (методы градиентных спусков и т.п);
- генетические алгоритмы;
- стохастичные алгоритмы;
- комбинация вышеперечисленных.

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

mayton
Давайте договоримся о какой функции идет речь. Дизьюнкция множества конических поверхностей (F) которую я предложил в своем первом посте не имеет пологих участков. Гипотетически возможны одинаковые значения минимумов (у краев поверхности).

прикиньте: проколы у вас приблизительно по равномерной сетке. Все локальные минимумы однозначны.
mayton
Ошибаетесь, коллега. ГА созданы для поиска минимумов именно таких функций.

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

[quot ]
Давайте грызть вместе.. где ваш полином... А?

возьмите частные производные от Summ(1/r(i,0)) по X(0) и Y(0) (в скобках -индексы). Или от Summ(Ln(r(i,0)). Получите свои полиномы >~1000 степени.
mayton
Зря зубоскальничаете. На форум и не такие заходят...
та ничого ж личнохо




ЗЫ. просто идея поиска "на милиметровке с точностью" - раскроить область на "клеточки", примерить, куда влезают заданные "клетчатые трафареты кругов" без проколов (что куда-то влезут с определенностью - даже "доказано"). и в окрестности центров этих областей искать решения стандартным натягиванием окружности на тройку ближайших к центру области проколов. (засада может быть в том случае, если таких троек (при малом смещении точки) будет много - т.е. специальная расстановка проколов почти по окружности - но и [любое] решение тогда будет "хорошим" с хорошей точностью).