找到Eulerian Tour的Python代码在一个案例中不起作用.为什么？

Question

我正在尝试解决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)]

知道为什么它会失败那个测试？(如果你有关于如何使这段代码更优雅的提示,我很乐意听到它们!)

Answer 1

你没有回溯机制getCurPoint().这意味着您的算法正在获取在图中传播的第一条边,构建一条可能导致死角但不遍历所有节点的路径.

这正是您的示例所发生的事情.您的算法将从节点0开始到达节点1.这个节点提供了3个边继续你的行程(这是(1, 5),(1, 7),(1, 6)),但他们中的一个将导致死胡同而不完成欧拉环游.不幸的是在图形中定义列出的第一个边缘(1, 5)是走错了路,不会让你在任何场合,以达到节点6,3和7.

要检查我的肯定,你可以尝试更改图形反转边给定的定义(1, 5)与(1, 7)时间,然后看看你的算法将然后正确列出的所有节点.

我该怎么帮忙

首先,为了帮助您解决这些问题,您应该始终制作图表(而不仅仅是让Feynman满意),并尝试在图表上遵循您的算法.这些案例很容易绘制,很明显算法不正确,你可能会发现原因.

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

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

如果可能:

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

• 避免你的3行构造(你曾经使用过两次)涉及一个孤独if的 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

如果你正在寻找一些其他简单的练习,这里有两个容易中等的问题,这些问题是开放的,可以一次性回答:

• 如何修改take_tour以返回所有可能的旅程/路径的列表？
• 你能够take_tour在所有可能的旅程/路径的迭代器中进行转换吗？(一个聪明的迭代器,只在请求时计算下一个路径).

我希望这足够说教.