我附上3个屏幕截图来帮助解释这一点,但基本问题是,给出是/否？决策节点,找到终止分支的最近的子节点.
我在C#.NET和JSON工作.在JSON中,我有一个对象,它为每个节点提供唯一的标识符,并且还标识从一个节点到下一个节点的每个“链接”.我希望编写一个函数(或几个)来确定给定C#中的分支节点的第一个“结束节点”.目前我已经在C#中将jSON构建为XML.
附件是图中jSON的输出：
{ "class": "go.GraphLinksModel","linkFromPortIdProperty": "fromPort","linkToPortIdProperty": "toPort","nodeDataArray": [
{"key":-1,"category":"Start","loc":"169 288","text":"Start"},{"key":-2,"category":"End","loc":"855 394","text":"End"},{"category":"Branch","text":"Yes or No","key":-4,"loc":"284.8837209302326 285.7848837209302"},{"category":"DelayNode","text":"Delay","key":-3,"loc":"365.8837209302326 215.52345997177622"},"key":-5,"loc":"478.8837209302326 214.52345997177622"},"key":-6,"loc":"568.8837209302326 151.52345997177622"},"key":-7,"loc":"573.8837209302326 268.5234599717762"},"key":-8,"loc":"653.8837209302326 215.52345997177622"},"key":-9,"loc":"392.8837209302326 392.5234599717762"},"key":-10,"loc":"454.8837209302326 317.5234599717762"},"key":-11,"loc":"550.8837209302326 473.5234599717762"},"key":-12,"loc":"549.8837209302326 317.5234599717762"},"key":-13,"loc":"711.8837209302326 343.5234599717762"},"key":-14,"loc":"434.8837209302326 487.5234599717762"}
],"linkDataArray": [
{"from":-4,"to":-3,"fromPort":"T","toPort":"L","visible":true},{"from":-1,"to":-4,"fromPort":"R","toPort":"L"},{"from":-3,"to":-5,{"from":-5,"to":-6,"to":-7,"fromPort":"B","visible":true,"text":"NO"},{"from":-6,"to":-8,{"from":-7,{"from":-4,"to":-9,{"from":-9,"to":-10,{"from":-10,"to":-12,{"from":-11,"to":-13,{"from":-12,{"from":-8,{"from":-13,"to":-2,"to":-14,{"from":-14,"to":-11,"text":"NO"}
]}
解决方法
正如对奥伦回答的评论中所指出的那样,奥伦实际上已经回答了这个问题：“两个分支机构最接近的节点是什么？”但实际上要回答的问题是“两个分支必须达到的最接近的节点是什么？”
这是一个相当难以解决的问题,我不知道一个有效的解决方案.但是,这是一个可行的算法草图.
假设给定的决策节点被称为A,而WOLOG它有两个子节点B和C.那么问题是什么是节点,称之为G,它具有以下两个属性：
>从B到END的每条可能路径,以及从C到END的每条可能路径都经过G.
> G是距离B和C最近的具有第一个属性的节点.
(注意G可能是END.我们可能有A – > B,A – > C,B – > END,C – > END.)
我们可以从容易制作一组可能的G的候选人开始.选择从B到END的任何路径 – 如果您愿意,可以随意选择它 – 并将其节点放在哈希集中.然后选择从C到END的任何路径,并将其节点放在哈希集中.这两组的交集包含G.调用交集α.
所以现在让我们从Alpha中删除绝对不是G的所有节点.对于集合Alpha中的每个节点N：
>构造一个与原始图形相同的新图形,但缺少N.
>新图表中的B或C是否仍可以到达END？如果是,则N绝对不是G.如果不是,则添加N以设置Beta.
如果我们完成Beta测试为空,则G为END.
否则,Beta中有节点.这些节点中的每一个都具有如果删除它,则没有其他方法可以从B或C到END.恰好其中一个节点必须最接近B – 如果两个节点同样接近,那么其中一个节点就没有必要了！ – 来自B的广度优先遍历也是如此,并且当您第一次遇到Beta中的节点时,那就是您的G.
如果图形很大,这个草图似乎不会很快,但我很确定它会起作用.我很想知道是否有更好的解决方案.
