# Parkerpal-Algorithm

**Repository Path**: parkerpal/parkerpal-algorithm

## Basic Information

- **Project Name**: Parkerpal-Algorithm
- **Description**: 定位与路径规划算法（实验版）
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-12-15
- **Last Updated**: 2025-07-25

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README


# 定位与规划算法

## 使用

```shell
# 生成可执行文件
xmake build

# 运行单元测试
xmake test

# 查看测试失败信息
xmake test -vD
```

## 定位算法

### 三边定位

三边定位（Trilateration）是一种通过已知三个或更多参考点的位置和到这些点的距离来确定一个未知位置的技术，是一个较为简单的模型。在无线通信中我们可以用信号强度指示（RSSI, Received Signal Strength Indicator）来估算距离。

缺点：多路径效应、环境因素对信号传播的影响、精度等


<img title="三边定位原理图" src="./img/三边定位.png">

## 路径规划算法

当知道起点和终点，以及路径，即可抽象为一副简单的图，规划中需要考虑的因素可以抽象为“权值”，这样把大体转化为了图论中的单源最短路径问题

我们确保抽象出来的图没有负权重边，这样可以选择实现简单可靠的Dijkstra算法，而且易于与机器学习结合进行优化。

这样问题就转变成了：

1. 如何构造为一个没有负权重边的图 
2. 如何定义和处理权值

### Dijkstra

适用于带非负权重边的图
使用优先队列（通常实现为堆）来选择下一个距离起点最近的顶点
时间复杂度：$O((V + E) log V)$，其中V是顶点数，E是边数

### $A^*$(A星算法):

是一种启发式搜索算法，特别适用于寻找两点之间的最短路径
需要一个启发函数来估计从当前节点到目标节点的成本
时间复杂度依赖于启发函数的质量