ts写一个二插堆双向A星算法
时间: 2024-02-19 09:04:02 浏览: 38
好的,以下是 TypeScript 实现的二叉堆排和双向 A* 算法的示例代码:
```typescript
// 定义二叉堆类
class BinaryHeap<T> {
private heap: [number, T][] = [];
// 获取父节点的索引
private parentIndex(index: number): number {
return Math.floor((index - 1) / 2);
}
// 获取左子节点的索引
private leftIndex(index: number): number {
return index * 2 + 1;
}
// 获取右子节点的索引
private rightIndex(index: number): number {
return index * 2 + 2;
}
// 上移节点
private shiftUp(index: number): void {
if (index === 0) return; // 已经是根节点了
const parentIndex = this.parentIndex(index);
if (this.heap[parentIndex][0] > this.heap[index][0]) {
// 父节点的值比当前节点的值大,需要交换
[this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
this.shiftUp(parentIndex);
}
}
// 下移节点
private shiftDown(index: number): void {
const leftIndex = this.leftIndex(index);
const rightIndex = this.rightIndex(index);
let minIndex = index;
if (leftIndex < this.heap.length && this.heap[leftIndex][0] < this.heap[minIndex][0]) {
minIndex = leftIndex;
}
if (rightIndex < this.heap.length && this.heap[rightIndex][0] < this.heap[minIndex][0]) {
minIndex = rightIndex;
}
if (minIndex !== index) {
// 需要交换
[this.heap[minIndex], this.heap[index]] = [this.heap[index], this.heap[minIndex]];
this.shiftDown(minIndex);
}
}
// 插入节点
insert(value: T, priority: number): void {
this.heap.push([priority, value]);
this.shiftUp(this.heap.length - 1);
}
// 弹出优先级最高的节点
pop(): T | undefined {
if (this.heap.length === 0) return undefined;
if (this.heap.length === 1) return this.heap.pop()![1];
const result = this.heap[0][1];
this.heap[0] = this.heap.pop()!;
this.shiftDown(0);
return result;
}
// 是否为空
isEmpty(): boolean {
return this.heap.length === 0;
}
}
interface GraphNode {
x: number;
y: number;
}
interface GraphEdge {
from: GraphNode;
to: GraphNode;
cost: number;
}
class Graph {
private edges: GraphEdge[] = [];
// 添加一条边
addEdge(from: GraphNode, to: GraphNode, cost: number): void {
this.edges.push({ from, to, cost });
}
// 获取某个节点的邻居
neighbors(node: GraphNode): GraphNode[] {
const result: GraphNode[] = [];
for (const edge of this.edges) {
if (edge.from.x === node.x && edge.from.y === node.y) {
result.push(edge.to);
} else if (edge.to.x === node.x && edge.to.y === node.y) {
result.push(edge.from);
}
}
return result;
}
// 获取两个节点之间的距离
cost(from: GraphNode, to: GraphNode): number | undefined {
for (const edge of this.edges) {
if ((edge.from.x === from.x && edge.from.y === from.y && edge.to.x === to.x && edge.to.y === to.y) ||
(edge.from.x === to.x && edge.from.y === to.y && edge.to.x === from.x && edge.to.y === from.y)) {
return edge.cost;
}
}
return undefined;
}
}
function heuristic(a: GraphNode, b: GraphNode): number {
// 计算两个节点之间的 Manhattan 距离
return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}
function aStar(start: GraphNode, end: GraphNode, graph: Graph): GraphNode[] {
const openSetStart = new BinaryHeap<GraphNode>();
const openSetEnd = new BinaryHeap<GraphNode>();
const cameFromStart = new Map<GraphNode, GraphNode>();
const cameFromEnd = new Map<GraphNode, GraphNode>();
const gScoreStart = new Map<GraphNode, number>();
const gScoreEnd = new Map<GraphNode, number>();
openSetStart.insert(start, 0);
openSetEnd.insert(end, 0);
gScoreStart.set(start, 0);
gScoreEnd.set(end, 0);
while (!openSetStart.isEmpty() && !openSetEnd.isEmpty()) {
const currentStart = openSetStart.pop()!;
const currentEnd = openSetEnd.pop()!;
if (currentStart === currentEnd) {
// 找到了一条从起点到终点的路径
const path: GraphNode[] = [currentStart];
let node = currentStart;
while (cameFromStart.has(node)) {
node = cameFromStart.get(node)!;
path.unshift(node);
}
node = currentEnd;
while (cameFromEnd.has(node)) {
node = cameFromEnd.get(node)!;
path.push(node);
}
return path;
}
for (const neighbor of graph.neighbors(currentStart)) {
const tentativeGScore = gScoreStart.get(currentStart)! + graph.cost(currentStart, neighbor)!;
if (!gScoreStart.has(neighbor) || tentativeGScore < gScoreStart.get(neighbor)!) {
cameFromStart.set(neighbor, currentStart);
gScoreStart.set(neighbor, tentativeGScore);
const fScore = tentativeGScore + heuristic(neighbor, end);
openSetStart.insert(neighbor, fScore);
}
}
for (const neighbor of graph.neighbors(currentEnd)) {
const tentativeGScore = gScoreEnd.get(currentEnd)! + graph.cost(currentEnd, neighbor)!;
if (!gScoreEnd.has(neighbor) || tentativeGScore < gScoreEnd.get(neighbor)!) {
cameFromEnd.set(neighbor, currentEnd);
gScoreEnd.set(neighbor, tentativeGScore);
const fScore = tentativeGScore + heuristic(start, neighbor);
openSetEnd.insert(neighbor, fScore);
}
}
}
// 没有找到路径
return [];
}
```
在上述代码中,`BinaryHeap` 类表示二叉堆,`Graph` 类表示图,`aStar` 函数表示双向 A* 算法。其中,`heuristic` 函数用于计算两个节点之间的估价函数值,这里使用了 Manhattan 距离。在实际使用中,需要根据具体情况修改估价函数。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)