在一种情况下，用于查找 Eulerian Tour 的 Python 代码不起作用.为什么? [英] Python code to find Eulerian Tour does not work in one case. Why?

问题描述

我正在尝试解决 Udacity 上的一个问题，如下所述:

I am trying to solve a problem on Udacity described as follows:

# 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]

我写的代码如下.它不是超级优雅，但似乎可以胜任.

The code I wrote is below. It's not super elegant, but it seems to do the job.

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)]

The issue is that when I submitted the code it passed every test case except when 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)]

知道为什么它会失败该测试吗?(如果您有关于如何使这段代码更优雅的提示，我很想听听他们的意见！)

Any idea why it would fail that test? (And if you have tips on how to make this code more elegant I would love to hear them!)

推荐答案

getCurPoint() 中没有回溯机制.这意味着您的算法正在采用图中找到的第一条边，构建一条可能导致死胡同的路径，而无需遍历所有节点.

You have no backtracking mecanism in getCurPoint(). This means that your algorithm is taking the first edge found to travel in the graph, building a path that may lead to dead ends without having traversed all nodes.

这正是您的示例所发生的情况.您的算法将从节点 0 开始到节点 1.该节点提供 3 条边来继续您的旅行(分别是 (1, 5)、(1, 7)、(1, 6)) ，但其中之一将导致没有完成欧拉旅行的死胡同.不幸的是，图形定义中列出的第一条边 (1, 5) 是错误的路径，不会让您有任何机会到达节点 6, 3 和 7.

This is exactly what is happening with your example. Your algorithm will start from node 0 to get to node 1. This node offer 3 edges to continue your travel (which are (1, 5), (1, 7), (1, 6)) , but one of them will lead to a dead end without completing the Eulerian tour. Unfortunately the first edge listed in your graph definition (1, 5) is the wrong path and won't let you any occasion to reach nodes 6, 3, and 7.

要检查我的肯定，您可以尝试将图的给定定义更改为使用 (1, 7) 反转边 (1, 5)，然后查看您的算法将如何正确列出所有节点.

To check my affirmation, you could try to change the given definition of the graph to invert edges (1, 5) with (1, 7), and see how your algorithm will then list all nodes correctly.

我能帮上什么忙

首先，为了帮助你自己解决这些问题，你应该总是制作图表(不仅仅是为了让 Feynman 开心)，并尝试在图表上遵循你的算法.这些情况很容易画出来，很明显算法不正确，你可能会发现原因.

First, to help you solve yourself these issues, you should always make diagrams (and not only to make Feynman happy), and try to follow your algorithm on the diagram. These cases are easy to draw, and it will become clear that the algorithm is not correct, and you might spot why.

第二，这个练习是关于回溯.你知道这是什么吗 ?如果没有，你可以尝试谷歌搜索这个词，甚至在 stackoverflow 搜索框中搜索它，维基百科也有一篇很好的文章.

Second, this exercise is about backtracking. Do you know what this is ? If not, you can try googling this word or even search it here in stackoverflow search box, and wikipedia has a good article on that also.

最后，我可以给你一些关于你的编码风格的建议.请将它们视为个人的，并采取适合您当前需求的方式:

At last, I can give you some advice on your coding style. Please consider them as personal and take what seems to suit your current needs:

如果可能:

• 避免 for x in range(len(graph)): 如果你只使用 graph[x] 之后.Python为图中的边提供了一个非常优雅的替换解决方案:.如果你真的需要您正在迭代的元素的索引，您可以选择优雅的:for i, enumerate(graph) 中的边:

• 避免你的 3 行结构(你用过两次)在一个单独的 iffor:

• avoid for x in range(len(graph)): if you'll use only graph[x] after. Python offers a very elegant replacement solution for edge in graph:. And if you really need the index of the element you are iterating, you could go for the elegant: for i, edge in enumerate(graph):

• avoid your 3 lines construct (that you've used twice) involving a lonely if in a for:

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

更喜欢显式的、更小的:

prefer explicit, and smaller:

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

不太重要的代码装饰风格备注:

less important code cosmetic style remarks:

• 对于变量、函数名和方法名，避免使用 java CamelCase，python 有一个PEP8 上更喜欢使用带下划线的小写变量名称的样式.
• 将点"重命名为节点"以坚持使用图上更广泛的词汇
• 将 'pair' 重命名为 'edge' 以获得对什么的描述性命名变量的含义而不是它的类型(尽管你可以想到在所谓的匈​​牙利符号)
中混合这两种信息

• avoid java CamelCase for variable, function name and method names, python has a PEP8 on styling that prefer variable names to use lower case with underscores.
• rename 'point' to 'node' to stick to wider used vocabulary on graph
• rename 'pair' to 'edge' to get a descriptive naming of what is the meaning of your variable rather than its type (although you could think of mixing both info in what is called Hungarian Notation)

应用装饰性评论，例如，我们将 getCurPoint 重命名为 get_next_nodes，其中:

Applying the cosmetic remarks, we'll have for example getCurPoint renamed to get_next_nodes, with:

• variable_with_underscore 而不是 CamelCase 和 Point-> nodes 如前所述，
• 复数，因为它将返回一个节点列表
• 'cur' 被重命名为 'next' 因为，它是关于获取下一个节点.

以更 Pythonic 的方式重写代码的示例

请注意，这只是重写，之前的错误始终存在.看看 get_next_nodes() 函数是如何改变的:

Please note that this is only a rewrite, and that the previous bug is always present. Take a look at the get_next_nodes() function how it changed:

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]

现在，您的算法存在更多问题

• 你的脚本应该如何对非欧拉图做出反应?您的算法将输出各种各样的结果，从错误的节点列表到令人困惑的异常.如果不避免异常，则应引发适当的非混淆异常.用这些图试试你的算法:

• How should your script react to non Eulerian graph ? Your algorithm will output a broad variety of results, ranging from wrong node list, to confusing exception. A proper non-confusing exception should be raised if exception is not to be avoided. Try your algorithm with these graph:

• 非欧拉:

• non-Eulerian:

[(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), (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)]

您正在 take_tour 的列表中手动添加 3 个节点.有一个更优雅的解决方案，代码更少！

you are adding by hand 3 nodes in your list in take_tour. There is a much more elegant solution, with much less code!

为什么要在 take_tour 中选择结束边和起始边?你可能选错了！您看到选择多项选择中的第一个可能是错误的.试试这个图:

why are you picking a finishing edge in take_tour along with the starting edge ? You might pick the wrong one ! you saw that taking the first of multiple choice could be wrong. Try this graph:

• 欧拉:[(0, 1), (0, 1), (0, 2), (0, 2)]，正确的结果应该是[0, 1, 0, 2, 0].

• Eulerian: [(0, 1), (0, 1), (0, 2), (0, 2)], the correct result should be [0, 1, 0, 2, 0].

最后，让我给你一个正确的答案

这个简单的递归代码将回答您试图解决的最初问题.

This simple recursive code will answer the initial problem you tried to solve.

请注意最初的 getCurPoint 是如何进行一些回溯的.唯一的添加是引入了 for 循环，它将解析所有可能的解决方案，而不是盲目地采取第一个.

Please note how the the initial getCurPoint is not far from doing some backtracking. The only addition is the introduction of the for loop that will parse in all possible solution instead of blindly taking the first one.

但是为了允许回溯，该函数必须能够退出当前路径计算.这通过允许在找不到路径的情况下返回 False 值来完成.False 然后将从子函数调用重新执行到父函数，有效地取消递归直到它可以尝试另一个边缘，这要归功于 for 循环.

But to allow backtracking, the function must be able to quit current path calculation. This is done by allowing False value to be returned in cases where no path are found. False will then be repercuted from child function call to parent function, effectively un-tying the recursion until it can try another edge thanks to the for loop.

您会注意到您可以合并 getCurPoint 和 take_tour.这增加了在新的 take_tour 中隐藏 2 个功能的好处:

You'll notice that you can merge getCurPoint and take_tour. This gives the added benefice to have 2 features hidden in the new 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 个简单到中等的问题，这些问题悬而未决，可以一次性回答:

If you are look for some other simple exercise, here are 2 easy to medium questions that are left open and that could be answered in one go:

• 您将如何修改 take_tour 以返回所有可能的游览/路径的列表?
• 你能在所有可能的游览/路径的迭代器中转换 take_tour 吗?(一个聪明的迭代器，只会根据请求计算下一条路径).

• how would you modify take_tour to return a list of all possible tour/paths ?
• and would you be able to transform take_tour in an iterator of all possible tour/paths ? (a clever iterator that would compute next path only upon request).

我希望这足够说教了.

这篇关于在一种情况下，用于查找 Eulerian Tour 的 Python 代码不起作用.为什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！