差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:no_morning_training:shaco:知识点:搜索:a [2020/08/20 19:24]
shaco
+++ 2020-2021:teams:no_morning_training:shaco:知识点:搜索:a [2020/08/20 19:30] (当前版本)
shaco
@@ 行 1: / 行 1: @@
 ====== A* ======
 ===== 简介&思想 =====
-通过估价函数预计搜索到的结点与终点的距离，以估价距离从小到大为顺序搜索终点，得到最短路，减少搜索时间。与dijkstra相似。
+通过估价函数预计搜索到的结点与终点的距离，以估价距离从小到大为顺序搜索终点，得到最短路，减少搜索时间。与dijkstra相似。\\
+估价函数越大搜索越少，但估价函数小于等于真实距离时才能得到正确的结果，因此要注意估价函数的选取，可以调整估价函数的倍数。
 ===== 例题 =====
 ==== 八数码难题 ====
@@ 行 12: / 行 13: @@
 <hidden code>
 <code cpp>
+#include<cstdio>
+#include<map>
+#include<queue>
+#include<string>
+#include<cstring>
+using namespace std;
+map<string,int>vist,D,H;
+struct unit
+{
+    string state;
+    int d,h,f,p;
+    bool operator < (const unit&x) const
+    {
+        return f>x.f;
+    }
+};
+priority_queue<unit>q;
+string End("123804765");
+int targ[9]={4,0,1,2,5,8,7,6,3},dpos[4][9]={{-1,-1,-1,0,1,2,3,4,5},{3,4,5,6,7,8,-1,-1,-1},{-1,0,1,-1,3,4,-1,6,7},{1,2,-1,4,5,-1,7,8,-1}};
+int dis[9][9]={{0,1,2,1,2,3,2,3,4},{1,0,1,2,1,2,3,2,3},{2,1,0,3,2,1,4,3,2},{1,2,3,0,1,2,1,2,3},{2,1,2,1,0,1,2,1,2},{3,2,1,2,1,0,3,2,1},{2,3,4,1,2,3,0,1,2},{3,2,3,2,1,2,1,0,1},{4,3,2,3,2,1,2,1,0}};
+void read()
+{
+    string s;
+    s.resize(9);
+    scanf("%s",&s[0]);
+    unit zero;
+    zero.state=s;
+    zero.d=zero.h=0;
+    for(int i=0;i<9;i++)
+    {
+        zero.h+=dis[i][targ[s[i]-48]];
+        if(s[i]==48)
+            zero.p=i;
+    }
+    zero.f=zero.h>>1;
+    q.push(zero);
+    D[s]=0;
+    H[s]=zero.h;
+}
+int main()
+{
+    read();
+    int m=1;
+    unit head;
+    while(m--)
+    {
+        head=q.top();
+        q.pop();
+        if(head.state==End)
+        {
+            printf("%d",head.d);
+            return 0;
+        }
+        if(vist[head.state]==-1)
+            continue;
+        vist[head.state]=-1;
+        string state_;
+        for(int i=0,p_,h_,d_;i<4;i++)
+        {
+            p_=dpos[i][head.p];
+            if(p_>=0)
+            {
+                state_=head.state;
+                state_[head.p]=state_[p_];
+                state_[p_]=48;
+                if(vist[state_]==-1) continue;
+                d_=head.d+1;
+                if(!vist[state_])
+                {
+                    h_=head.h-dis[head.p][targ[0]]-dis[p_][targ[head.state[p_]-48]]+dis[head.p][targ[state_[head.p]-48]]+dis[p_][targ[0]];
+                    q.push({state_,d_,h_,d_+(h_>>1),p_});
+                    m++;
+                    D[state_]=d_;
+                    H[state_]=h_;
+                    vist[state_]=1;
+                }
+                else if(d_<D[state_])
+                {
+                    q.push({state_,d_,d_+(H[state_]>>1),p_});
+                    m++;
+                    D[state_]=d_;
+                }
+            }
+        }
+    }
+    return 0;
+}
 </code>
 </hidden>
 ----
 ===== 总结 =====

CVBB ACM Team

用户工具

站点工具

差别

页面工具