启发式搜索¶
此类算法很少会出现在算法竞赛中，主要应用于人工智能方面
常用的启发函数¶
对于网格地图来说, 如果只能四方向(上下左右)移动, 曼哈顿距离(Manhattan distance) 是最合适的启发函数.
function Manhattan(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
// 在最简单的情况下, D 可以取 1, 返回值即 dx + dy
return D * (dx + dy)
如果网格地图可以八方向(包括斜对角)移动, 使用 切比雪夫距离(Chebyshev distance) 作为启发函数比较合适.
function Chebyshev(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
// max(dx, dy) 保证了斜对角的距离计算
return D * max(dx, dy)
function heuristic(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
// 在最简单的情况下, D 可以取 1, 返回值即 sqrt(dx * dx + dy * dy)
return D * sqrt(dx * dx + dy * dy)
欧式距离因为有一个 sqrt() 运算, 计算开销会增大, 所以可以使用 Octile 距离 来优化(不知道怎么翻译), Octile 的核心思想就是假定只能做 45 度角转弯.
function heuristic(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
k = sqrt(2) - 1
return max(dx, dy) + k * min(dx, dy)
IDAStar¶
基于迭代加深与启发函数算法
问题: 旋转游戏 (类平面魔方)
题目地址https://www.luogu.com.cn/problem/UVA1343
启发函数¶
贪心思想: 每次操作最优只能减少一个错误值 因此最少需要操作 8 - 中心数最大和数值
AC Code
import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;
public class Main {
Scanner sin = new Scanner(System.in);
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer cin = new StreamTokenizer(in);
PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
final int N = 1010, mod = (int)(1e9+7), inf = 0x3f3f3f3f;
int nextInt() throws Exception {
cin.nextToken();
return (int) cin.nval;
}
/*
0 1
2 3
4 5 6 7 8 9 10
11 12
13 14 15 16 17 18 19
20 21
22 23
*/
int[][] op = {
{0, 2, 6, 11, 15, 20, 22},
{1, 3, 8, 12, 17, 21, 23},
{10, 9, 8, 7, 6, 5, 4},
{19, 18, 17, 16, 15, 14, 13},
{23, 21, 17, 12, 8, 3, 1},
{22, 20, 15, 11, 6, 2, 0},
{13, 14, 15, 16, 17, 18, 19},
{4, 5, 6, 7, 8, 9, 10}
};
int[] center = {6, 7, 8, 11, 12, 15, 16, 17};
int[] opposite = {5, 4, 7, 6, 1, 0, 3, 2};
int[] a = new int[24];
int[] path = new int[N];
int max_depth;
// 启发函数
int f() {
int[] sum = new int[4];
for (int i = 0; i < 4; i ++) sum[i] = 0;
for (int i = 0; i < 8; i ++) sum[a[center[i]]]++;
int res = 0;
for (int i = 1; i <= 3; i ++) res = Math.max(res, sum[i]);
return 8 - res;
}
boolean check() {
for (int i = 1; i < 8; i ++)
if (a[center[i]] != a[center[0]])
return false;
return true;
}
void operation(int x) {
int t = a[op[x][0]];
for (int i = 0; i < 6; i ++) a[op[x][i]] = a[op[x][i + 1]];
a[op[x][6]] = t;
}
boolean dfs(int depth, int last) {
if (depth + f() > max_depth) return false;
if (check()) return true;
for (int i = 0; i < 8; i ++) {
if (opposite[i] == last) continue;
path[depth] = i;
operation(i);
if (dfs(depth + 1, i)) return true;
operation(opposite[i]);
}
return false;
}
void solve() throws Exception {
while(true) {
for (int i = 0; i < 24; i ++) {
a[i] = nextInt();
if (a[0] == 0) return;
}
max_depth = 0;
while(!dfs(0, -1)) max_depth ++;
if (max_depth == 0) cout.print("No moves needed");
for (int i = 0; i < max_depth; i ++)
cout.print((char)('A' + path[i]));
cout.println("\n" + a[6]);
}
}
public static void main(String[] args) throws Exception {
Main cmd = new Main();
cmd.solve();
cmd.cout.close();
}
}
Astar¶
基于dfs与启发函数算法
问题第K短路
题目地址https://www.acwing.com/problem/content/180/
启发函数¶
使用dijkstra算法求最短距离做估价函数
AC Code
import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;
public class Main {
Scanner sin = new Scanner(System.in);
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer cin = new StreamTokenizer(in);
PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
final int N = 1010, mod = (int) (1e9 + 7), inf = 0x3f3f3f3f;
int nextInt() throws Exception {
cin.nextToken();
return (int) cin.nval;
}
int n, m, k, S, T, K;
class node {
int pos, dis;
node(int pos, int dis) {
this.pos = pos;
this.dis = dis;
}
}
List<node>[] G = new List[N];
List<node>[] RG = new List[N];
void init() {
for (int i = 0; i < N; i++) {
G[i] = new ArrayList<>();
RG[i] = new ArrayList<>();
dis[i] = inf;
}
}
void add(List<node>[] G, int a, int b, int c) {
G[a].add(new node(b, c));
}
boolean[] st = new boolean[N];
int[] dis = new int[N];
// dijkstar 求估计函数
void dijkstra() {
Queue<node> q = new PriorityQueue<>((node a, node b) -> {
return a.dis - b.dis;
});
q.add(new node(T, 0));
dis[T] = 0;
while(q.size() > 0) {
node t = q.poll();
if (st[t.pos]) continue;
st[t.pos] = true;
for (node i : RG[t.pos]) {
if (dis[i.pos] > dis[t.pos] + i.dis) {
dis[i.pos] = dis[t.pos] + i.dis;
q.add(new node(i.pos, dis[i.pos]));
}
}
}
}
class edge {
int pos, dis, f;
edge(int pos, int dis, int f) {
this.pos = pos;
this.dis = dis;
this.f = f;
}
}
int[] cnt = new int[N];
int Astar() {
Queue<edge> q = new PriorityQueue<>((edge a, edge b) -> {
return a.f - b.f;
});
q.add(new edge(S, 0, dis[S]));
while (q.size() > 0) {
edge t = q.poll();
cnt[t.pos] ++;
if (cnt[T] == K && t.pos == T) return t.dis;
if (cnt[t.pos] > K) continue;
for (node i : G[t.pos]) {
q.add(new edge(i.pos, t.dis + i.dis, t.dis + i.dis + dis[i.pos]));
}
}
return -1;
}
void solve() throws Exception {
init();
String[] op = in.readLine().split(" ");
n = Integer.parseInt(op[0]);
m = Integer.parseInt(op[1]);
while (m-- > 0) {
op = in.readLine().split(" ");
int a = Integer.parseInt(op[0]), b = Integer.parseInt(op[1]), c = Integer.parseInt(op[2]);
add(G, a, b, c);
add(RG, b, a, c);
}
op = in.readLine().split(" ");
S = Integer.parseInt(op[0]);
T = Integer.parseInt(op[1]);
K = Integer.parseInt(op[2]);
if (S == T) K++;
dijkstra();
if (dis[S] == inf) cout.println(-1);
else cout.println(Astar());
}
public static void main(String[] args) throws Exception {
Main cmd = new Main();
cmd.solve();
cmd.cout.close();
}
}