集合的视觉表示

发布于 2024-10-08 21:47:34 字数 405 浏览 0 评论 0原文

我有一些实验数据,我决定将它们表示为集合。

假设有一个主集合 E={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r ,s}(蓝色圆圈)和几个子集B红色虚线省略号),其中包含主集中的元素<强>E。

我需要在主集中E中表示这些子集并显示它们的交集,或多或少类似于下图。

这就是为什么我需要一些算法(带有示例)来绘制该图。最好使用 PHP 或 Javascript(使用 SVG 规范),因为我将在 Web 应用程序中实现这个问题。

集合覆盖问题的图形表示

预先谢谢您!

I have some experimental data and I have decided to represent them as sets.

Let's say, there is a main set called E={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s} (blue circle) and several sub-sets B (red dashed ellipses) which contains elements from main set E.

I need to represent these sub-sets in the main set E and show their intersections, more or less similar to the figure below.

That's why I need some algorithms (with an example) to draw that figure. Preferably in PHP or Javascript (using SVG specification), because I am going to implement this problem in a Web Application.

Graphical representation of set-covering problem

Thank you beforehand!

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

指尖上得阳光 2024-10-15 21:47:34

我的感觉是,这是 遗传算法 擅长的事情,因为:

  1. 总路径所有子集周长的长度可以用作适应度函数(最小化此函数将倾向于给出缺乏长瘦子集的“良好”解决方案),并且该函数是连续的。
  2. 实现突变(调整一个或多个元素的位置)和交叉(交换某些元素的位置)应该很简单。

对于适应度函数的另一个重要建议:严重惩罚任何一个子集的周长包含不属于该集合的元素的解决方案。

我的建议是使用元素的凸包作为子集周长(或者甚至可能是边界框,这更简单)。确定最佳位置后,您可以使用样条线绘制周长,使其美观且平滑。

My feeling is that this is something that a genetic algorithm would be good at, because:

  1. The total path length of all subset perimeters could be used as the fitness function (minimising this will tend to give "good" solutions lacking long skinny subsets), and this function is continuous.
  2. It should be straightforward to implement mutation (jiggle the positions of one or more elements) and crossover (swap the positions of some elements).

Another important suggestion for the fitness function: heavily penalise any solution where one subset's perimeter encloses an element that does not belong to that set.

My suggestion is to work with convex hulls of elements for subset perimeters (or possibly even bounding boxes, which are even simpler). Once optimal locations have been decided, you can draw the perimeters using splines to make them nice and smooth.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文