Approximate Minimal Set Cover Python -


i have list of lists each list contains edge lengths of polygon. example:

[[0, 1, 2],  [0, 1.1, 2],  [0, 1.2, 2],  [0, 1.3, 2],  [4.5, 1.1],  [4.4, 1.1],  [5, 1, 2],  [5, 1.1, 2],  [5, 1.2, 2]  [6, 1, 7, 4],  [6, 1.1, 7, 4.1]] 

i able find approx minimum "cover" in sense each element of "cover" of it's values within specified tolerance of elements covering. example, if tolerance .1 given list above get:

[[0, 1, 2],  [0, 1.2, 2],  [4, 1],  [4.5, 1.1],  [5, 1.1, 2],  [6, 1, 7, 4],] 

i new python use of terminology isn't far off. perhaps helpful explain motivation.i architect trying optimize given surface panelization. because of manufacturing tolerances panels edges lengths differ fixed amount can considered same(in example above edges can differ .1 , still considered same). trying find minimum set of panels produced , still panelize surface.

to find optimal solution here computationally quite difficult -- seem asking something, doesn't have perfect.

for rest of this, i'm going discuss proposed algorithm 1d case, on grounds it's simpler describe, can extend algorithm 3d. i'm declaring "range" [min,max].

for each point, following:
--check list of ranges see if point falls 1 of them
----if does, make range [max(min,point-interval), min(max,point+interval)].
----if not, add new range [point-interval, point+interval]
once complete, output point list center of each range.

the idea here represent each point acceptable range fits in. once have that, overlapping ranges can reduced intersection, since anywhere in intersection acceptable both initial points. process can continued until ranges remain not overlap.


Comments

Popular posts from this blog

php - Submit Form Data without Reloading page -

linux - Rails running on virtual machine in Windows -

php - $params->set Array between square bracket -