我正在使用 R 编程语言。
假设有 100 人 - 每个人都用 1:100 开始的 ID 表示。每个人都可以与其他人成为朋友。数据集可以用图形/网络格式表示,如下所示:
# Set the seed for reproducibility
set.seed(123)
# Generate a vector of ID's from 1 to 100
ids <- 1:100
# Initialize an empty data frame to store the "from" and "to" values
edges <- data.frame(from=integer(), to=integer(), stringsAsFactors=FALSE)
# Iterate through the ID's
for(id in ids) {
# Randomly select a minimum of 1 and a maximum of 8 neighbors for the current ID
neighbors <- sample(ids[ids != id], size=sample(1:8, size=1))
# Add a new row to the data frame for each "to" value
for(neighbor in neighbors) {
edges <- rbind(edges, data.frame(from=id, to=neighbor))
}
}
正如我们所看到的,数据可以可视化以揭示图形/网络格式:
library(igraph)
library(visNetwork)
# Convert the data frame to an igraph object
g <- graph_from_data_frame(edges, directed=FALSE)
# Plot the graph
plot(g)
# Optional visualization
#visIgraph(g)
现在,假设该数据集中的每个人都有一定数量的 cookie。这看起来像这样:
set.seed(123)
cookies = data.frame(id = 1:100, number_of_cookies = c(abs(as.integer(rnorm(25, 15, 5))), abs(as.integer(rnorm(75, 5, 5)))))
这是我的问题:
- 我想确保这个数据集中没有人拥有少于 12 个 cookie - 也就是说,如果某人拥有少于 12 个 cookie,他们可以将他们的 cookie 与邻居(例如一级邻居、二级邻居)“汇集”在一起, ... n 级邻居 ... 直到满足这个条件),看看他们现在是否有超过 12 个 cookie
- 但是,我还想确保在此池化过程中,池化的朋友组中没有超过 20 个 cookie(即,这可能需要“取消池化”之前池化在一起的邻居)
- 最后,如果某人与其他人在一个组中 - 那么这个人不能被放入另一个组中(即没有“双重浸入”)
我编写了一个函数,它接受一个 ID 作为输入,然后返回该 ID 以及该 ID 的所有邻居的 cookie 总数:
library(data.table)
library(dplyr)
sum_cookies_for_id <- function(id) {
# Get the connected IDs for the given ID
connected_ids <- c(id, edges[edges$from == id | edges$to == id, "to"])
# Sum the number of cookies for all connected IDs
sum(cookies[cookies$id %in% connected_ids, "number_of_cookies"])
}
# Test the function
sum_cookies_for_id(23)
但除此之外,我不知道如何继续。
有人可以告诉我如何继续为这个问题编写代码吗?在这样的例子中可以使用动态规划吗?
Thanks!
Notes:
- 我认为这个问题可能具有“随机”性质 - 也就是说,取决于您从哪个 ID 开始以及您将此特定 ID 与哪个其他 ID 分组......最终可能会导致更少或更多的人拥有少于 12 个 cookie
- 我认为编写一个执行随机分组的“贪婪”算法可能是解决此类问题的最简单选择?
- 将来,我有兴趣看看如何更“复杂的算法”(例如遗传算法) 可用于进行分组,以便留下少于 12 个 cookie 的最少人数。
- 思考:在考虑这些总/总和约束的同时,是否有可能使用一些预先存在的图/网络聚类算法来解决这个问题(例如 Louvain 社区检测)?