BFS和DFS算法在背包问题中的比较

Question

BFS和DFS算法在背包问题中的比较

pythonpython-3.xalgorithmknapsack-problem

3

我对Python还比较新，我的任务要求我比较算法的时间和内存使用情况。

我已经编写了两个算法并运行了它们。我能够测量使用的时间，但无法找到知道使用了多少空间的方法。我也不确定问题是要求我根据一般的BFS和DFS计算还是根据我编写的代码计算。

比较算法所用时间的差异。

比较算法在某一时刻所使用的内存空间。

为了获取时间，我使用了 start_time = time.time() 和 end = time.time()。

BFS algorithm
0.0060007572174072266s 
DFS algorithm
0.005002260208129883s

如果我要计算基于我的代码所使用的内存空间，该怎么做呢？也许我只是困惑了，但问题的措辞让我感觉需要运行两个算法并比较它们的性能以此来衡量。

代码:

BFS :

def knapsack_bfs(items, max_weight):
    queue = deque()
    root = Node(-1, 0, 0, [])
    queue.append(root)

    max_benefit = 0
    best_combination = []

    while queue:
        current = queue.popleft()

        if current.level == len(items) - 1:
            if current.benefit > max_benefit:
                max_benefit = current.benefit
                best_combination = current.items
        else:
            next_level = current.level + 1
            next_item = items[next_level]

            include_benefit = current.benefit + next_item.benefit
            include_weight = current.weight + next_item.weight

            if include_weight <= max_weight:
                include_node = Node(next_level, include_benefit,
                                    include_weight, current.items + [next_item.id])
                if include_benefit > max_benefit:
                    max_benefit = include_benefit
                    best_combination = include_node.items
                queue.append(include_node)

            exclude_node = Node(next_level, current.benefit,
                                current.weight, current.items)
            queue.append(exclude_node)

    return max_benefit, best_combination

DFS:

def knapsack_dfs(items, max_weight):
    queue = []
    root = Node(-1, 0, 0, [])
    queue.append(root)

    max_benefit = 0
    best_combination = []

    while queue:
        current = queue.pop()

        if current.level == len(items) - 1:
            if current.benefit > max_benefit:
                max_benefit = current.benefit
                best_combination = current.items
        else:
            next_level = current.level + 1
            next_item = items[next_level]

            include_benefit = current.benefit + next_item.benefit
            include_weight = current.weight + next_item.weight

            if include_weight <= max_weight:
                include_node = Node(next_level, include_benefit,
                                    include_weight, current.items + [next_item.id])
                if include_benefit > max_benefit:
                    max_benefit = include_benefit
                    best_combination = include_node.items
                queue.append(include_node)

            exclude_node = Node(next_level, current.benefit,
                                current.weight, current.items)
            
            queue.append(exclude_node)

    return max_benefit, best_combination

编辑：

以下结果基于下面的答案：

program.py:42: size=4432 B (+840 B), count=79 (+15), average=56 B
program.py:116: size=0 B (-768 B), count=0 (-1)
program.py:79: size=0 B (-744 B), count=0 (-13)
program.py.py:85: size=0 B (-72 B), count=0 (-1)
program.py:57: size=0 B (-56 B), count=0 (-1)
program.py:56: size=0 B (-56 B), count=0 (-1)
program.py:74: size=0 B (-32 B), count=0 (-1)
program.py:37: size=32 B (+0 B), count=1 (+0), average=32 B

- zellez

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- justhecuke · Accepted Answer

您可以尝试另一个答案建议的方法：https://dev59.com/mHRB5IYBdhLWcg3wr44U#45679009

虽然我无法运行您的代码来尝试，因为缺少Node定义，但您可以尝试类似以下的内容：

import tracemalloc

tracemalloc.start()
knapsack_dfs(...)
dfs_snapshot = tracemalloc.take_snapshot()
knapsack_bfs(...)
bfs_snapshot = tracemalloc.take_snapshot()
tracemalloc.stop()

bfs_snapshot = bfs_snapshot.filter_traces((tracemalloc.Filter(False, '*tracemalloc.py'),))
dfs_snapshot = dfs_snapshot.filter_traces((tracemalloc.Filter(False, '*tracemalloc.py'),))

for statdiff in bfs_snapshot.compare_to(dfs_snapshot, 'lineno'):
  print(statdiff)