I found a heuristic solution that has complexity O(n*log(n)) per
step (for 1000 elements and 16 areas, I got a good solution in 500
steps).
The code has some constraints that are easy to remove:
- All areas must have exactly the same amount of elements
- Distances calculated assuming flat space (just rewrite Point’s
function distance_to)
It’s easy to customize heuristic params and remove those
constraints
Ps.: Not sure about the complexity, you can check yourself, because
I solved the problem during a sleepless, but it’s gone now and I’m
going to bed. If you have some doubts ask me and I’ll answer
tomorrow…
Solution:
class Point
attr_accessor :x, :y, :distances, :at
def initialize(x, y)
@x, @y = x.to_f, y.to_f
end
def distance_to§
Math.sqrt sum_of_squares_to§
end
def sum_of_squares_to§
(self.x-p.x)**2 + (self.y-p.y)**2
end
def calc_distances_to(areas)
@distances = areas.inject({}){ |d, a| d[a] = distance_to a.mean;
d }
end
def self.new_by_rand
Point.new(rand(100), rand(100))
end
def to_s
“(#{x},#{y})”
end
alias :inspect :to_s
end
class Area < Array
def mean
@mean || mean!
end
def entropy
self.inject(0) do |ent, p|
ent += mean.sum_of_squares_to p
end
end
def mean!
ps = self.inject( Point.new(0, 0) ) do |ps, p|
ps.x += p.x
ps.y += p.y
ps
end
ps.x = ps.x/self.size
ps.y = ps.y/self.size
self.sort_by!{ |p| p.distance_to ps }
@mean = ps
end
def fix!
self.each do |p|
p.at = self
end
end
def self.refine(areas, points, n)
area_size = areas.first.size
refresh_distances(areas, points)
doubt_points = areas.inject([]) do |dp, area|
dp.concat area[n…-1]
end
doubt_points.each do |point|
point.at.delete point
point.at = nil
end
doubt_points.each do |point|
ordered_areas = point.distances.sort_by{ |k, v| v }
nearest_area, distance = ordered_areas.pop
until(nearest_area.size < area_size)
nearest_area, distance = ordered_areas.pop
end
nearest_area << point
point.at = nearest_area
end
end
def self.refresh_distances(areas, points)
areas.each &:mean!
points.each do |p|
p.calc_distances_to areas
end
end
def self.all_areas_same(areas_1, areas_2)
areas_1.each_with_index do |a, i|
return false if areas_2[i] != a
end
return true
end
def self.refine_until_good_solution(areas, points, good_ratio =
0.01, max = 10_000, n = (areas.first.size0.9).to_i, doubt_region =
max0.05)
areas, points = areas.clone, points.clone
current_entropy = last_entropy = areas.inject(0){ |ent, a| ent +=
a.entropy }
enhance = 10*good_ratio
count = 0
best_solution = areas.clone
best_entropy = current_entropy
while( count < doubt_region || ( count < max && enhance >
good_ratio ) )
last_entropy = current_entropy
Area.refine areas, points, n
current_entropy = areas.inject(0){ |ent, a| ent += a.entropy }
enhance = (current_entropy - best_entropy)/best_entropy
if best_entropy > current_entropy
best_entropy = current_entropy
best_solution = areas.clone
end
count += 1
puts “Step: #{count}, Enhance: #{enhance}, Entropy:
#{current_entropy}”
end
best_solution.each &:fix!
[ best_solution, best_entropy ]
end
end
Example:
points = []
areas = 16.times.map do |n|
area = Area.new
(1000/16).times do |i|
p = Point.new_by_rand
p.at = area
area << p
points << p
end
area
end
Area.refine_until_good_solution(areas, points)
