определение погрешности, бинарный поиск

[Mayor]

определение погрешности, бинарный поиск

задачка:
в одномерном пространстве на дистанции максимум 1000 парсек, расположено до 100 центров масс удаленных друг от друга не менее чем на 1 парсек, массой от 1 до 1000 единиц каждая
нужно получить координаты точек равновесия с точностью до 10в-9 парсек

если искать бинарным поиском то сколько потребуется циклов на каждый отрезок?

какова в этом плане точность double float?

[Алексей++]

что значит "точки равновесия" ? Точки с нулевой гравитацией ?

а для точности в 9 знаков хватит и float и double

[Dimka]

Алексей1153++, в C float не хватит - там 7-8 знаков.

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

[Алексей++]

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

для скорости же, числа с плавающей точкой вообще не использовать, нужно взять за единицу значение 1*10^-9 парсек и всё вычислять в относительных единицах, используя __int64

[Dimka]

Алексей1153++, на пространстве размерами 1e+3 по 3-м измерениям с точностью 1e-9 будет тупым сканированием 1e+18 вычислений функции потенциала от 100 аргументов. Некошерно. И никакие тут замены float на int не помогут.

[Алексей++]

dimka, я и говорю, если время не поджимает )) Но ведь для полей давно должны быть все такие задачи решены- почему бы не поискать их? На ТОЭ как-то была лекция про расчёт магнитного поля в двигателе, только я оттуда ничего уже не помню...

[Mayor]

Алексей1153++, в C float не хватит - там 7-8 знаков.

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

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

не знаю чем не понравился бинарный поиск - он быстро пишется достаточно быстро реализуется

берем середину отрезка между 2мя рядом расположеными центрами, если в ней гравитация минус то берем середину между серединой и правой гранью иначе левой - достаточно быстро считается, но проблемма в том, что я не могу понять от чего зависит число итераций - что для флоата что для доубла 100 итераций вполне достаточно вроде

[Вад]

А разве локальные экстремумы бинарным поиском ищутся?

[Dimka]

не знаю чем не понравился бинарный поиск - он быстро пишется достаточно быстро реализуется

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

Посмотри на предыдущую задачу. То, что получилось в конце концов, никак не "жадный алгоритм", который ты отстаивал в начале только потому, что он известен и "неэвристичен".

Хотя тут ещё большой вопрос, чем эвристика отличается от неэвристики - если только отсутствием чёткого доказательства, что для данной задачи это действительно подходящее с некоторыми оговорками решение, то для тебя любой известный алгоритм будет эвристическим.

[Dimka]

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

Центры масс влияют друг на друга не попарно, а все вместе одновременно. Локальный минимум гравитации 3-х тел будет лежать внутри треугольника, ими образованного, но никак не на сторонах этого треугольника.

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

[Mayor]

Центры масс влияют друг на друга не попарно, а все вместе одновременно. Локальный минимум гравитации 3-х тел будет лежать внутри треугольника, ими образованного, но никак не на сторонах этого треугольника.

погоди, если брать гравитационное воздействие пропрорциональное массе на квадрат растояния и все объекты расположны на 1й прямой то центры отстуствия воздействия гравитации будут тоже на этой прямой, и более в условии шла речь об одномерном пространсве - так что точки вне этой прямой ваще отсутсвуют