Оптимизация расстояния сетки, содержащей заданный набор точек

Question

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

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

Позвольте мне привести пример:
Скажите, что я работаю с закрытым интервалом [1,10]

xmin=1  
xmax=10 

Скажем, у меня есть 3 начальные точки: xmin, 5 и xmax

num_ivc=3  
known(num_ivc)=[xmin,5,xmax] //my arrays start at 1. Assume "known" starts sorted

Я храню свои точки сетки / сетки в массиве, называемом скоординированным.Скажем, я хочу всего 10 баллов в моей сетке / сетке.

N=10  
coord(10)  

Помните, все это произвольно - за исключением имен переменных, конечно.Алгоритм должен установить координаты {1,2,3,4,5,6,7,8,9,10}

Теперь для менее тривиального примера:

num_ivc=3  
known(num_ivc)=[xmin,5.5,xmax  
or just  
num_ivc=1  
known(num_ivc)=[5.5]   

СейчасНе могли бы вы иметь 5 равномерно распределенных точек на интервале [1, 5,5] и 5 равномерно распределенных точек на интервале (5,5, 10]? Но между 1 и 5,5 больше места, чем между 5,5 и 10.указывает на [1, 5.5], а затем на 4 (от 5,5 до 10). Ключ в том, чтобы минимизировать разницу в расстоянии.

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

only works if N is large
only works if N is small
only works if it the known points are close together
only works if it the known points are far apart
only works if at least one of the known points is near a boundary
only works if none of the known points are near a boundary

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

Answer 1

Ваши начальные точки определяют количество интервалов, длина которых (скажем) a1, a2, ..., ak. Вы собираетесь разделить их на (скажем) m1, m2, ..., mk подинтервалы. Очевидно, что вы хотите равный интервал в каждом интервале, поэтому у вас будет m1 подинтервалов длины a1 / m1, затем m2 длины a2 / m2 и т. Д.

Теперь, конечно, вы не определили «оптимальный интервал», и, вероятно, не существует Единого Истинного Пути для его определения, но давайте возьмем его для обозначения «минимизация суммы квадратов длин подынтервалов». (Простое упражнение: когда у вас есть только один интервал, это фактически дает вам равное подразделение.) Тогда ваша цель - минимизировать a1 ^ 2 / m1 + ... + ak ^ 2 / mk с ограничением m1 +. .. + mk фиксировано, а все m являются натуральными числами.

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

1. Вычислите начальное предположение, просто округлив «непрерывное» решение до ближайших целых чисел. То есть: если вы стремитесь получить в общей сложности M + 1 балл, а следовательно, и M субинтервалов, возьмите mj = round (M * aj / s), где s = a1 + ... + ak.
2. К сожалению, это не даст вам правильное значение m1 + ... + mk, если вам не повезет. Так что теперь исправьте это, добавив 1 к некоторым из них (если у вас слишком мало очков) или вычтя 1 из некоторых (если у вас слишком много). Сделайте это, скажем, в порядке ошибки, возникшей при округлении; то есть в порядке M * aj / s - раунд (M * aj / s). (Увеличение или уменьшение порядка в зависимости от того, в каком направлении ваш m1 + ... + mk был неправильным.)

Здесь я делаю предположение, которое может быть или не быть правильным, а именно то, что вы хотите, это что-то вроде «все интервалы одинаковой длины, как можно ближе», а не «соседние интервалы равной длины, как почти по возможности ". (Тестовый пример: предположим, что вы пытаетесь разделить интервал [0,1] на 9 внутренних точек, и у вас должна быть одна из них с 0,001. Вы берете 0, 0,001 и еще 8 точек с равным интервалом между 0,001 и 1? или вы действительно хотите, чтобы они были ближе к 0,001?) Если вам нужен последний, то все становится интереснее и сложнее.

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