Алгоритм для групповых шкал

Question

У меня есть диаграмма с диаграммой с несколькими вертикальными осями, и я хочу группировать диаграмму повсеместно. Теперь он разделяется только специальными данными в коде. Например:

• масштабе 1 составляет около 3,0 и содержит только одну диаграмму с максимальным значением 2,5
• шкала 2 составляет около 2000 и содержит три диаграммы с максимальным значением 1200, 1500, 1650
• масштаб 3 представляет собой около 10000 и содержит две диаграммы с макс. значение 9000 и 8200

Какой алгоритм группировки я могу использовать в каждом случае?

Answer 1

Вы, кажется, ищете алгоритм, который принимает несколько значений (разные сюжеты для построения) и сортирует их по группам (группируя объекты, построенные по одному и тому же масштабу вместе). Аналогичная ситуация возникает при изготовлении цветных карт, которые показывают, например, насколько богаты разные области, только они разделяют области на группы, а не разные вещи на группы. Один из алгоритмов, используемых для этого, - http://en.wikipedia.org/wiki/Jenks_natural_breaks_optimization. Я не думаю, что это особенно здорово, но люди его используют, и это хорошо объясняется в статье.

Вы также можете решить эту проблему с помощью динамического программирования, где у вас есть функция стоимости, например, если вы построите график с максимальным значением 1000 с использованием шкалы с максимальным значением 1500, у вас есть стоимость (1000-1500)^2. Сортируйте максимальные значения для графиков в порядке и работайте слева направо. Для первых k максимальных значений найдите наилучшее назначение, используя до n групп, для n = 1..k. Вы можете получить ответы на k из ответов на k-1.