这是我当前在迷宫问题中的启发式函数：
fn heuristic(&self, x: i32, y: i32) -> i32 {
((self.m - 1) - y).abs() + ((self.n - 1) - x).abs()
}
我打算使用曼哈顿距离启发式，但它不起作用。
fn heuristic(&self, x: i32, y: i32) -> i32 {
(((self.m - 1) - y).abs() + ((self.n - 1) - x).abs()) / 5
}
所以我通过除以 5 使其变得更正，然后它就起作用了，但我不知道为什么。
这是我的完整代码：
use std::io::stdin;
#[derive(Clone, Copy)]
struct Node {
coord: (i32, i32),
real_cost: i32,
f: i32,
}
impl Node {
fn new(coord: (i32, i32), real_cost: i32, f: i32) -> Self {
Node {
coord,
real_cost,
f,
}
}
fn x(&self) -> i32 {
self.coord.0
}
fn y(&self) -> i32 {
self.coord.1
}
}
impl PartialEq for Node {
fn eq(&self, other: &Self) -> bool {
self.f == other.f
}
}
impl PartialOrd for Node {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
self.f.partial_cmp(&other.f)
}
}
struct Heap {
heap: Vec<Node>,
// Node Structure
}
static BLOCK: i32 = 0;
impl Heap {
fn new() -> Self {
Heap { heap: Vec::new() }
}
fn child_index(&self, current: usize) -> usize {
current * 2 + 1
}
fn parent_index(&self, current: usize) -> usize {
(current - 1) / 2
}
fn push(&mut self, num: Node) {
self.heap.push(num);
let mut current = self.heap.len() - 1;
while current != 0 {
let parent = self.parent_index(current);
if self.heap[current] >= self.heap[parent] {
break;
}
self.heap.swap(current, parent);
current = parent;
}
}
fn front(&mut self) -> Option<Node> {
if self.heap.is_empty() {
None
} else {
Some(self.heap[0])
}
}
fn pop(&mut self) {
if self.heap.is_empty() {
return;
}
let mut parent = 0;
let mut child = self.child_index(0);
let &last = self.heap.last().unwrap();
while child < self.heap.len() {
let left = &self.heap[child];
if child + 1 < self.heap.len() {
let right = &self.heap[child + 1];
if left > right {
child += 1;
}
}
self.heap[parent] = self.heap[child];
parent = child;
child = self.child_index(parent);
}
self.heap[parent] = last;
self.heap.pop();
}
}
struct Maze {
map: Vec<Vec<i32>>,
visit: Vec<Vec<bool>>,
pq: Heap,
n: i32,
m: i32,
}
impl Maze {
fn new(height: i32, width: i32) -> Self {
Maze {
map: Vec::new(),
visit: vec![vec![false; width as usize]; height as usize],
pq: Heap::new(),
n: height,
m: width,
}
}
fn heuristic(&self, x: i32, y: i32) -> i32 {
(((self.m - 1) - y).abs() + ((self.n - 1) - x).abs()) / 5
}
fn explore(&mut self, x: i32, y: i32, real_cost: i32) {
if x < 0
|| y < 0
|| x >= self.n
|| y >= self.m
|| self.map[x as usize][y as usize] == BLOCK
|| self.visit[x as usize][y as usize] == true
{
return;
}
self.visit[x as usize][y as usize] = true;
let heuristic = self.heuristic(x, y);
let new_node = Node::new((x, y), real_cost, heuristic + real_cost);
self.pq.push(new_node);
}
fn a_star(&mut self) {
let heuristic = self.heuristic(0, 0);
let new_node = Node::new((0, 0), 1, heuristic + 1);
self.pq.push(new_node);
while let Some(cur) = self.pq.front() {
self.pq.pop();
let x = cur.x();
let y = cur.y();
if x == self.n - 1 && y == self.m - 1 {
println!("{}", cur.real_cost);
return;
}
let real_cost = cur.real_cost + 1;
self.explore(x + 1, y, real_cost);
self.explore(x - 1, y, real_cost);
self.explore(x, y + 1, real_cost);
self.explore(x, y - 1, real_cost);
}
panic!("error");
}
}
fn get_io() -> String {
let mut line = String::new();
stdin().read_line(&mut line).unwrap();
line
}
fn str_to_int(line: &String) -> Vec<i32> {
line.split_whitespace()
.filter_map(|x| x.parse::<i32>().ok())
.collect()
}
fn chars_to_int(line: &String) -> Vec<i32> {
let mut result = Vec::new();
for c in line.chars() {
if c != '\n' {
result.push(c as i32 - '0' as i32);
}
}
result
}
fn main() {
let args = str_to_int(&get_io());
let mut maze = Maze::new(args[0], args[1]);
for _ in 0..maze.n {
let nums = chars_to_int(&get_io());
maze.map.push(nums);
}
maze.a_star();
// println!("map : {:?}, \n visit : {:?}", maze.map, maze.visit);
}
我相信当该节点的当前实际成本小于该节点之前记录的（最小）实际成本时，您也应该重新访问该节点。
我的建议是更新“访问”地图，使该值是 i32 而不是布尔值，并且在探索功能中，您可以将检查更新为
real_cost >= self.visit[x as usize][y as usize]