深度优先搜索逻辑递归函数-解网

问：

我有一些代码，我模拟了一个玩家试图在地牢爬行游戏中逃离地牢。我想使用深度优先搜索来测试玩家是否能成功。

在地牢类中，我的方法出了点问题，应该测试地牢的每条路径是否都会成功：以下是我的打印声明：

self = <main_test.GraphTest testMethod=test_can_all_paths_make_it>

    def test_can_all_paths_make_it(self):
        dungeon = self.create_dungeon()
>       self.assertEqual(dungeon.can_all_paths_make_it(Player(11)), False)
E       AssertionError: True != False

coderbyte-tests/main_test.py:140: AssertionError
----------------------------- Captured stdout call -----------------------------
Checking node: <graph.Monster object at 0x7f82158aa190>, Current Health: 11
Checking neighbor: <graph.Monster object at 0x7f82158aa130>
Encountered Monster: <graph.Monster object at 0x7f82158aa130>
Checking node: <graph.Monster object at 0x7f82158aa130>, Current Health: 7
Checking neighbor: <graph.Monster object at 0x7f82158aa040>
Encountered Monster: <graph.Monster object at 0x7f82158aa040>
Checking node: <graph.Monster object at 0x7f82158aa040>, Current Health: 2
Checking neighbor: <graph.Treasure object at 0x7f8215914850>
Processing neighbor: <graph.Treasure object at 0x7f8215914850>
Checking node: <graph.Treasure object at 0x7f8215914850>, Current Health: 2
Found Treasure!

# Will any path make it to the end? Can they choose randomly and always make it?
    def can_all_paths_make_it(self, player: Player) -> bool:
      def dfs(node, current_health):
        if isinstance(node, Treasure):
          return True

        if current_health <= 0:
          return False
        
        if node is not node.next:
          return False
        
        for neighbor in node.next:
                if isinstance(neighbor, Monster):
                    # Simulate a battle with the monster
                    new_health = current_health - neighbor.damage
                    if not dfs(neighbor, new_health):
                        return False
                elif not dfs(neighbor, current_health):
                    return False

        return True

      return dfs(self.monster, player.health)

似乎逻辑有点不对劲，因为有些测试用例失败了。（测试用例不会确切地显示我关闭的位置，除了在输出 False 时期望 True）。

我知道，为了测试是否所有路径都能成功，我需要考虑死胡同、生命值的损失以及它们是否在宝藏中。

出了什么问题，我该如何解决？

以下是测试用例

import unittest

从图表导入怪物，宝藏，玩家，地牢

类 GraphTest（unittest.测试用例）：

# a(3) -> b(4) -> c(5) -> treasure
def create_dungeon(self) -> Dungeon:
    a = Monster("a", 3)
    b = Monster("b", 4)
    c = Monster("c", 5)
    treasure = Treasure()
    a.append_monster(b)
    b.append_monster(c)
    c.append_treasure(treasure)

    return Dungeon(a)

# a(3) -> b(4)  c(5) -> treasure
def create_dungeon2(self) -> Dungeon:
    a = Monster("a", 3)
    b = Monster("b", 4)
    c = Monster("c", 5)
    treasure = Treasure()
    a.append_monster(b)
    c.append_treasure(treasure)

    return Dungeon(a)

# a(1) -> b(4)
#   |      |
#   v      v
# c(2) -> d(1) -> treasure
def create_dungeon3(self):
    a = Monster("a", 1)
    b = Monster("b", 4)
    c = Monster("c", 2)
    d = Monster("d", 1)
    treasure = Treasure()
    a.append_monster(b)
    a.append_monster(c)
    b.append_monster(d)
    c.append_monster(d)
    d.append_treasure(treasure)

    return Dungeon(a)

# a(1) -> b(4) -> e(1)
#   |      |
#   v      v
# c(2) -> d(1) -> treasure

'''
Probability review: Just because there are 2 different possiblilites does not 
mean that they are equal probability. For example, on any given day, there could be 
rain or no rain. That doesn't imply that rain has a 50% chance.

In this case, there are 3 different paths:
a->c->d->treasure, a->b->d->treasure, and a->b->e. 

Here, a->c->d->tresure has a 50% chance of happening, a->b->e is 25%, and a->b->d->treasure is 25%. 
An easy way to think about it that the probability of A reaching C is 50% and C reaching D is 100%
and D reaching Treasure is 100%. Overall, it would be 50% chance to do A->C->D->Treasure.
'''
def create_dungeon4(self):
    a = Monster("a", 1)
    b = Monster("b", 4)
    c = Monster("c", 2)
    d = Monster("d", 1)
    e = Monster("e", 1)
    treasure = Treasure()
    a.append_monster(b)
    a.append_monster(c)
    b.append_monster(d)
    c.append_monster(d)
    b.append_monster(e)
    d.append_treasure(treasure)

    return Dungeon(a)

# a(1) -> b(5) -> e(1) 
#   |      |       |       
#   v      v       v        
# c(2) -> d(7) -> f(2) -> treasure
# optimal -> a -> b -> e -> f
def create_dungeon5(self):
    a = Monster("a", 1)
    b = Monster("b", 5)
    c = Monster("c", 2)
    d = Monster("d", 7)
    e = Monster("e", 1)
    f = Monster("f", 2)
    treasure = Treasure()
    a.append_monster(b)
    a.append_monster(c)
    b.append_monster(e)
    b.append_monster(d)
    c.append_monster(d)
    d.append_monster(f)
    e.append_monster(f)
    f.append_treasure(treasure)

    return Dungeon(a)

# a(1) -> b(5) -> e(1) ------
#   |      |       |        |
#   v      v       v        v
# c(2) -> d(7) -> f(2) -> treasure
# optimal -> a -> b -> e -> f
def create_dungeon6(self):
    a = Monster("a", 1)
    b = Monster("b", 5)
    c = Monster("c", 2)
    d = Monster("d", 7)
    e = Monster("e", 1)
    f = Monster("f", 2)
    treasure = Treasure()
    a.append_monster(b)
    a.append_monster(c)
    b.append_monster(e)
    b.append_monster(d)
    c.append_monster(d)
    d.append_monster(f)
    e.append_monster(f)
    e.append_treasure(treasure)
    f.append_treasure(treasure)

    return Dungeon(a)

def test_can_at_least_one_path_make_it(self):
    dungeon = self.create_dungeon()
    self.assertEqual(dungeon.can_at_least_one_path_make_it(), True)
    
    dungeon = self.create_dungeon2()
    self.assertEqual(dungeon.can_at_least_one_path_make_it(), False)


def test_can_all_paths_make_it(self):
    dungeon = self.create_dungeon()
    self.assertEqual(dungeon.can_all_paths_make_it(Player(11)), False)

    dungeon = self.create_dungeon()
    self.assertEqual(dungeon.can_all_paths_make_it(Player(12)), True)

    dungeon = self.create_dungeon2()
    self.assertEqual(dungeon.can_all_paths_make_it(Player(7)), False)
    
    dungeon = self.create_dungeon3()
    self.assertEqual(dungeon.can_all_paths_make_it(Player(5)), False)

    dungeon = self.create_dungeon3()
    self.assertEqual(dungeon.can_all_paths_make_it(Player(6)), True)

    dungeon = self.create_dungeon4()
    self.assertEqual(dungeon.can_all_paths_make_it(Player(100)), False)

def test_probability_player_will_make_it(self):
    dungeon = self.create_dungeon()
    self.assertEqual(dungeon.probability_player_will_make_it(Player(12)), 1.0)

    dungeon = self.create_dungeon()
    self.assertEqual(dungeon.probability_player_will_make_it(Player(11)), 0.0)
    
    dungeon = self.create_dungeon2()
    self.assertEqual(dungeon.probability_player_will_make_it(Player(100)), 0.0)

    dungeon = self.create_dungeon3()
    self.assertEqual(dungeon.probability_player_will_make_it(Player(1)), 0.0)

    dungeon = self.create_dungeon3()
    self.assertEqual(dungeon.probability_player_will_make_it(Player(5)), 0.5)

    dungeon = self.create_dungeon3()
    self.assertEqual(dungeon.probability_player_will_make_it(Player(100)), 1.0)

    dungeon = self.create_dungeon4()
    self.assertEqual(dungeon.probability_player_will_make_it(Player(1)), 0.0)

    dungeon = self.create_dungeon4()
    self.assertEqual(dungeon.probability_player_will_make_it(Player(5)), 0.5)

    dungeon = self.create_dungeon4()
    self.assertEqual(dungeon.probability_player_will_make_it(Player(100)), 0.75)

def test_can_make_it(self):
    dungeon = self.create_dungeon5()
    self.assertEqual(dungeon.can_make_it(Player(9)), True)

    dungeon = self.create_dungeon5()
    self.assertEqual(dungeon.can_make_it(Player(8)), False)

    dungeon = self.create_dungeon6()
    self.assertEqual(dungeon.can_make_it(Player(7)), True)

    dungeon = self.create_dungeon6()
    self.assertEqual(dungeon.can_make_it(Player(6)), False)

对于我自己，我创建了这个打印声明 def can_all_paths_make_it（self， player： Player） -> bool： def dfs（节点，current_health）： print（f“检查节点：{node}，当前运行状况：{current_health}”）

    if isinstance(node, Treasure):
        print("Found Treasure!")
        return True

    if current_health <= 0:
        print("Player has lost all health!")
        return False

    if not isinstance(node.next, list):
        print("Invalid path: node.next is not a list")
        return False  # If node.next is not a list, it's not a valid path

    for neighbor in node.next:
        print(f"Checking neighbor: {neighbor}")

        if isinstance(neighbor, Monster):
            print(f"Encountered Monster: {neighbor}")
            # Simulate a battle with the monster
            new_health = current_health - neighbor.damage
            if not dfs(neighbor, new_health):
                return False
        elif not dfs(neighbor, current_health):
            return False

    return True

return dfs(self.monster, player.health)

python 算法数据结构深度优先搜索

如果我们不知道失败的测试用例是什么，或者其中应该发生什么，我们就无法真正帮助失败的测试用例。我们通常不会在这里为您“找到错误”;在发布之前，您应该 a）确定一个具体的、可重现的问题，b）通过仔细检查代码运行时发生的情况并寻找与您预期不同的内容来隔离问题发生的位置。

0赞 Karl Knechtel 11/13/2023

也就是说：我无法理解 .仔细想想那里的逻辑。为了尝试其余代码，我们需要假设不满足此条件，对吗？因此，我们对循环何时开始了解什么？这有意义吗？就此而言：似乎应该保存一个节点列表，因为它上有一个循环。右？节点列表可以与节点是同一个对象吗？if node is not node.next: return Falsenodenode.nextfor

0赞 trincot 11/13/2023

请提供代码以初始化您的代码返回错误结果的地牢状态。

0赞 user1984 11/13/2023

看起来你把 for 作为第一个参数传入。但正如其他人所说，你需要提供一个具体的例子和问题，否则，这将恶化为猜谜游戏。self.monsterdfsnode

1赞 Mike 'Pomax' Kamermans 11/14/2023

不要在评论中输入详细信息。把它们放在你的帖子中，这样每个人都可以看到它们。然后你可以评论说“我已经用结果更新了我的帖子”或类似的东西。

答：

1赞 trincot 11/14/2023 #1

存在以下几个问题：

if current_health <= 0当运行状况为零时，将计算结果为 True，但这仍然是可接受的运行状况。
生命值只会因邻近怪物的伤害而减少，而不会因第一个怪物的伤害而减少。您应该将该损坏逻辑移出循环，并将其应用于当前节点。
if node is not node.next:没有意义。此条件始终为 True。您需要测试死胡同if not node.next:

以下是更正后的代码：

    def can_all_paths_make_it(self, player: Player) -> bool:
        def dfs(node, current_health):
            if current_health < 0:  # the player died
                return False
            
            if isinstance(node, Treasure):  # bingo!
                return True

            if isinstance(node, Monster):  # have to fight
                current_health -= node.damage
 
            if not node.next:   # dead end
                return False

            return all(dfs(neighbor, current_health) 
                       for neighbor in node.next)

        return dfs(self.monster, player.health)

深度优先搜索逻辑递归函数

Depth First Search Logic Recursive Function

评论

评论