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    }}

执行结果如下：

***

[左神java代码]()