最大加权独立集问题?

最大加权独立集问题?

1.创建包含 100 个节点的路径图,并在每个节点上分配 1 到 50 的随机权重。
2.实现动态规划算法的递归版本,以计算刚刚在步骤 1 中创建的图形的最大权重独立集。
3.实现著名而优雅的动态规划版本,其中独立集以自下而上的迭代方式计算。


回答:

import random

# Set a fixed random seed for reproducibility

random.seed(42)

# Create a path graph with 100 nodes

# Each node is assigned a random weight between 1 and 50

weights = [random.randint(1, 50) for _ in range(100)]

weights[:10] # Display the weights of the first 10 nodes

[41, 8, 2, 48, 18, 16, 15, 9, 48, 7]

def mwis_recursive(i, weights, cache):

# Base case: negative index means an empty set

if i < 0:

return 0

# If the result is in the cache, return it

if i in cache:

return cache[i]

# Recursive case: either include node i and skip node i-1, or skip node i and include node i-1

include_i = weights[i] + mwis_recursive(i - 2, weights, cache)

exclude_i = mwis_recursive(i - 1, weights, cache)

# Save the result in the cache and return it

cache[i] = max(include_i, exclude_i)

return cache[i]

# Initialize the cache

cache = {}

# Compute the maximum weight of the independent set

max_weight_recursive = mwis_recursive(len(weights) - 1, weights, cache)

max_weight_recursive

结果:1519

def mwis_iterative(weights):

# Initialize the array for the maximum weight of the independent set for each subproblem

max_weights = [0] * (len(weights) + 1)

# Compute the maximum weight of the independent set for each subproblem

for i in range(len(weights)):

include_i = weights[i] + max_weights[i - 1]

exclude_i = max_weights[i]

max_weights[i + 1] = max(include_i, exclude_i)

# Compute which nodes are included in the maximum weight independent set

included = []

i = len(weights)

while i > 0:

if weights[i - 1] + max_weights[i - 2] > max_weights[i - 1]:

included.append(i - 1)

i -= 2

else:

i -= 1

return max_weights[-1], included[::-1]

# Compute the maximum weight of the independent set and which nodes are included

max_weight_iterative, included_nodes = mwis_iterative(weights)

max_weight_iterative, included_nodes

最大权重独立集中的节点为:[0, 3, 5, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 55, 57, 59, 61, 63, 66, 68, 71, 73, 76, 78, 80, 82, 84, 87, 89, 91, 93, 95, 97, 99]

以上是 最大加权独立集问题? 的全部内容, 来源链接: utcz.com/p/938686.html

回到顶部