7

個人的なイースター プロジェクトとして、モデルベースのテストを職場で実装しようとしています。Python で実装されたグラフがあり、グラフのすべてのエッジをトラバースするか、グラフのすべての遷移を少なくとも 1 回実行する必要があります。エッジを 2 回以上トラバースすることは問題ではありませんが、同じノードで開始および終了し、一連のエッジ/トランジションを取得する必要があります。

より単純なアルゴリズム > 最短のシーケンス。

私は周りを見回して多くのアルゴリズムを見つけましたが、自分に合ったアルゴリズム/組み合わせを見つけることができませんでした. 誰かが私を正しい方向に向けたり、これを行う方法についてのヒントを教えてくれたりしたら、それは素晴らしいことです.

私のグラフの実装は次のようになります。

graph = {
    A : {'IDLE': 't8', 'B': 't2', 'C': 't4'},
    B : {'A': 't3', 'C': 't4', 'IDLE': 't6'},
    C : {'A': 't5', 'IDLE': 't7', 'B': 't2'},
    IDLE : {'A': 't1'}
}

グラフ

4

4 に答える 4

5

アプローチ1

グラフGを新しいグラフG'に変更できます。ここで、Gの各エッジがG'のノードになります。一部のA、B、およびCのGで「A-> t1-> B-> t2-> C」が可能な場合は、G'でt1からt2にエッジを作成します。

次に、G'でパスカバーを見つける必要があります。

アプローチ2

  • 位置Pは、最初はノードP0（アイドルなど）です。
  • 各エッジT（AからB）について、PからAへのルートを見つけ、Tを使用してBに移動します。PをBに更新します。
  • 最後に、PからP0に戻るルートを見つけます。
于 2012-04-06T11:58:37.420 に答える
1

グラフ内の各P1、P2ポイントについて、すべてのR道路を検索します。ここで、Rは次のようになります。

R =（P1、Pf1、...、Pfn、P2）

P1からP2までの各R1、R2道路について、交差点（R1、R2）に0を超えるポイントがある場合（もちろん、P1とP2を除く）、どちらが短いかを判断します。R1の長さがR2の長さよりも小さい場合は、R2を忘れてください。そうでない場合は、R1を忘れてください。

反復では、P1からP2までの最短の完全に分離した道路が見つかります。ポイント（P1、...、Pk）がある道路を横断する場合1 <= i <= kであるPiを選択すると、最初のポイントはPiになり、最後のポイントはPiになります。パイにもなります。

順序は重要ではないとします。ポイントをトラバースするときはいつでも、トラバース済みとしてマークしてください。ポイントがトラバースとしてマークされている場合、指定されたポイントに再度移動する必要はありませんが、必要に応じてポイントを再度トラバースしてもかまいません。したがって、計画される道路は次のようになります：Pf1、...、Pfk、Pf1。

Pfjごとに、Pfm：

私たちはこの瞬間にPfjにいます。Pfmがトラバースされた場合、Pfmに再度移動したくないので、次の反復に進みます

Pfmを通過しない場合、PfjからPfmへのR1、...、Rq道路があります。通過していないポイントの数が最大で、すでに通過している道路の数が最小の道路を選択します。道路内の未横断ポイントと横断ポイントの重要性を巧妙なアイデアで重み付けする必要があります（うまくいけば、重みによってPf1からPf1までの道路の全長が最小化されます）。

アルゴリズムの最後に到達したいので、Pf1をトラバースとしてマークしないように注意してください。

于 2012-04-06T14:02:09.857 に答える
0

アルゴリズムが必要なのか、それとも仕事を成し遂げる方法を知りたいのか、私にはわかりません。後者の場合は、networkxを使用できます。

networkxをダウンロードしてインストールしたら、次のことを試すことができます

>>> import networkx as nx
>>> DG=nx.DiGraph()
>>> def CycleFrom(G,node):
    return sorted((c for c in nx.simple_cycles(DG) if node in c), key=len)[0]

>>> for (stnode, edges) in graph.items():
    for (ennode,edge) in edges.items():
        DG.add_edge(stnode,ennode,name=edge)


>>> for node in DG.nodes():
    print "Cycles from {0} is {1}".format(node,CycleFrom(DG,node))


Cycles from A is ['A', 'IDLE', 'A']
Cycles from IDLE is ['A', 'IDLE', 'A']
Cycles from B is ['A', 'B', 'A']
Cycles from C is ['A', 'C', 'A']
>>>
于 2012-04-06T12:35:47.913 に答える