用ts写一个二叉堆排双向A星
时间: 2023-07-18 10:15:50 浏览: 61
下面是一个 TypeScript 实现的双向 A* 算法,其中使用二叉堆作为优先队列:
```typescript
interface Node {
x: number;
y: number;
f: number;
g: number;
h: number;
parent: Node | null;
}
function aStar(start: Node, end: Node, map: number[][]): Node | null {
const openList1: Node[] = [start];
const openList2: Node[] = [end];
const closeList1: Node[] = [];
const closeList2: Node[] = [];
const heap1 = new BinaryHeap<Node>((a, b) => a.f < b.f);
const heap2 = new BinaryHeap<Node>((a, b) => a.f < b.f);
heap1.push(start);
heap2.push(end);
while (heap1.size() > 0 && heap2.size() > 0) {
const current1 = heap1.pop()!;
const current2 = heap2.pop()!;
closeList1.push(current1);
closeList2.push(current2);
if (closeList2.some(node => node.x === current1.x && node.y === current1.y)) {
const node = closeList2.find(node => node.x === current1.x && node.y === current1.y);
return node?.parent ? node.parent : node;
}
if (closeList1.some(node => node.x === current2.x && node.y === current2.y)) {
const node = closeList1.find(node => node.x === current2.x && node.y === current2.y);
return node?.parent ? node.parent : node;
}
const neighbors1 = getNeighbors(current1, map);
neighbors1.forEach(neighbor => {
if (closeList1.some(node => node.x === neighbor.x && node.y === neighbor.y)) return;
if (!openList1.some(node => node.x === neighbor.x && node.y === neighbor.y)) {
neighbor.g = current1.g + 1;
neighbor.h = manhattanDistance(neighbor, end);
neighbor.f = neighbor.g + neighbor.h;
neighbor.parent = current1;
openList1.push(neighbor);
heap1.push(neighbor);
} else {
const existingNode = openList1.find(node => node.x === neighbor.x && node.y === neighbor.y);
if (existingNode && current1.g + 1 < existingNode.g) {
existingNode.g = current1.g + 1;
existingNode.f = existingNode.g + existingNode.h;
existingNode.parent = current1;
heap1.update(existingNode);
}
}
});
const neighbors2 = getNeighbors(current2, map);
neighbors2.forEach(neighbor => {
if (closeList2.some(node => node.x === neighbor.x && node.y === neighbor.y)) return;
if (!openList2.some(node => node.x === neighbor.x && node.y === neighbor.y)) {
neighbor.g = current2.g + 1;
neighbor.h = manhattanDistance(neighbor, start);
neighbor.f = neighbor.g + neighbor.h;
neighbor.parent = current2;
openList2.push(neighbor);
heap2.push(neighbor);
} else {
const existingNode = openList2.find(node => node.x === neighbor.x && node.y === neighbor.y);
if (existingNode && current2.g + 1 < existingNode.g) {
existingNode.g = current2.g + 1;
existingNode.f = existingNode.g + existingNode.h;
existingNode.parent = current2;
heap2.update(existingNode);
}
}
});
}
return null;
}
function getNeighbors(node: Node, map: number[][]): Node[] {
const neighbors: Node[] = [];
const { x, y } = node;
if (y > 0 && map[y - 1][x] !== 1) neighbors.push({ x, y: y - 1, f: 0, g: 0, h: 0, parent: null });
if (y < map.length - 1 && map[y + 1][x] !== 1) neighbors.push({ x, y: y + 1, f: 0, g: 0, h: 0, parent: null });
if (x > 0 && map[y][x - 1] !== 1) neighbors.push({ x: x - 1, y, f: 0, g: 0, h: 0, parent: null });
if (x < map[0].length - 1 && map[y][x + 1] !== 1) neighbors.push({ x: x + 1, y, f: 0, g: 0, h: 0, parent: null });
return neighbors;
}
function manhattanDistance(node1: Node, node2: Node): number {
return Math.abs(node1.x - node2.x) + Math.abs(node1.y - node2.y);
}
class BinaryHeap<T> {
private heap: T[] = [];
private compareFn: (a: T, b: T) => boolean;
constructor(compareFn: (a: T, b: T) => boolean) {
this.compareFn = compareFn;
}
size(): number {
return this.heap.length;
}
push(item: T): void {
this.heap.push(item);
this.bubbleUp(this.heap.length - 1);
}
pop(): T | undefined {
if (this.heap.length === 0) return undefined;
const root = this.heap[0];
const last = this.heap.pop()!;
if (this.heap.length > 0) {
this.heap[0] = last;
this.bubbleDown(0);
}
return root;
}
update(item: T): void {
const index = this.heap.indexOf(item);
if (index >= 0) {
this.bubbleUp(index);
this.bubbleDown(index);
}
}
private bubbleUp(index: number): void {
const item = this.heap[index];
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
const parent = this.heap[parentIndex];
if (this.compareFn(item, parent)) {
this.heap[index] = parent;
index = parentIndex;
} else break;
}
this.heap[index] = item;
}
private bubbleDown(index: number): void {
const item = this.heap[index];
const length = this.heap.length;
while (index < length) {
const leftIndex = index * 2 + 1;
const rightIndex = index * 2 + 2;
let leftChild: T, rightChild: T;
let swapIndex = -1;
if (leftIndex < length) {
leftChild = this.heap[leftIndex];
if (this.compareFn(leftChild, item)) swapIndex = leftIndex;
}
if (rightIndex < length) {
rightChild = this.heap[rightIndex];
if (this.compareFn(rightChild, item) && this.compareFn(rightChild, leftChild)) swapIndex = rightIndex;
}
if (swapIndex === -1) break;
this.heap[index] = this.heap[swapIndex];
index = swapIndex;
}
this.heap[index] = item;
}
}
```
这里的 `Node` 接口定义了一个节点,包含了 x、y、f、g、h 和 parent 属性,分别表示节点的横纵坐标、总代价、从起点到该节点的代价、从该节点到终点的估价和父节点。`aStar` 函数实现了双向 A* 算法,其中使用两个优先队列(二叉堆)来维护两个方向的搜索。`getNeighbors` 函数用于获取一个节点的邻居节点。`manhattanDistance` 函数用于计算两个节点之间的曼哈顿距离。`BinaryHeap` 类是一个二叉堆的实现,用于实现优先队列。