2

特定のプロセス図を通る一連の非反復パスを確立する合理的な方法で可能かどうかを理解しようとしています。

ここに私が持っているプロセス図に関するいくつかの基本的な事実があります:

  • 1 つ以上の開始点がある
  • 1 つ以上のエンドポイントがある
  • すべての始点には、そこからつながる 1 つのコネクタがあります
  • すべてのステップには、少なくとも 1 つ以上の受信コネクタと 1 つ以上の送信コネクタがあります。
  • 次のものが複数ある場合は、それぞれに名前を付ける必要があります。
    • ターミネーターを開始
    • 終了ターミネーター
    • ステップからつながる接続

必要と思われるすべてのデータにアクセスできます (すべての開始点の検索、すべての接続の取得、接続の名前など)。

基本的には、始点から終点までの過程で、円を繰り返し回らないユニークなパスをできるだけ多く見つけたいと考えています。したがって、同じステップを数回実行できますが、特定のルートで完全な回路を複数回繰り返すことはできません。

これは、人々が論文を書き、それができるかできないかの証拠を持っているようなものです.私はそれをグーグルで検索する必要がある魔法の言葉を知りません;-) 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 を 3 回押し、そのたびにオプション 2 を選択しましたが、繰り返しはありません。

余分なポイント：複数のアウトバウンドコネクタを持つノードのいくつかを、プロセスの特定の実行内で一貫しているとマークできると考えていました..たとえば、2つの決定ポイント「言語」を持つ「コードを書く」プロセスがある場合アウトバウンド コネクタ "c#" および "java" このプロセスの特定の実行内では、常に c# または Java のいずれかであると言えます。これは、プロセスの実行中に変更されることはありません。「バグはありますか？」のように変化する可能性があるものとは対照的です。最初のパススルーでは「はい」となる可能性があり、2 回目のパススルーでは (いくつかのバグ修正手順の後 ;-) 結果が「いいえ」になる可能性があります。

この種の特別な分析/処理/定義に関連する用語またはテクニックを知っていますか?

編集: @Ishtar の回答に基づいて、JS で実装されたサンプル ソリューションを回答者として追加しました。

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ソリューションのWebページの完全な例、グラフは質問からのものです...うまくいくようですが、広範囲にテストされていません。私が予想していたよりもはるかに簡単な解決策です;-)

    <!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 に答える