贪婪算法和时间复杂度#2
我们有一颗正在滴答作响的炸弹，可能会爆炸。这个炸弹有n个开关，可以上下移动。这些开关的某些组合会触发炸弹，但只有一种组合会使其失效。
我们的任务是将开关从当前位置移动到使炸弹失效的位置，同时不引爆炸弹。这些开关又大又笨拙，所以我们一次只能移动一个开关。
假设我们有n=4个开关，当前在^vvv位置。我们需要把它们放到^v^^位置。禁止的位置是vvv^、^vv^、^v^v和^^v。
a.)我必须手绘这个，并找到解决任务的开关动作的最短序列-结果是4 ...and我找到了两个这样的序列，如果我是对的……
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)回答 2
Stack Overflow用户
发布于 2019-05-30 08:46:44
手头的任务是在图中找到最短路径。为此，有一种典型的方法，即广度优先搜索算法(https://en.wikipedia.org/wiki/Breadth-first_search)。
没有真正需要详细介绍这是如何实现的，因为它可以在其他地方阅读到更详细的内容，并且比我在StackOverflow答案中做这件事要好得多。
但可能需要解释的是，您手头的开关组合是如何用图形表示的。
假设您只有两个交换机。然后你就会得到这个图：
^^---^v
| |
| |
v^---vv如果你的起始位置是^^，你的结束(分解)位置是vv，而位置^v是一个爆炸位置，那么你的图形就会缩减为：
^^ ^v
|
|
v^---vv在这个小示例中，最短路径是显而易见且简单的。
手边的图形很容易在2D中勾画出来，每个维度(x和y)代表其中一个开关。如果您有多个开关，则只需为每个开关添加一个维度。对于三个交换机，如下所示：
^^^--------^^v
|\ |\
| \ | \
| \ | \
| \ | \
| ^v^--- | --^vv
| | | |
| | | |
v^^--------v^v |
\ | \ |
\ | \ |
\ | \ |
\| \|
vv^--------vvv如果禁止位置^^v、v^^和vv^，则此图缩减为：
^^^ ^^v
\
\
\
\
^v^--------^vv
|
|
v^^ v^v |
\ |
\ |
\ |
\|
vv^ vvv这已经表明了清晰的方法，广度优先搜索将很容易找到它。然而，它只对许多维度/开关变得有趣。
当然，为更多的尺寸/开关绘制此图会让人感到困惑(查看4D的tesseract)。但并不一定要有一个视觉图像。一旦你以一般的方式编写了创建2D和3D图形的算法，它就可以轻松地扩展到n个维度/开关，而不会增加任何复杂性。
Stack Overflow用户
发布于 2019-05-31 03:05:19
start = 8
target = 11
forbidden = {1: -1 , 9: -1, 10: -1, 14: -1}
dimensions = 4
def distance(start, target, forbidden, dimensions):
stack1 = []
stack1.append(start)
forbidden[start] = -1
while(len(stack1) > 0):
top = stack1.pop()
for i in range(dimensions):
testVal = top ^ (1 << i)
if testVal is target:
forbidden[testVal] = top
result = [testVal]
while testVal is not start:
testVal = forbidden[testVal]
result.insert(0, testVal)
return result
if testVal not in forbidden:
forbidden[testVal] = top
stack1.append(testVal)
return [-1]
print(distance(start, target, forbidden, dimensions))这是我为你问题中的例子编写的代码。我没有使用位，而是使用基数为10的数字来表示代码。被禁止的代码被映射到hashmap，在找到目标后使用该hashmap向上跟踪路径。我使用堆栈来跟踪要尝试的代码。每次通过while循环时，最后添加的代码都会弹出，并将其未访问的邻居添加到堆栈中。重要的是，为了防止循环，堆栈上或以前见过的代码被添加到禁用节点列表中。当第一次找到目标代码时，将调用早期返回，并通过hashmap跟踪路径。
此解决方案使用广度优先搜索，并在第一次找到目标时返回。这意味着它不保证从开始到目标的最短路径，但它确实保证了一条可用的工作路径。由于可能遍历所有可能的代码，且有2^维的节点数，因此该算法的时间复杂度也是O(2^n)
https://stackoverflow.com/questions/56367356
复制相似问题