Python

Question

我有一个关于机场航班的家庭作业，首先我必须根据以下条件从 10000 个随机数为 1000x1000 数组创建稀疏矩阵（i、j 和值）的表示：

i 和 j 必须在 0-999 之间，因为数组
值必须在 1.0-5.0 之间
i 不能等于 j
i 和 j 只能出现一次

i 是出发机场，j 是到达机场，值是从 i 到 j 的行程小时数。

然后我必须根据上述标准找到最多停靠 2 到 8 个的机场 A 的往返行程。例如：

A、D、F、G、A 是合法的往返行程，有 4 个站点
A、D、F、D、A 不是合法往返，因为 D 被访问了两次

注意：问题必须完全使用 python 内置库来解决。不接受像 scipy 和 numpy 这样的外部库。

我已经尝试运行一个 10000 个数字的循环，并根据上述标准为行、列和值分配一个随机数，但我想这不是作业要求我做的，因为循环不会停止。

我猜 i 和 j 不是稀疏矩阵的实际 iloc 和 j 表示，而是它们的值？我不知道。

除了往返实现的示例之外，我目前没有工作代码。虽然如果列表为空会引发错误：

dNext = {
    0: [],
    1: [4, 2, 0],
    2: [1, 4],
    3: [0],
    4: [3, 1]
}

def findRoundTrips(trip, n, trips):
    if (trip[0] == trip[-1]) and (1 < len(trip) <= n + 1):
        trips.append(trip.copy())
        return
    for x in dNext[trip[-1]]:
        if ((x not in trip[1:]) and (len(trip) < n)) or (x == trip[0]):
            trip.append(x)
            findRoundTrips(trip, n, trips)
            trip.pop()

Answer 1

以下是我构建稀疏矩阵的方法：

from collections import defaultdict
import random

max_location = 1000
min_value = 1.0
max_value = 5.0

sparse_matrix = defaultdict(list)

num_entries = 10000
for _ in range(num_entries):
    source = random.randint(0, max_location)
    dest = random.randint(0, max_location)
    value = random.uniform(min_value, max_value)

    sparse_matrix[source].append((dest, value))

这样做是将稀疏矩阵定义为字典，其中字典的键是旅行的起点。键的值定义了你可以飞到的任何地方以及飞到那里需要多长时间作为元组列表。

注意，我没有检查我是否完全正确地使用了 randint 和 uniform，如果你使用这个，你应该查看这些函数的文档以了解是否有此解决方案中是否存在任何差一错误。

Python - 从 10000 个随机值创建稀疏矩阵表示

Python - Create sparse matrix representation from 10000 random values

sparse-matrix