最大加权独立集问题?
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