草庐IT

关于递归：避免Python的堆栈

codeneng 2023-03-28 原文

Avoiding Python's Stack

我正在尝试多种搜索算法来解决广义 AI 问题，其中之一是深度优先搜索。我已经将广度优先搜索、贪心搜索和 A* 搜索从它们的自然递归形式转换为迭代形式，但是在使用深度优先搜索 cleanly 时遇到了更多麻烦(尽管这并不超出我的能力，我不确定这样做的最pythonic方式，因此问题)。

我遇到了 CPython 的 1000 次递归调用限制，即使是一些中型问题。后继状态是延迟生成的(_generate_states 是生成器，而不是列表)，并且需要从初始状态开始的路径。

从使用调用堆栈到显式堆栈的最 Pythonic 方式是什么？堆栈中应该存储多少信息？回溯时(当没有状态返回非空列表时)，从堆栈前面弹出死信息的最佳方法是什么？

1
2
3
4
5
6
7
8
9
10
def dfs(initial, closed_set, goal, capacity):
    if initial == goal:
        return [initial]

    for state in _generate_states(initial, capacity):
        if state not in closed_set:
            result = dfs(state, [initial] + closed_set, goal, capacity)
            if result:
                return [state] + result
    return []

  • 我不知道有一种最 Pythonic 的方式，但我很好奇是否有其他人有比这更好的答案。应该存储多少信息的答案是"不超过算法工作所需的量"。
  • 只是一个小小的改进——如果你使用双端队列而不是列表，你可能会得到一个稍微快一点的堆栈。
  • @Omnifarious当我优化BF时也是这种情况，我存储了很多冗余路径(因为每个当前层节点都有相同的父路径)。我也很想知道处理这方面的最佳方法。
  • DFS 的非递归代码看起来应该与 BFS 几乎相同，除了您将使用堆栈而不是队列。
  • 我不得不承认我是多么讨厌"pythonic"这个词。

这里有一个解决方案，可以让生成器保持周围以保留所需的惰性属性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def dfs(initial, goal, capacity):
    # These three variables form the"stack".
    closed_set = {initial}
    stack = [initial]
    gens = [_generate_states(initial, capacity)]

    while stack:
        cur = stack[-1]
        gen = gens[-1]
        try:
            state = next(gen)
        except StopIteration:
            # This node is done
            closed_set.discard(cur)
            gens.pop()
            stack.pop()
            continue

        if state == goal:
            return stack

        if state not in closed_set:
            closed_set.add(state)
            stack.append(state)
            gens.append(_generate_states(state, capacity))

    return None

注意，路径是定位到目标时的栈，因为栈是到达当前节点所访问的节点的记录。

  • 您使用了未定义的 path。您的意思是改用 stack 吗？

我假设你知道如何使用堆栈迭代地实现 DFS(它与 BFS 基本相同，只是 LIFO 而不是 FIFO)，所以我将发布一些一般性提示。

  • 在迭代实现 DFS 时，您应该使用 collections.deque 作为堆栈，该堆栈针对快速追加和弹出元素进行了优化。
  • 您绝对应该为 closed_set 使用集合而不是列表。 (如果您想找到最短路径，也可以使用地图 {state: depth}。)
  • 为了跟踪路径，您可以创建一个package类，封装您的当前状态和对前一个状态的引用(基本上是状态的链接列表)，或者使用前驱状态的映射。

但不确定在这种情况下如何使用生成器，因此您的堆栈将容纳深度 x 个分支因子元素...或者您可以将生成器放在堆栈上，而不是实际的元素?只是一个想法...

  • deque 实际上只有 FIFO 需要。简单的旧列表对于 LIFO 是有效的； append() 或 pop() 不需要移动任何元素。

这就是我将如何创建迭代深度优先搜索的方法。它使用 candidate_states 作为接下来应该探索的状态堆栈。您可以使用 parents 字典重建从任何访问节点到初始节点的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def reconstruct_path(state, parents):
    path = []
    while state != None:
        path.append(state)
        state = parents[state]
    path.reverse()
    return path

def dfs(initial, goal):
    visited_states = set()
    candidate_states = [initial]
    parents = {initial: None}
    while len(candidate_states) > 0:
        cur_state = candidate_states.pop()
        if cur_state in visited_states: continue
        if cur_state == goal:
            return reconstruct_path(cur_state, parents)
        for state in _generate_states(cur_state):
            parents[state] = cur_state
            candidate_states.append(state)
    return None

  • 在编写 BFS 解决方案时，我使用了相同的字典技术。

Python关于spanclassnbspartificial-intelligencedepth-first-searchiterationpythonrecursion

有关关于递归：避免Python的堆栈的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. ruby-on-rails - RSpec:避免使用允许接收的任何实例 - 2

    我正在处理旧代码的一部分。beforedoallow_any_instance_of(SportRateManager).toreceive(:create).and_return(true)endRubocop错误如下:Avoidstubbingusing'allow_any_instance_of'我读到了RuboCop::RSpec:AnyInstance我试着像下面那样改变它。由此beforedoallow_any_instance_of(SportRateManager).toreceive(:create).and_return(true)end对此:let(:sport_

  3. Python 相当于 Perl/Ruby ||= - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Pythonconditionalassignmentoperator对于这样一个简单的问题表示歉意，但是谷歌搜索||=并不是很有帮助；)Python中是否有与Ruby和Perl中的||=语句等效的语句？例如:foo="hey"foo||="what"#assignfooifit'sundefined#fooisstill"hey"bar||="yeah"#baris"yeah"另外，类似这样的东西的通用术语是什么？条件分配是我的第一个猜测，但Wikipediapage跟我想的不太一样。

  4. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  5. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  6. python - 如何读取 MIDI 文件、更改其乐器并将其写回？ - 2

    我想解析一个已经存在的.mid文件，改变它的乐器，例如从“acousticgrandpiano”到“violin”，然后将它保存回去或作为另一个.mid文件。根据我在文档中看到的内容，该乐器通过program_change或patch_change指令进行了更改，但我找不到任何在已经存在的MIDI文件中执行此操作的库.他们似乎都只支持从头开始创建的MIDI文件。 最佳答案 MIDIpackage会为您完成此操作，但具体方法取决于midi文件的原始内容。一个MIDI文件由一个或多个音轨组成，每个音轨是十六个channel中任何一个上的

  7. 「Python｜Selenium｜场景案例」如何定位iframe中的元素？ - 2

    本文主要介绍在使用Selenium进行自动化测试或者任务时，对于使用了iframe的页面，如何定位iframe中的元素文章目录场景描述解决方案具体代码场景描述当我们在使用Selenium进行自动化测试的时候，可能会遇到一些界面或者窗体是使用HTML的iframe标签进行承载的。对于iframe中的标签，如果直接查找是无法找到的，会抛出没有找到元素的异常。比如近在咫尺的例子就是，CSDN的登录窗体就是使用的iframe，大家可以尝试通过F12开发者模式查看到的tag_name,class_name,id或者xpath来定位中的页面元素，会抛出NoSuchElementException异常。解决

  8. python ffmpeg 使用 pyav 转换 一组图像 到 视频 - 2

    2022/8/4更新支持加入水印水印必须包含透明图像，并且水印图像大小要等于原图像的大小pythonconvert_image_to_video.py-f30-mwatermark.pngim_dirout.mkv2022/6/21更新让命令行参数更加易用新的命令行使用方法pythonconvert_image_to_video.py-f30im_dirout.mkvFFMPEG命令行转换一组JPG图像到视频时，是将这组图像视为MJPG流。我需要转换一组PNG图像到视频，FFMPEG就不认了。pyav内置了ffmpeg库，不需要系统带有ffmpeg工具因此我使用ffmpeg的python包装p

  9. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  10. python - 是否可以使用 Ruby 或 Python 禁用 anchor /引用来发出有效的 YAML？ - 2

    是否可以在PyYAML或Ruby的Psych引擎中禁用创建anchor和引用(并有效地显式列出冗余数据)？也许我在网上搜索时遗漏了一些东西，但在Psych中似乎没有太多可用的选项，而且我也无法确定PyYAML是否允许这样做.基本原理是我必须序列化一些数据并将其以可读的形式传递给一个不是真正的技术同事进行手动验证。有些数据是多余的，但我需要以最明确的方式列出它们以提高可读性(anchor和引用是提高效率的好概念，但不是人类可读性)。Ruby和Python是我选择的工具，但如果有其他一些相当简单的方法来“展开”YAML文档，它可能就可以了。 最佳答案

随机推荐