python-3.x - 贪心算法和时间复杂度#2

Question

我们有一颗正在滴答作响并可能爆炸的炸弹。这个炸弹有 n 个开关，可以向上或向下移动。这些开关的某些组合会触发炸弹，但只有一种组合会使其失效。

我们的任务是将开关从当前位置移动到使炸弹失效的位置，同时不会引爆它。这些开关又大又笨拙，所以我们一次只能移动一个开关。

比方说，我们有 n = 4 个当前位置 ^vvv 的开关。我们需要让他们到达位置 ^v^^。禁止的位置是 vvv^、^vv^、^v^v 和 ^^^v。

a.) 我必须手工绘制它并找到解决任务的最短开关 Action 序列 - 我得到的结果是 4 ...我找到了两个这样的序列，如果我是对的......

b.) 这就是它变得困难的地方 - 编写一个代码来回答上述问题(最短的序列和多少)。代码应该被通用化，以便它可以与其他数量的开关和其他起始、目标和禁止组合一起工作；有针对性和禁止的组合可能有多个，甚至更少。我们唯一确定的是开关只有两个位置。它还应提供所需条件不可用的可能性；在这种情况下，程序当然应该告诉。

c.) 接下来的问题是代码的时间复杂度，但现在我想我就到此为止吧......

我用“0”和“1”代替，因为这样更容易想象。

所以我的方法是一种贪心算法(我认为)- 起始位置，你考虑所有可能的(允许的)位置，你忽略禁止的位置，然后选择位置序列具有的位置与我们的目标序列差异最小。

我尚未编写代码的关键部分，这是我需要帮助的部分。

all_combinations = ['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011' , '1100', '1101', '1110', '1111']


def distance (position1, position2):
     distance = 0
     for i in range (len (position1)):
         if position1 [i]! = position2 [i]:
             distance + = 1
     return distance


def allowed_positions (current, all_combinations):
     allowed = set ()
     for combination and all combinations:
         if the distance (current, combination) == 1:
             allowed.add (combination)
     return allowed


def best_name (current, all_combinations, target):
     list = []
     for option and permitted_mood (current, all_combinations):
         list.append (distance (option, target), option)

Answer 1

手头的任务是在图中寻找最短路径。为此，有一种典型的方法，即广度优先搜索算法 (https://en.wikipedia.org/wiki/Breadth-first_search)。

没有真正需要深入了解这是如何完成的细节，因为它可以在其他地方更详细地阅读，并且比我在 StackOverflow 答案中所做的解释要好得多。

但可能需要解释的是您手头的开关组合是如何用图表表示的。

假设您只有两个开关。然后你就有了这张图:

^^---^v
|     |
|     |
v^---vv

如果你的起始位置是^^，结束(化解)位置是vv，而^v位置是爆炸位置，然后你的图表被简化为:

^^   ^v
|       
|       
v^---vv

在这个小例子中，最短路径显而易见且简单。

手头的图形很容易以二维方式绘制出来，每个维度(x 和 y)代表一个开关。如果您有更多开关，则只需为每个开关添加一个维度。对于三个开关，这看起来像这样:

^^^--------^^v
 |\         |\
 | \        | \
 |  \       |  \
 |   \      |   \
 |   ^v^--- | --^vv
 |    |     |    |
 |    |     |    |
v^^--------v^v   |
  \   |      \   |
   \  |       \  |
    \ |        \ |
     \|         \|
     vv^--------vvv

如果位置 ^^v、v^^ 和 vv^ 被禁止，则此图将简化为:

^^^        ^^v
  \           
   \           
    \           
     \           
     ^v^--------^vv
                 |
                 |
v^^        v^v   |
             \   |
              \  |
               \ |
                \|
     vv^        vvv

它已经显示出清晰的路径，广度优先搜索将很容易找到它。不过，它只对许多维度/开关变得有趣。

为更多维度/开关绘制此图当然会令人困惑(查找 4D 超立方体)。但不一定要有视觉图像。一旦您编写了以通用方式在 2D 和 3D 中创建图形的算法，它就可以轻松扩展到 n 维/开关，而不会增加任何复杂性。