2

次のように説明されている Udacity の問題を解決しようとしています。

# Find Eulerian Tour
#
# Write a function that takes in a graph
# represented as a list of tuples
# and return a list of nodes that
# you would follow on an Eulerian Tour
#
# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]

私が書いたコードは以下です。それは超エレガントではありませんが、仕事をしているようです.

def getCurPoint(points, curPoint):
    for pair in range(len(points)):
        if curPoint in points[pair]:
            for i in points[pair]:
                if i != curPoint:
                    points.pop(pair)
                    return [curPoint] + getCurPoint(points, i)
    return []

def takeTour(graph):
    point = graph[0][0]
    criticals = []
    points = []
    for pair in range(len(graph)):
        if point in graph[pair] and len(criticals) <= 1:
            criticals.append(graph[pair])
        else:
            points.append(graph[pair])

    stops = [point]

    curPoint = criticals[0][1]

    stops += getCurPoint(points, curPoint)

    for x in criticals[1]:
        if x != point:
            stops.append(x)

    stops.append(point)

    return stops

問題は、コードを送信したときに、次の場合を除いてすべてのテスト ケースに合格したことです。graph = [(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7), (5, 9), (2, 4), (0, 4), (2, 5), (3, 6), (8, 9)]

なぜそのテストに失敗するのか考えていますか? (そして、このコードをよりエレガントにするためのヒントがあれば、ぜひ聞かせてください!)

4

1 に答える 1

13

にはバックトラック機構がありませんgetCurPoint()。これは、アルゴリズムがグラフ内を移動することがわかった最初のエッジを取得し、すべてのノードを通過せずに行き止まりにつながる可能性のあるパスを構築していることを意味します。

これはまさにあなたの例で起こっていることです。アルゴリズムは node から始まり、 node0に到達します1。このノードは、旅行を続けるための 3 つのエッジ ( (1, 5)、(1, 7)、(1, 6)) を提供しますが、そのうちの 1 つはオイラー ツアーを完了することなく行き止まりになります。残念ながら、グラフ定義にリストされている最初のエッジは間違ったパスであり、ノード、、および(1, 5)に到達する機会がありません。637

私の断言を確認するには、グラフの特定の定義を でエッジを反転するように変更してみて(1, 5)、(1, 7)アルゴリズムがすべてのノードを正しくリストする方法を確認してください。

手伝いましょうか

まず、これらの問題を自分で解決できるようにするには、常に図を作成し (ファインマンを満足させるだけでなく)、その図でアルゴリズムに従うようにしてください。これらのケースは簡単に描くことができ、アルゴリズムが正しくないことが明らかになり、その理由がわかるかもしれません。

第二に、この演習はバックトラックに関するものです。これが何であるか知っていますか？そうでない場合は、この単語をグーグルで検索するか、stackoverflow 検索ボックスで検索することもできます。ウィキペディアにもそれに関する優れた記事があります。

最後に、あなたのコーディング スタイルについてアドバイスできます。それらは個人的なものと考えて、現在のニーズに合うと思われるものを選んでください。

可能であれば：

  • for x in range(len(graph)):後でのみ使用する場合は避けてくださいgraph[x]。Python は、非常に洗練された代替ソリューションを提供しますfor edge in graph:。そして、反復している要素のインデックスが本当に必要な場合は、エレガントに行くことができます: for i, edge in enumerate(graph):

  • ifで孤独を 含む3行の構成（2回使用した）を避けてくださいfor：

    for x in criticals[1]:
    if x != point:
        stops.append(x)

    明示的で小さい方を好む:

    node_a, node_b = critical_edges[1] 
stops += [node_a] if node_b == node else [node_b]

  • 重要度の低いコードの装飾スタイルのコメント:

    • 変数、関数名、およびメソッド名には Java CamelCase を使用しないでください。Python には、変数名にアンダースコア付きの小文字を使用することを好むスタイリングに関するPEP8があります。
    • 'point' を 'node' に名前変更して、グラフ上でより広く使用されている語彙に固執する
    • 'pair' を 'edge' に名前を変更して、変数の型ではなく意味を説明する名前を付けます (ただし、ハンガリー表記と呼ばれるもので両方の情報を混合することを考えることができます)

装飾的なコメントを適用すると、たとえば次のようgetCurPointに名前が に変更されますget_next_nodes。

  • variable_with_underscore の代わりに CamelCase とPoint->nodes前に説明したように、
  • ノードのリストを返すため、複数形
  • 「cur」は「next」に名前が変更されました。これは、次のノードを取得するためです。

より Pythonic な方法でコードを書き直したサンプル

これは単なる書き直しであり、以前のバグは常に存在することに注意してください。get_next_nodes()関数がどのように変化したかを見てみましょう。

def get_next_nodes(edges, cur_node):
    connected_edges = [x for x in edges
                       if cur_node in x]
    if connected_edges:
        a, b = connected_edges[0]
        next_node = b if a == cur_node else a
        edges.remove(connected_edges[0])
        return [cur_node] + get_next_nodes(edges, next_node)
    return []

def take_tour(graph):
    start_node = graph[0][0]
    critical_edges = []
    nodes = []
    for edge in graph:
        if start_node in edge and len(critical_edges) < 2:
            critical_edges.append(edge)
        else:
            nodes.append(edge)

    second_node = critical_edges[0][1]
    stops = [start_node] + get_next_nodes(nodes, second_node)

    a, b = critical_edges[1]
    stops += [a] if b == start_node else [b]
    return stops + [start_node]

さて、アルゴリズムにはさらに問題があります

  • スクリプトは非オイラー グラフにどのように反応しますか? アルゴリズムは、間違ったノード リストから紛らわしい例外まで、さまざまな結果を出力します。例外が回避されない場合は、適切な混乱のない例外を発生させる必要があります。次のグラフでアルゴリズムを試してください。

    • 非オイラー:

      [(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7), (5, 9), ( 2, 4), (2, 5), (3, 6), (8, 9)]

    • 非オイラー:[(0, 1), (0, 3)]

    • オイラー:[(0, 0)]
    • 非オイラー:[]

  • のリストに 3 つのノードを手動で追加していますtake_tour。はるかに少ないコードで、はるかにエレガントなソリューションがあります!

  • なぜtake_tour開始エッジと一緒に終了エッジを選択するのですか? あなたは間違ったものを選ぶかもしれません！多肢選択式の最初の選択が間違っている可能性があることがわかりました。このグラフを試してください:

    • オイラー: [(0, 1), (0, 1), (0, 2), (0, 2)]、正しい結果は です[0, 1, 0, 2, 0]。

最後に、あなたに正しい答えを出させてください

この単純な再帰コードは、解決しようとした最初の問題に答えます。

getCurPointイニシャルがバックトラックを行うことからそれほど遠くないことに注意してください. 唯一の追加は、for盲目的に最初のソリューションを取得するのではなく、すべての可能なソリューションで解析するループの導入です。

ただし、バックトラックを許可するには、関数が現在のパス計算を終了できる必要があります。これはFalse、パスが見つからない場合に値が返されるようにすることで行われます。False次に、子関数呼び出しから親関数への再帰が繰り返され、forループのおかげで別のエッジを試すことができるまで再帰を効果的に解きます。

getCurPointとをマージできることがわかりますtake_tour。これにより、新しい に 2 つの機能が隠されているという追加の利点が得られますtake_tour。

  • オイラー パス (同じノードで開始および終了する必要があるオイラー ツアーとは異なります) を表示できます。
  • 別の開始ノードにパスを表示させることに興味がある場合は、開始ノードを提供できます。

コードは次のとおりです。

def take_tour(graph, node_start=None, cycle_only=True):
    if len(graph) == 0:
        if node_start is None:
            return []
        return [node_start]

    node_start = graph[0][0] if node_start is None else node_start

    for chosen_edge in [x for x in graph if node_start in x]:
        (node_a, node_b) = chosen_edge
        path = take_tour([e for e in graph if e != chosen_edge],
                         node_b if node_start == node_a else node_a,
                         cycle_only=False)
        if path is not False and (not cycle_only or node_start == path[-1]):
            return [node_start] + path
    return False

他の簡単な演習を探している場合は、ここに 2 つの簡単から中程度の質問があります。

  • take_tour可能なすべてのツアー/パスのリストを返すようにどのように変更しますか?
  • take_tour可能なすべてのツアー/パスのイテレータに変換できますか? (要求があった場合にのみ次のパスを計算する巧妙な反復子)。

これが十分に教訓的だったことを願っています。

于 2012-11-17T23:47:09.907 に答える