AI 助理
备案控制台
开发者社区 人工智能 文章 正文

地图权重计算（算法题）

2024-01-19 41
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 地图权重计算（算法题）

问题描述

题目：权重计算

描述：

考虑一个19x19的网格，每个网格都可以赋予一个权重。现在，给定一个坐标范围在 (−1500,1500),(−1500,1500)(−1500,1500),(−1500,1500) 之内的数据点，你的任务是为这个数据点在19x19的网格中确定权重。

数据点可能的位置与相应的权重计算如下：

  1. 数据点在某个网格的中心：此时，该数据点所在的那个网格权重为1，其余所有网格的权重为0。
  2. 数据点位于四个网格的交点：这四个相交的网格各自的权重为0.25，其余所有网格的权重为0。
  3. 数据点在网格的内部边界但非交点上：此时，数据点位于两个网格的共同边界上。例如，如果数据点在两个网格的水平共同边界上，则这两个网格的权重各为0.5，其余所有网格的权重为0。同理，如果数据点在两个网格的垂直边界上，这两个网格的权重也各为0.5。
  4. 数据点位于整体网格系统的边界上：在这种特殊情况下，所有网格的权重都为0，因为数据点在整个网格系统的外部边界上。
  5. 数据点在某个网格的内部角上但非交点需要安装距离来分配权重：例如，如果数据点在左下角上但不在四个网格的交点，你需要计算与该点相邻的左侧、下方、左下角和当前所在的网格的权重，使得总权重为1，需要计算当前点和这四个网格中心的距离，然后根据这个距离的比例来分配这个权值。

输入：

  • 一个元组，代表数据点的坐标 (x,y) ，其中 x,y∈[−1500,1500]x,y∈[−1500,1500]。

输出：

  • 一个 19×19 的二维数组，表示每个网格的权重。

思路分析

测试数据

1. 数据点在某个网格的中心：

测试点： (0,0)

解释： 这是整个19x19网格系统的中心点。在这种情况下，中心网格权重为1，其余网格权重为0。

预测结果： 19x19的二维数组中，中心格权重为1，其余为0。

测试通过

2. 数据点位于四个网格的交点：

测试点： (-1184.22, -1184.22)

解释： 数据点位于第一个行和第一个列的交点上。

**预测结果：**其中(1,1)、(1,2)、(2,1)和(2,2)的权重都是0.25。

测试通过

**3. **数据点在网格的内部边界但非交点上

  • 输入：(0, -1500 + CELL_SIZE)
  • 输出：一个19x19的二维数组，其中两个相邻网格的权重为0.5，其余网格的权重为0。
  • 解释：数据点 (-1184.22, -1294.22) 位于两个相邻网格的内部边界上，其中一个网格在左侧，另一个在右侧。因此，这两个相邻网格的权重都为0.5，其余网格的权重都是0。

测试通过，需要注意的是，编程里面的坐标相对于数学里面的是倒过来的

4. 数据点位于整体网格系统的边界上：

测试点： (-1500, 0)

解释： 数据点位于整个网格系统的左边界上。

预测结果： 所有网格权重为0。

通过测试

5.数据点在某个网格的内部角上但非交点需要安装距离来分配权重：

测试点： (-1125, 1125)

解释： 给定的数据点 (−1125,1125)位于第 2 列和第 16 行的网格内部角上。

预测结果： （当前网格）的权重应该最大，（左侧网格）的权重次之，网格（上方网格）的权重再次之，网格 （左上角网格）的权重最小，其余为0。

测试通过

测试代码

下面的代码，是用来通过测试数据，获得测试数据结果的。测试数据就是上面写的

import numpy as np
# 定义单元格大小
CELL_SIZE = 3000 / 19  # 单元格的尺寸
epsilon = 1e-3  # 容差
def get_grid_position_and_distances(x, y):
    """
    计算给定点的网格位置以及到四个边界的距离。
    """
    # 计算x和y坐标所对应的格子位置
    grid_x = int((x + 1500) // CELL_SIZE)
    grid_y = int((y + 1500) // CELL_SIZE)
    # 计算到四个边界的距离
    dist_left = x - (-1500 + grid_x * CELL_SIZE)
    dist_right = (-1500 + (grid_x + 1) * CELL_SIZE) - x
    dist_top = y - (-1500 + grid_y * CELL_SIZE)
    dist_bottom = (-1500 + (grid_y + 1) * CELL_SIZE) - y
    return grid_x, grid_y, dist_left, dist_right, dist_top, dist_bottom
def calculate_weight(x, y):
    """
    根据点的位置计算权重矩阵。
    """
    # 获取点的网格位置和距离信息
    grid_x, grid_y, dist_left, dist_right, dist_top, dist_bottom = get_grid_position_and_distances(x, y)
    weight_matrix = np.zeros((19, 19))  # 初始化权重矩阵为全零
    # 判断是否为外部边界点
    if x == 1500 or x == -1500 or y == 1500 or y == -1500:
        return weight_matrix  # 返回全零矩阵
    # 判断是否为中心点
    if np.isclose(x, -1500 + (grid_x + 0.5) * CELL_SIZE) and np.isclose(y, -1500 + (grid_y + 0.5) * CELL_SIZE):
        weight_matrix[grid_y, grid_x] = 1
        return weight_matrix
    # 判断是否为交叉点
    if (np.isclose(x, -1500 + grid_x * CELL_SIZE) or np.isclose(x, -1500 + (grid_x + 1) * CELL_SIZE)) and \
            (np.isclose(y, -1500 + grid_y * CELL_SIZE) or np.isclose(y, -1500 + (grid_y + 1) * CELL_SIZE)):
        weight_matrix[grid_y, grid_x] = 0.25
        weight_matrix[grid_y + 1, grid_x] = 0.25
        weight_matrix[grid_y, grid_x + 1] = 0.25
        weight_matrix[grid_y + 1, grid_x + 1] = 0.25
        return weight_matrix
    # 判断是否为内部边界点
    if np.isclose(dist_left, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y, grid_x - 1] = 0.5
        return weight_matrix
    if np.isclose(dist_right, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y, grid_x + 1] = 0.5
        return weight_matrix
    if np.isclose(dist_top, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y - 1, grid_x] = 0.5
        return weight_matrix
    if np.isclose(dist_bottom, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y + 1, grid_x] = 0.5
        return weight_matrix
    # 重新计算内部角落点的权重
    # 计算到四个近邻格子中心的距离
    distances = [
        np.sqrt(dist_left ** 2 + dist_top ** 2),
        np.sqrt(dist_right ** 2 + dist_top ** 2),
        np.sqrt(dist_left ** 2 + dist_bottom ** 2),
        np.sqrt(dist_right ** 2 + dist_bottom ** 2)
    ]
    # 计算距离的倒数
    inverse_distances = [1 / (d + epsilon) for d in distances]  # 添加epsilon以防止除以零
    total_inverse_distance = sum(inverse_distances)
    # 根据距离的倒数分配权重
    weights = [idist / total_inverse_distance for idist in inverse_distances]
    weight_matrix[grid_y, grid_x] = weights[0]
    weight_matrix[grid_y, grid_x - 1] = weights[1]
    weight_matrix[grid_y - 1, grid_x] = weights[2]
    weight_matrix[grid_y - 1, grid_x - 1] = weights[3]
    return weight_matrix
# 定义测试点
test_points = [
    (0, 0), (-1184.22, -1184.22),(0, -1500 + CELL_SIZE), (-1500, 0), (-1125, 1125)
]
for point in test_points:
    print(f"Test point: {point}")
    print(calculate_weight(*point))
    print("=" * 40)

测试结果

权重计算问题代码设计思路

  1. get_grid_position_and_distances函数:
  • 该函数接收一个点的x和y坐标作为输入。
  • 它首先计算给定点在网格系统中的位置(grid_x和grid_y)。
  • 然后，它计算点到其包含网格的四个边界的距离（dist_left, dist_right, dist_top, dist_bottom）。
  • 函数返回这些值。
  1. calculate_weight函数:
  • 该函数接收一个点的x和y坐标作为输入。
  • 它首先调用get_grid_position_and_distances函数来获取网格位置和边界距离。
  • 接下来，它根据不同的情况为每个网格分配权重：
  • 如果点位于网格系统的外部边界上，所有网格的权重都为0。
  • 如果点位于某个网格的中心，那个网格的权重为1，其他网格的权重为0。
  • 如果点位于四个网格的交点，这四个网格的权重都为0.25。
  • 如果点位于两个网格的内部边界上，这两个网格的权重都为0.5。
  • 如果点位于某个网格的内部角上但不在交点上，它计算点到四个邻近格子的中心的距离，并根据这些距离分配权重。

完整的代码

需要注意的是，这个代码不能够在jupyter里面运行，因为print函数对于特别费时间，数据量大容易拖垮浏览器，所以用的pycharm展示的，算法运行效率很高，如果去掉print那么一秒不到就可以出结果

import numpy as np
# 定义单元格大小
CELL_SIZE = 3000 / 19  # 单元格的尺寸
epsilon = 1e-3  # 容差
def get_grid_position_and_distances(x, y):
    """
    计算给定点的网格位置以及到四个边界的距离。
    """
    # 计算x和y坐标所对应的格子位置
    grid_x = int((x + 1500) // CELL_SIZE)
    grid_y = int((y + 1500) // CELL_SIZE)
    # 计算到四个边界的距离
    dist_left = x - (-1500 + grid_x * CELL_SIZE)
    dist_right = (-1500 + (grid_x + 1) * CELL_SIZE) - x
    dist_top = y - (-1500 + grid_y * CELL_SIZE)
    dist_bottom = (-1500 + (grid_y + 1) * CELL_SIZE) - y
    return grid_x, grid_y, dist_left, dist_right, dist_top, dist_bottom
def calculate_weight(x, y):
    """
    根据点的位置计算权重矩阵。
    """
    # 获取点的网格位置和距离信息
    grid_x, grid_y, dist_left, dist_right, dist_top, dist_bottom = get_grid_position_and_distances(x, y)
    weight_matrix = np.zeros((19, 19))  # 初始化权重矩阵为全零
    # 判断是否为外部边界点
    if x == 1500 or x == -1500 or y == 1500 or y == -1500:
        return weight_matrix  # 返回全零矩阵
    # 判断是否为中心点
    if np.isclose(x, -1500 + (grid_x + 0.5) * CELL_SIZE) and np.isclose(y, -1500 + (grid_y + 0.5) * CELL_SIZE):
        weight_matrix[grid_y, grid_x] = 1
        return weight_matrix
    # 判断是否为交叉点
    if (np.isclose(x, -1500 + grid_x * CELL_SIZE) or np.isclose(x, -1500 + (grid_x + 1) * CELL_SIZE)) and \
            (np.isclose(y, -1500 + grid_y * CELL_SIZE) or np.isclose(y, -1500 + (grid_y + 1) * CELL_SIZE)):
        weight_matrix[grid_y, grid_x] = 0.25
        weight_matrix[grid_y + 1, grid_x] = 0.25
        weight_matrix[grid_y, grid_x + 1] = 0.25
        weight_matrix[grid_y + 1, grid_x + 1] = 0.25
        return weight_matrix
    # 判断是否为内部边界点
    if np.isclose(dist_left, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y, grid_x - 1] = 0.5
        return weight_matrix
    if np.isclose(dist_right, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y, grid_x + 1] = 0.5
        return weight_matrix
    if np.isclose(dist_top, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y - 1, grid_x] = 0.5
        return weight_matrix
    if np.isclose(dist_bottom, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y + 1, grid_x] = 0.5
        return weight_matrix
    # 重新计算内部角落点的权重
    # 计算到四个近邻格子中心的距离
    distances = [
        np.sqrt(dist_left ** 2 + dist_top ** 2),
        np.sqrt(dist_right ** 2 + dist_top ** 2),
        np.sqrt(dist_left ** 2 + dist_bottom ** 2),
        np.sqrt(dist_right ** 2 + dist_bottom ** 2)
    ]
    # 计算距离的倒数
    inverse_distances = [1 / (d + epsilon) for d in distances]  # 添加epsilon以防止除以零
    total_inverse_distance = sum(inverse_distances)
    # 根据距离的倒数分配权重
    weights = [idist / total_inverse_distance for idist in inverse_distances]
    weight_matrix[grid_y, grid_x] = weights[0]
    weight_matrix[grid_y, grid_x - 1] = weights[1]
    weight_matrix[grid_y - 1, grid_x] = weights[2]
    weight_matrix[grid_y - 1, grid_x - 1] = weights[3]
    return weight_matrix
# 加载数据
data = np.load('D:\系统默认\桌面\永信\B4013-算法题\part.npy')
# 遍历数据并计算权重
for point in data:
    source_x, source_y = point
    print(compute_weights_for_point(source_x, source_y))
print("运行完了")

运行结果

文章标签：
算法
定位技术
Python
关键词：
计算算法
权重算法
极客李华
目录
相关文章
武子康
|
2月前
|
存储 分布式计算 算法
大数据-106 Spark Graph X 计算学习 案例：1图的基本计算、2连通图算法、3寻找相同的用户
大数据-106 Spark Graph X 计算学习 案例：1图的基本计算、2连通图算法、3寻找相同的用户
武子康
66 0
zzy的aly
|
2月前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算（目标检测）
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析（包括TP、FP、FN、TN、精准率和召回率），接口处理，数据集处理，以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例，用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
zzy的aly
68 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算（目标检测）
简简单单做算法
|
3月前
|
算法 数据可视化 数据安全/隐私保护
基于LK光流提取算法的图像序列晃动程度计算matlab仿真
该算法基于Lucas-Kanade光流方法，用于计算图像序列的晃动程度。通过计算相邻帧间的光流场并定义晃动程度指标（如RMS），可量化图像晃动。此版本适用于Matlab 2022a，提供详细中文注释与操作视频。完整代码无水印。
简简单单做算法
59 1
游客qeoynko2nmbgk
|
3月前
|
算法 C++
如何精确计算出一个算法的CPU运行时间?
如何精确计算出一个算法的CPU运行时间?
游客qeoynko2nmbgk
48 0
花酒锄作田
|
4月前
|
算法 Go Python
[算法]计算斐波拉契数列
[算法]计算斐波拉契数列
花酒锄作田
46 2
zcq5jk6y5y5e4
|
4月前
|
算法
计算空间物体包围球的两种算法实现
计算空间物体包围球的两种算法实现
zcq5jk6y5y5e4
49 0
龙大吉
|
6月前
|
机器学习/深度学习 算法
**反向传播算法**在多层神经网络训练中至关重要，它包括**前向传播**、**计算损失**、**反向传播误差**和**权重更新**。
【6月更文挑战第28天】**反向传播算法**在多层神经网络训练中至关重要，它包括**前向传播**、**计算损失**、**反向传播误差**和**权重更新**。数据从输入层流经隐藏层到输出层，计算预测值。接着，比较预测与真实值计算损失。然后，从输出层开始，利用链式法则反向计算误差和梯度，更新权重以减小损失。此过程迭代进行，直到损失收敛或达到训练次数，优化模型性能。反向传播实现了自动微分，使模型能适应训练数据并泛化到新数据。
龙大吉
70 2
爱喝兽奶的熊孩子
|
6月前
|
算法 C++
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
爱喝兽奶的熊孩子
66 2
爱喝兽奶的熊孩子
|
6月前
|
算法 C++
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
爱喝兽奶的熊孩子
92 2
我爱matlab
|
6月前
|
算法
m基于PSO粒子群优化的LDPC码NMS译码算法最优归一化参数计算和误码率matlab仿真
MATLAB2022a仿真实现了基于遗传优化的NMS LDPC译码算法，优化归一化参数以提升纠错性能。NMS算法通过迭代处理低密度校验码，而PSO算法用于寻找最佳归一化因子。程序包含粒子群优化的迭代过程，根据误码率评估性能并更新解码参数。最终，展示了迭代次数与优化过程的关系，并绘制了SNR与误码率曲线。
我爱matlab
54 2

热门文章

最新文章

  • 1
    【TDOA定位】基于chan和talor算法实现TDOA定位含性能对比matlab代码
  • 2
    openssl中算法的组织方式
  • 3
    C# 实现分布式自增 ID 算法（Snowflake 雪花算法）
  • 4
    【算法研究】Bresenham画线算法
  • 5
    拓扑排序详解（包含算法原理图解、算法实现过程详解、算法例题变式全面讲解等）
  • 6
    算法导论第十四章 数据结构的扩张
  • 7
    JVM内存模型及垃圾回收算法
  • 8
    九连环的递归算法（C和C++）
  • 9
    【字符串处理算法】删除特定的字符的算法设计及C代码实现
  • 10
    指针难，算法难，难住了谁
  • 1
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
    380
  • 2
    【机器学习】为什么K-means算法使用欧式距离度量？
    367
  • 3
    【机器学习】描述K-means算法的步骤
    149
  • 4
    【机器学习】K-means和KNN算法有什么区别？
    602
  • 5
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    49
  • 6
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    50
  • 7
    图搜索算法详解
    125
  • 8
    R语言实现蒙特卡洛模拟算法
    294
  • 9
    python实现时序平滑算法SG滤波器
    174
  • 10
    m基于FPGA的MPPT最大功率跟踪算法verilog实现,包含testbench
    73

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月