Так как на данном форуме сейчас всего 22 темы, включая подробный перечень всех алгоритмов по алфавиту и по категориям, и данная тема идёт всего лишь второй в списке тем форума, так как тема уже поднималась один раз через 2 года, так как по словам автора видно, что тема для него ещё актуальна (до сих пор хочет что-то ещё реализовать), то решил допустимым написать сюда сообщение.
Спасибо за интересную задачу! Предложу свой подход к её решению.
Пусть
— количество точек, которые нужно сгенерировать (почему
, станет ясно потом).
— диапазон, в котором должны находиться генерируемые точки.
— рациональные числа, границы допустимого диапазона среднего значения. Если точность не ниже второго знака, то
.
Задача имеет решение тогда и только тогда, когда существует целое
, такое что
. Инструкция языка Си для проверки этого условия:
(p1 * q / q1 != p2 * q / q2). В том числе задача имеет решение тогда, когда
. В случае точности в несколько знаков после запятой неравенство будет выглядеть так:
, а инструкция так:
(p3 * q / q3 != (p3 + 1) * q / q3), а достаточное условие так:
.
Пусть
— число точек, имеющих значение
,
. Тогда условие вхождения среднего значения в требуемый диапазон будет записываться следующим образом:
. Обозначим:
, а
уже обозначено:
. Отсюда сразу видно, откуда взялось необходимое и достаточное условие существования решения.
Решение задачи состоит в том, чтобы выбрать число
p из диапазона возможных значений от
p1 * q / q1 + 1 до
p2 * q / q2 (это будет целевая сумма всех точек) и случайным образом разбить эту сумму на числа из допустимого диапазона.
можно выбрать как первый элемент из числа подходящих (когда не имеет значения где среднее значение окажется внутри допустимого диапазона, в таком случае оно всегда будет в самом начале диапазона), как ближайший к требуемому среднему элемент, как случайный элемент из диапазона (выбираем распределение (например, равномерное или нормальное), подбираем вероятности элементов так, чтобы они наиболее близко походили к распределению (при этом нужно будет решить задачу математической оптимизации, в случае равномерного распределения — задачу линейного программирования) и генерировать в соответствии с этими вероятностями случайный элемент).
Разбиение суммы на числа из допустимого диапазона это то же самое, что сгенерировать случайные
(далее в соответствии с этими
сгенерировать возрастающую последовательность, а потом применить к ней случайную перестановку). Это то же самое, что построить случайную неубывающую целочисленную функцию целочисленного переменного с областью определения
и областью прибытия
, имеющую фиксированную площадь под графиком, равную
. Это то же самое, что случайным образом
проехаться по Манхэттену шириной
и высотой
так, чтобы отрезать кусок Манхэттена площадью
. То же самое, что случайным образом насыпать
ящиков в контейнер шириной
и высотой
, стоящий на боку.
Для этого нужно подсчитать и перечислить все промежуточные состояния контейнера при переваливании его с одного бока на другой, потом, начиная с первого состояния, двигаться случайным образом по графу переходов между последовательными состояниями при переваливании с вероятностями переходов пропорциональными количеству вариантов, которые ожидаются после перехода. Это позволит сгенерировать случайный вариант из всех возможных с вероятностью (1 / количество всех возможных вариантов). Для подсчёта количества вариантов можно попробовать найти для него рекурсивное выражение через количество вариантов в контейнере меньшего размера:
, но у меня не получается.
По-моему, алгоритмы
Хакера,
Debugger'а и
alibek'a будут прилеплять точки к краям. В середине их будет разбрасывать больше к краям, а ближе к краям они будут двигаться медленней, что в итоге будет приводить к в среднем большей концентрации точек у краёв, но нужно проверять.
Кроме того, реализация алгоритма
Хакера от
oskolok_vatbI тоже прилепляет точки к краям (это хорошо видно на графике), но по другой причине: по причине ошибки в программе: ветка кода
ElseIf Data(Point1) < minPossibleValue And Data(Point2) > maxPossibleValue Then никогда не выполняется, а в случае, когда одна из точек находится на границе, вообще ни одно условие не срабатывает и точки остаются на месте. В результате, точки могут войти на границу, но не могут выйти, и они там массово скапливаются. Вообще, реализация плохая, да и у
Хакера идея не совсем додуманная. Поэтому и результаты некрасивые получились. Вот так будет правильно:
- Код: Выделить всё
If Data(Point1) > minPossibleValue And Data(Point2) < maxPossibleValue And Data(Point1) < maxPossibleValue And Data(Point2) > minPossibleValue Then
If Int(2 * Rnd) = 0 Then
Data(Point1) = Data(Point1) - 1
Data(Point2) = Data(Point2) + 1
Else
Data(Point1) = Data(Point1) + 1
Data(Point2) = Data(Point2) - 1
End If
ElseIf Data(Point1) > minPossibleValue And Data(Point2) < maxPossibleValue Then
Data(Point1) = Data(Point1) - 1
Data(Point2) = Data(Point2) + 1
ElseIf Data(Point1) < maxPossibleValue And Data(Point2) > minPossibleValue Then
Data(Point1) = Data(Point1) + 1
Data(Point2) = Data(Point2) - 1
End If
Ты выставляешь все значения примерно равными (для части точек выставляешь значение на единицу меньше требуемого среднего, для части — на единицу больше требуемого), то есть выкладываешь на дно контейнера полные ряды, а последний ряд выкладываешь частично. При этом ты это делаешь очень неоптимально, вот оптимальное решение (уж не знаю, оптимизирует ли это компилятор или нет):
- Код: Выделить всё
For i = 0 To UBound(Data) - (Average Mod (UBound(Data) + 1))
Data(j) = (Average - (Average Mod (UBound(Data) + 1))) / (Average Mod (UBound(Data) + 1))
Next i
For i = UBound(Data) - (Average Mod (UBound(Data) + 1)) + 1 To UBound(Data)
Data(j) = ((Average - (Average Mod (UBound(Data) + 1))) / (Average Mod (UBound(Data) + 1))) + 1
Next i
В итоге в начальном раскладе получается небольшая пространственная неоднородность (слева точек немножко больше, чем справа, засчёт выложенного слева неполного ряда). С течением итераций эта неоднородность выравнивается, но при небольшом количестве итераций может быть заметна незначительная бегущая средняя. Чтобы её не было, ты должен использовать алгоритм Брезенхэма, про который говорил
Хакер. При выкладывании последнего ряда ты должен выложить его не сплошной полосой, а распределив ящики приблизительно равномерно по ряду. То есть если нужно выложить половину ряда, то вместо того чтобы заполнить правую половину ряда, а оставшуюся половину оставить пустой, ты должен сначала положить один ящик, а затем одно место оставить пустым, потом снова положить один ящик, потом снова оставить место пустым. То есть сделать начальный расклад в виде зубчатки. Если последний ряд должен содержать три ящика, то ящики нужно положить в начале, в середине и в конце, оставшееся место оставить пустым, если последний ряд должен содержать на три ящика меньше, чем ширина контейнера, то нужно его полностью выложить ящиками, а три места, в начале, в середине и в конце, оставить пустыми и т. д. Это и будет реализацией того самого алгоритма, похожего на алгоритм Брезенхэма, про который говорил
Хакер. В алгоритме Брезенхэма строится прямая линия из одного угла прямоугольной таблицы шириной
и высотой
в противоположный. Участки прямой при этом имеют только две возможных длины: результат целочисленного деления
на
и длина, на единицу большая этого значения. Точно так же как и у тебя: части точек выставляется значение на единицу меньше требуемого среднего, а для части — на единицу больше требуемого. В алгоритме Брезенхэма ширина таблицы приблизительно равномерно распределяется между строками таблицы, образуя
участков линий, а у тебя целевая сумма приблизительно равномерно распределяется между
точками. Тебе нужно реализовать определение значения точек аналогично тому, как в алгоритме Брезенхэма идёт определение ширины горизонтальных участков линий при рисовании прямой линии в таблице
на
. Сам алгоритм Брезенхэма описывать не буду, извини, это можно найти в Интернете без проблем, в том числе и на этом форуме.
Кроме того, в алгоритме
Хакера в общем случае (не в случае сдвига на 1, а в случае сдвига на несколько единиц) нужно смотреть, насколько возможно продвижение при зеркальном сдвиге в одну сторону (когда уменьшается первое число и увеличивается второе) и насколько возможно продвижение в другую сторону (когда уменьшается второе число и увеличивается первое) и выбрать случайное значение из суммарного интервала движения в ту и в другую сторону.
Попробуй реализовать алгоритм
Хакера, и построй графики распределения точек по возможным значениям (с какой частотой какие значения встречаются). Образуется ли там увеличение концентрации точек к краям диапазона?
А лучший алгоритм из всех здесь предложенных, я думаю, это твой алгоритм. Алгоритм
Qwertiy является тем же самым, что и твой алгоритм, но случайность вносится в конце, а не вначале. Берётся случайный равномерно распределённый набор точек и затем по единичке уменьшаются случайные точки и сумма набора уменьшается к нужной сумме
(см. выше) и среднее арифметическое к нужному значению. Постоянное движение к цели, которое всегда гарантированно даст подходящий результат. И со случайностью, и с распределением всё весьма неплохо. Только двигаться нужно к цели смелее. По одной единичке отнимать — это как девушке лайки ставить ВКонтакте. Нужно сразу приглашать девушку на свидание. То есть уменьшать случайную точку на случайное число k, которое генерируется случайным в диапазоне от 0 до значения уменьшаемой точки, как в алгоритме
Хакера. Это будет то же самое, но цель будет достигнута быстрее. А ещё лучше — генетический алгоритм и генерировать популяцию. Это ещё эффективнее. Это то же самое, что и твой метод, только движение к цели будет идти сразу в несколько потоков. Некоторые сперматозоиды будут двигаться медленно и не туда, и они отомрут через некоторое время, а некоторые будут двигаться быстро и к цели. Один из числа последних (такой, который сразу на k шагов вперёд мутирует), в конце концов, добъётся внимания требуемого среднего значения, то есть добъется определённого в условии задачи уровня близости с ней.
oskolok_vatbI писал(а):alibek,
Большое спасибо, попробую реализовать.
Ну как дела, реализовал?
Википедия — это наилучший источник информации по теме «Википедия».
