我们有一颗正在滴答作响并可能爆炸的炸弹。这个炸弹有 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)
最佳答案
手头的任务是在图中寻找最短路径。为此，有一种典型的方法，即广度优先搜索算法 (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 维/开关，而不会增加任何复杂性。
关于python-3.x - 贪心算法和时间复杂度#2，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56367356/