求解一个算法（变态需求）

刚刚对一个需求画了一个业务场景，但是业务场景的解就是让我头疼，其实现在连这个解的标准都还没有确定，不知道该怎么描述这个问题，下面把这个问题的图给贴出来，请各位高手帮忙看一下： 


 

图中的A1,A2,A3,B1,B2...,C2,C3都是业务实例，每个业务实例属于一层，以上图片有三层，其中A1,A2,A3属于A层，B1,B2...B6属于B层，C1,C2,C3属于C层，其中还有各个有向的线我都给增加了名字，表示各个业务实例中的关系，其中拿A2A3B3B4B5XXYYY1举个例子：

 

  它表示A2,A3共同对B3,B4,B5有一种影响，对于这条线来说A2,A3称为该影响的源，B3,B4,B5称为该影响的目标，后边的X就是表示源的个数（有几个源就有几个X），Y表示目标的个数（有几个目标就有几个Y），1是对他们之间的关系的第一次影响（以后如果有相同的影响关系这个值就得递增了）。

影响关系的要求：其中源必须来自同一层，目标也必须是同一层。同一层的任何组合都可以做影响关系的源，也可以成为影响关系的目标。同样的源可以影响多次同样的目标。比如：

 A3对A1有三次影响。

现在的任务（也是本人最头疼的地方）：

首先是确定各层中业务实例在该层中的的位置（层内只有横向坐标）使得将来构建的时候使用的线交叉最少（这个问题的前提是不能破坏层的之间的上下级关系。这个业务需求就是我将来要把这个图中所描述的关系在JSP中画出来），但是我现在还没有一个标准是什么叫交叉数最少，还请各位高手指点迷津。

如果有了这个标准后，有没有一个可行的算法去实现它。

我不知道遗传算法和神经网络能不能解决该问题，如果有人知道，请麻烦给个提示。

业务补充：

分层一般也就只有4，5，但是不排除特殊的业务会达到10层甚至更多。

每一层一般也就5，6个业务实例，但是也有可能很多。

 

不知道我把问题说明白没有，请各位高手帮忙或者给个提示。

 

 

 

 

评论

5 楼 mfnevi 2010-03-18  

sdh5724 写道

http://www.iteye.com/topic/113027

这家伙玩过一些。 

你这个东西是一个典型的有向图自动布局算法。 这在图论里有不少描述， 你最好看看相关算法论文， 我觉得有了论文的支持后， 应该是不算太难的。

这篇文章我已经看过了，它采用jgraph自动布局来确定页面元素的位置，这样的话，他们之间的位置，以及和线之间的关系可能发生交叉，还有好像没有分层的这种说法，考虑给各条线增加权重，也好像不能很好的来控制层。

4 楼 mfnevi 2010-03-17  

sdh5724 写道

这问题有点复杂。。。目前的自动算法， 好像还不是那么磷光， 可以看看很多UML啊， VISIO 都做不到一个优秀的布局。 

对，我只是想找到一种思路，也许不是最优解，但是，至少能得到一个解决问题的方法。

sdh5724 写道

http://www.iteye.com/topic/113027

这家伙玩过一些。 

你这个东西是一个典型的有向图自动布局算法。 这在图论里有不少描述， 你最好看看相关算法论文， 我觉得有了论文的支持后， 应该是不算太难的。

我先看看，谢过。

sdh5724 写道

你是不是在做变更影响的自动化判定类似的业务啊？  这个在软件集成里用处比较大。

一个差不多吧，，一个引擎平台。。。

3 楼 sdh5724 2010-03-17  

你是不是在做变更影响的自动化判定类似的业务啊？  这个在软件集成里用处比较大。

2 楼 sdh5724 2010-03-17  

http://www.iteye.com/topic/113027

这家伙玩过一些。 

你这个东西是一个典型的有向图自动布局算法。 这在图论里有不少描述， 你最好看看相关算法论文， 我觉得有了论文的支持后， 应该是不算太难的。

1 楼 sdh5724 2010-03-17  

这问题有点复杂。。。目前的自动算法， 好像还不是那么磷光， 可以看看很多UML啊， VISIO 都做不到一个优秀的布局。