2022-04-19:A*算法,
过程和Dijskra高度相处,
有到终点的预估函数,
只要预估值<=客观上最优距离,就是对的。
预估函数是一种吸引力:
1)合适的吸引力可以提升算法的速度;
2)吸引力“过强”会出现错误。
答案2022-04-19:
具体见代码。
代码用rust编写。代码如下:
use rand::Rng;
fn main() {
let mut map: Vec<Vec<isize>> = vec![];
for i in 0..10 {
map.push(vec![]);
for j in 0..10 {
map[i].push(0);
}
}
for i in 0..map.len() {
for j in 0..map[0].len() {
map[i][j] = rand::thread_rng().gen_range(1, 10);
}
}
let startX: isize = 0;
let startY: isize = 0;
let targetX: isize = 4;
let targetY: isize = 7;
let ret: isize = min_distance2(&mut map, startX, startY, targetX, targetY);
for i in 0..10 {
println!("{:?}", map[i]);
}
println!("{}", ret);
}
const MAX_VALUE: isize = 9223372036854775807;
fn min_distance2(
map: &mut Vec<Vec<isize>>,
startX: isize,
startY: isize,
targetX: isize,
targetY: isize,
) -> isize {
if map[startX as usize][startY as usize] == 0 || map[targetX as usize][targetY as usize] == 0 {
return MAX_VALUE;
}
let n = map.len() as isize;
let m = map[0].len() as isize;
let mut heap: Vec<Vec<isize>> = Vec::new();
let mut closed: Vec<Vec<bool>> = Vec::new();
for i in 0..n {
closed.push(Vec::new());
for j in 0..m {
closed[i as usize].push(false);
}
}
let mut t = vec![
map[startX as usize][startY as usize],
distance(startX, startY, targetX, targetY),
startX,
startY,
];
heap.push(t);
let mut ans = MAX_VALUE;
while heap.len() > 0 {
//用切片模拟堆,所以需要排序
heap.sort_by(|x, y| (x[0] + x[1]).cmp(&(y[0] + y[1])));
// 报错
// let mut cur: &Vec<isize> = &(heap[0]);
// heap.remove(0);
let mut fromDistance: isize = heap[0][0];
let mut row: isize = heap[0][2];
let mut col: isize = heap[0][3];
heap.remove(0); //必须放在这里
if (closed[row as usize][col as usize]) {
continue;
}
closed[row as usize][col as usize] = true;
if (row == targetX && col == targetY) {
ans = fromDistance;
break;
}
add2(
fromDistance,
row - 1,
col,
targetX,
targetY,
n,
m,
map,
&mut closed,
&mut heap,
);
add2(
fromDistance,
row + 1,
col,
targetX,
targetY,
n,
m,
map,
&mut closed,
&mut heap,
);
add2(
fromDistance,
row,
col - 1,
targetX,
targetY,
n,
m,
map,
&mut closed,
&mut heap,
);
add2(
fromDistance,
row,
col + 1,
targetX,
targetY,
n,
m,
map,
&mut closed,
&mut heap,
);
}
return ans;
}
fn add2(
pre: isize,
row: isize,
col: isize,
targetX: isize,
targetY: isize,
n: isize,
m: isize,
map: &mut Vec<Vec<isize>>,
closed: &mut Vec<Vec<bool>>,
heap: &mut Vec<Vec<isize>>,
) {
if (row >= 0
&& row < n
&& col >= 0
&& col < m
&& map[row as usize][col as usize] != 0
&& !closed[row as usize][col as usize])
{
let mut t = vec![
pre + map[row as usize][col as usize],
distance(row, col, targetX, targetY),
row,
col,
];
heap.push(t);
}
}
// 曼哈顿距离
fn distance(curX: isize, curY: isize, targetX: isize, targetY: isize) -> isize {
return abs(targetX - curX) + abs(targetY - curY);
}
fn abs(a: isize) -> isize {
if a < 0 {
-a
} else {
a
}
}
执行结果如下:
手机扫一扫
移动阅读更方便
你可能感兴趣的文章