2

我试图了解是否有可能以任何合理的方式通过给定的流程图建立一组非重复路径。

以下是关于我所拥有的流程图的一些基本事实：

  • 他们有一个或多个起点
  • 他们有一个或多个端点
  • 所有起点都有一个从它们引出的连接器
  • 所有步骤至少有一个或多个入站连接器和一个或多个出站连接器
  • 如果有以下一项以上，则必须分别命名：
    • 启动终止符
    • 终结者
    • 从一个步骤引出的连接

我可以访问我能想象到的所有数据（查找所有起点、获取所有连接、连接名称等）。

我基本上想在整个过程中找到尽可能多的独特路径，从起点到终点，您不会反复绕圈。因此，您可以多次执行相同的步骤，但在任何给定的路线中，您不能多次重复完整的电路。

这似乎是人们会写论文并证明为什么可以或不能完成的事情的类型，我只是不知道我需要用谷歌搜索的魔法词;-) Sudo 代码或类似代码将是理想的（而且令人惊叹）但如果​​有人能指出我正确的方向，我很乐意自己阅读。

非常欢迎和非常感谢任何搜索词的建议

请注意，我会对提出许多额外“愚蠢”可能性的解决方案感兴趣，这些可能性必须由人事后审查 - 看看它产生了什么仍然很有趣。

一个例子来澄清事情：

        G<--2-E<--1-F-2--|
        |     |     ^    |
        |     1     |    |
        |     |     2    |
        \/   \/     |   \/
start--->A--->B---->C-1->D---end

一些路线通过：

  • 开始，A，B，C：1，D，结束
  • 开始,A,B,C:2,F:1,E:1,B,C:1,D,结束
  • 开始,A,B,C:2,F:1,E:2,G,A,B,C:1,D,结束
  • 开始,A,B,C:2,F:2,D,结束

不错，但是更有趣的呢：

  • 开始,A,B,C:2,F:1,E:2,G,A,B,C:2,F:1,B,C:2,F:2,D,结束

我按了三下 C，每次我选择选项二并且没有重复。

加分：我在想我可以将一些具有多个出站连接器的节点标记为在任何给定的流程执行中是一致的。例如，如果有一个“编写代码”流程的决策点“语言”有两个出站连接器“c#”和“java”我可以说，在这个进程的任何给定执行中，它始终是 c# 或 java - 在进程执行期间永远不会改变。而不是像“有错误吗？”这样可能会改变的东西。在第一次通过时可能是肯定的，然后在第二次通过时（在一些修复错误步骤之后；-）可能会得到否定的结果。

您是否知道与此类额外分析/处理/定义相关的任何术语或技术？

编辑：我添加了一个在 JS 中实现的示例解决方案作为基于@Ishtar 的答案的答案。

4

3 回答 3

2

深度优先搜索怎么样？这将遍历所有可能的路径。唯一困难的部分是忽略会再次导致相同循环的路径。如果您在一个节点上，请检查您之前是否去过那里（一个循环），并确保路径中没有相同的序列。

例如

start,A,B,C:2,F:1,E:1,B,C:2,F:1,E:1,B

从这里，我们只能去C。回头看（最后4个节点），我们找到了循环C:2,F:1,E:1,B。循环已经存在，所以我们不能去节点c。由于我们不能去其他任何地方，这个分支没有给出正确的路径。

伪代码：

allpaths(path,node)
  cycle = path.substring(path.lastIndex(node)) + node
  if path.contains(cycle)
    return
  path = path + node
  if node.isEndNode
    print path
    return
  for child in node.children
    allpaths(path, child)
于 2011-09-02T13:07:12.397 回答
1

这相关吗？找到有向图的所有基本电路。即使它不是您使用的算法，它也可能有助于适当的定义和名称。

于 2011-09-02T13:06:19.663 回答
0

@Ishtars 解决方案网页中的一个完整示例，该图是问题中的一个......它似乎有效，没有经过广泛测试。它比我预期的要简单得多；-)

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <title></title>
    <script type="text/javascript">

        function connection(name, endPoint) {
            this.name = name;
            this.endPoint = endPoint;
        }

        function node(name) {
            this.name = name;
            this.connections = [];

            this.addConnection = function (conn) {
                this.connections[this.connections.length] = conn;
            }
        }


        function printPath(path) {
            document.getElementById('output').innerHTML = 
              document.getElementById('output').innerHTML
              + path + '<br />';
        }

        function allPaths(path, node) {
            if (node.name == "end") {
                printPath(path + ',' + node.name);
                return;
            }
            cycle = path.substring(path.lastIndexOf(node.name)) + ',' + node.name;
            if (cycle.length > 1 && path.indexOf(cycle) > 0) {
                return;
            }
            for (var i = 0; i < node.connections.length; i++) {
               allPaths(path + ',' + node.name + ":" + 
                   node.connections[i].name
                   ,node.connections[i].endPoint);
            }
       }

        var start = new node("start");
        var a = new node("A");
        var b = new node("B");
        var c = new node("C");
        var d = new node("D");
        var e = new node("E");
        var f = new node("F");
        var g = new node("G");
        var end = new node("end");

        start.addConnection(new connection("1", a));
        a.addConnection(new connection("1", b));
        b.addConnection(new connection("1", c));
        c.addConnection(new connection("1", d));
        c.addConnection(new connection("2", f));
        d.addConnection(new connection("1", end));
        f.addConnection(new connection("1", e));
        f.addConnection(new connection("2", d));
        e.addConnection(new connection("1", b));
        e.addConnection(new connection("2", g));
        g.addConnection(new connection("1", a));

    </script>
</head>
<body onload="javascript:allPaths('start', a)";>
    <div id="output"></div>
</body>
</html>

这是输出（以防万一有人发现错误；-）：

start,A:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:1,E:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:2,D:1,end

猜猜我写这篇文章时不知道 jsFiddle，这里是上面代码的小提琴：

http://jsfiddle.net/6bWMp/1/

于 2011-09-02T17:50:29.383 回答