更新記錄
【1】2020.07.21-11:40
- 1.完善A*內容
【2】2020.08.30-16:55
- 1.完善例題決議
正文
[A problem]
如果讓你在這么一個方格圖中尋找最短路徑，你會怎么做？
Student-A：我會廣度優先演算法！
Student-B[最優]：我會貪心走過去！
上面是最簡單的狀況，如果有障礙物呢？
注：綠色格子不可通過
Student-A：我會廣度優先演算法與深度優先演算法！
Student-B：我，，
看起來此問題得到了解決，但是我們可以很快想到：樸素的搜索演算法最壞情況下竟需要遍歷整個圖！！
那么我們此時需要剪枝，那么如何剪呢？
最容易想到的就是在某一步發現不管怎么樣，都不可能達到目標情況或不是最優解，此時直接回溯，效率提高不少
用一個式子來表示就是：
\(s+h(s)>dep\)
\(s\)就是當前的步數，\(dep\)就是目標
那么其中的\(h(s)\)就是對當前的一個估計，稱為估價函式
當前步數+估計>目標，你還會走下去嗎？
當然不會，所以直接回溯
容易發現，估價函式越準確，\(s\)越小，程式越快；估計函式越不準，\(s\)越大，程式越慢
在尋找最短路的問題中，\(h(s)\)就是代表當前到終點的距離
在不同的問題中，\(h(s)\)也有不同的含義
P1379 八數碼難題
這里的\(h(s)\)就是沒有在正確位置上的數的個數
首先計算\(dep\)，即最少幾步即可到達目標狀況
隨著廣度的放寬，慢慢進行A*搜索尋找答案
函式中
if(!dis) return 1;
if(s+dis>stdep) return 0;
就是A*的核心
#include<iostream>
#include<cstdio>
#define R register
int goalx[9]={0,1,2,3,3,3,2,1,1},movx[4]={1,-1,0,0},zx;
int goaly[9]={0,1,1,1,2,3,3,3,2},movy[4]={0,0,1,-1},zy;
int stdep;
std::string begin;
inline int abs(int a){return a<0?-a:a;}
inline int GetRow(int a){return a%3+1;}
inline int GetColumn(int a){return a/3+1;}
inline int GetOriginal(int x,int y){return x-1+(y-1)*3;}
inline int GetDist(std::string a){
int dist=0,now=0;
for(R int i=0;i<a.length();i++){
now=a[i]-'0';
if(!now){
zx=GetRow(i),zy=GetColumn(i);
continue;
}
dist+=(abs(GetRow(i)-goalx[now]) + abs(GetColumn(i)-goaly[now]));
}
return dist;
}
inline bool A_star(int s,int pre){
int dis=GetDist(begin);
if(!dis) return 1;
if(s+dis>stdep) return 0;
for(R int i=0;i<4;i++){
int past=GetOriginal(zx,zy);
zx+=movx[i],zy+=movy[i];
int now=GetOriginal(zx,zy);
if(zx<1||zy<1||zx>3||zy>3||now==pre){
zx-=movx[i],zy-=movy[i];continue;
}
std::swap(begin[past],begin[now]);
if(A_star(s+1,past))
return 1;
std::swap(begin[past],begin[now]);
zx-=movx[i],zy-=movy[i];
}
return 0;
}
signed main(){
std::ios::sync_with_stdio(0);
std::cin>>begin;
stdep=GetDist(begin);
while(stdep<30){
if(A_star(0,-1))
break;
stdep+=1;
}
std::cout<<stdep;
}
P2324 [SCOI2005]騎士精神
同上，這里的\(h(s)\)是沒有在正確位置上的棋子的個數
#include<iostream>
#include<cstdio>
#define R register
using std::string;
string goal[5]={"11111","01111","00*11","00001","00000"},in[5];
int mx[8]={1,1,-1,-1,2,2,-2,-2},sx;
int my[8]={2,-2,2,-2,1,-1,1,-1},sy;
int t,dep;
inline int GetDist(string a[5]){
int dist=0;
for(R int i=0;i<5;i++)
for(R int o=0;o<5;o++){
if(a[i][o]=='*'){
sx=i,sy=o;
continue;
}
if(a[i][o]!=goal[i][o]) dist+=1;
}
return dist;
}
inline bool A_star(int s,int prex,int prey){
int dis=GetDist(in);
if(!dis) return 1;
if(s+dis>dep) return 0;
int sx2=sx,sx3=sx,sy2=sy,sy3=sy;
for(R int i=0;i<8;i++){
sx2+=mx[i],sy2+=my[i];
if(sx2<0||sy2<0||sx2>4||sy2>4||(prex==sx2&&prey==sy2)){
sx2-=mx[i],sy2-=my[i];
continue;
}
std::swap(in[sx3][sy3],in[sx2][sy2]);
if(A_star(s+1,sx3,sy3)) return 1;
std::swap(in[sx3][sy3],in[sx2][sy2]);
sx2-=mx[i],sy2-=my[i];
}
return 0;
}
signed main(){
scanf("%d",&t);
while(t--){
for(int i=0;i<5;i++) std::cin>>in[i];
dep=GetDist(in);
while(dep<16){
if(A_star(0,-1,-1))
break;
dep+=1;
}
if(dep==16) printf("-1\n");
else printf("%d\n",dep);
}
}
UVA1343 旋轉游戲 The Rotation Game
這里的\(h(s)\)是八宮格內還缺幾個數就滿足題意
讀入比較惡心，要小心寫代碼
我這篇好像是Luogu最優解
【代碼選注】
char Map[8]={'A','B','C','D','E','F','G','H'};
考慮到字典序的問題，我們列舉的時候1-8，最后來個對應
至于為啥不是i+'A'這種型別，為了保險（懶
int shrc[8]={1,2,3,4,2,1,4,3},dep;
int shru[8]={0,0,1,1,1,1,0,0},ans;
1-8所對應的狀態，為了好處理所以打亂順序，這相當于對應陣列
inline int GetSituation()
獲得情況，看看最少還有幾個數沒有回到位置上
inline void Change(char a[8],int rc,bool rule)
改動某一行
rule取值意義
-
0是左移（上移）
-
1是右移（下移）
rc取值意義：
-
1是豎著的左邊的
-
2是豎著的右邊的
-
3是橫著的上邊的
-
4是橫著的下邊的
if(!st){
ans=f[1][3]-'0';
return 1;
}
存在不需要搜索或搜索完畢的情況，此時記錄，退出
if(shrc[i]==prc&&shru[i]!=pru) continue;
防止出現兩次移動相當于沒移的情況
Change(f[shrc[i]],shrc[i],!shru[i]);
相反方向回溯
#include<iostream>
using std::cin;
using std::cout;
char f[5][8],lu[100],Map[8]={'A','B','C','D','E','F','G','H'};
int shrc[8]={1,2,3,4,2,1,4,3},dep;
int shru[8]={0,0,1,1,1,1,0,0},ans;
inline int Tmax(int a,int b,int c){return a>b?(a>c?a:c):(b>c?b:c);}
inline int GetSituation(){
int a[4]={0,0,0,0};
a[f[1][3]-'0']+=1;a[f[1][4]-'0']+=1;a[f[1][5]-'0']+=1;
a[f[2][3]-'0']+=1;a[f[2][4]-'0']+=1;a[f[2][5]-'0']+=1;
a[f[3][4]-'0']+=1;a[f[4][4]-'0']+=1;
return 8-Tmax(a[1],a[2],a[3]);
}
inline void Change(char a[8],int rc,bool rule){
char head;
if(rule){
head=a[7];
for(int i=6;i>0;i--) a[i+1]=a[i];
a[1]=head;
}
else{
head=a[1];
for(int i=1;i<7;i++) a[i]=a[i+1];
a[7]=head;
}
switch(rc){
case 1: f[3][3]=f[1][3],f[4][3]=f[1][5];break;
case 2: f[3][5]=f[2][3],f[4][5]=f[2][5];break;
case 3: f[1][3]=f[3][3],f[2][3]=f[3][5];break;
case 4: f[1][5]=f[4][3],f[2][5]=f[4][5];break;
}
}
inline bool A_star(int s,int prc,int pru){
int st=GetSituation();
if(!st){
ans=f[1][3]-'0';
return 1;
}
if(s+st>dep) return 0;
for(int i=0;i<8;i++){
if(shrc[i]==prc&&shru[i]!=pru) continue;
Change(f[shrc[i]],shrc[i],shru[i]);
lu[s]=Map[i];
if(A_star(s+1,shrc[i],shru[i])) return 1;
Change(f[shrc[i]],shrc[i],!shru[i]);
}
return 0;
}
signed main(){
while(1){
cin>>f[1][1];if(f[1][1]=='0') break;
cin>>f[2][1]>>f[1][2]>>f[2][2];
for(int i=1;i<8;i++) cin>>f[3][i];
f[1][3]=f[3][3],f[2][3]=f[3][5];
cin>>f[1][4]>>f[2][4];
for(int i=1;i<8;i++) cin>>f[4][i];
f[1][5]=f[4][3],f[2][5]=f[4][5];
cin>>f[1][6]>>f[2][6]>>f[1][7]>>f[2][7];
dep=GetSituation();ans=f[1][3]-'0';
while(!A_star(0,-1,-1)) dep+=1;
if(!dep) cout<<"No moves needed";
else for(int i=0;i<dep;i++) cout<<lu[i];
cout<<"\n"<<ans<<"\n";
}
}
容易發現，A*與IDA*就是在原搜索的基礎上加上幾行優化的東西，所以啟發式搜索并沒有那么難
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/17892.html
標籤：其他