最简单的解决没有可变性迷宫的方式 [英] Simplest way to solve a maze without mutability

问题描述

学习一些Scala和计划生育的好处后，我重新实现我的一些previous CS分配，以更好地理解FP。不过，我有一个任务，这似乎不切实际与计划生育实施（或至少是平凡的翻译）。

After learning some Scala and the benefits of FP, I am reimplementing some of my previous CS assignments to better understand FP. However, I got to one assignment that seems impractical to implement with FP (or at least trivially translate).

在解决一个简单的二维迷宫，有必要记住哪些节点已被访问。然而，如果没有共享的状态，怎么能每次递归调用知道什么节点上的其他递归调用已研究？我可以通过迷宫作为参数传递给每一个递归调用，并返回一个包含去过的地方一个新的迷宫，但似乎过于密集计算来复制整个迷宫每次递归调用。将一个更先进的方法需要实现一个不可变的迷宫求解？

When solving a simple 2D maze it is necessary to remember which nodes have been visited. However, without shared state, how can each recursive call know what nodes the other recursive calls have examined? I could pass the maze as a parameter to each recursive call and return a new maze containing the places visited, but that seems too computationally intensive to copy an entire maze each recursive call. Would a more advanced approach be required to implement an immutable maze solver?

推荐答案

您可以通过围绕一组包含访问节点（或它们的ID /名称，如果节点本身具有可比性的在您的设置相等）。添加项目到一个不变的一套一般需 O（log n）的，所以没有检查一个元素是否包含在一组。所以，这不是复制迷宫显著便宜。

You can pass around a set containing the visited nodes (or their ids/names if nodes themselves are comparable for equality in your setup). Adding items to an immutable set generally takes O(log n), so does checking whether an element is contained in the set. So that's significantly cheaper than copying the maze.

这篇关于最简单的解决没有可变性迷宫的方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！