AI-路径导航（最短路径算法 and A算法）

84 阅读 0 评论 56 点赞

我是靠谱客的博主专一小白菜，最近开发中收集的这篇文章主要介绍AI-路径导航（最短路径算法 and A算法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

输入：城市坐标文件，需导航两个城市编号

输出：路径序列就路径长度

2.1 试采用最短路径算法实现，分析其存在的主要问题；

2.2 设计适当的启发式策略，采用A算法实现

最短路径：

#include <cstdio>//with this method,we can find all the shortest ways from the start point to any other points.
#include <iostream>
#include <algorithm>
#include <fstream>
#include <string>
#include <sstream>
#include <cmath>
#include <set>
#include <cstring>
using namespace std;//the problem of this shortest-path method is that you must find the best way of every other point.Tihs will be very complex when the amount of points increase.
#define N 13
#define BG 1100000000
double pmap[N][N];//point map

char sp,tp;
int sn,tn;

struct point{
    int num;
    double dist;
    int pnum;
    bool operator < (const point &a)const
    {
        return a.dist>dist;//order the set by dist
    }
};

multiset<point>qo;//balace tree~,every time we should find the point wihch is closest to the start point quickly.
multiset<point>qc;//to find the whole
multiset<point>::iterator it;
point inp,outp;
double d[N];
int p[N];//p[N] stores the best parent of every point

void input()//the format of the first 8 lines is"cityname x y",and the following lines are the cities which are connected.
{
    cin>>sp>>tp;
    
    ifstream OpenFile("/Users/liuyuhan/Desktop/Blue_Home/MyTest/AMusic/LineLandMail/CityPoints.txt");
    string ch;
    int cityx[N],cityy[N];
    int i;
    while(!OpenFile.eof())
    {
        int hl,vl;
        char city;
        int x,y;
        char Xcity,Ycity;
        getline(OpenFile,ch);
        stringstream seg;
        seg.str(ch);
        if(i<N)
        {
            
            seg>>city;
            seg>>x;
            seg>>y;
            cityx[city-'A']=x;//the horizen index of the city
            cityy[city-'A']=y;//the vertical index of the city
        }
        else
        {
            //int x,y;
            seg>>Xcity;
            seg>>Ycity;
            x=Xcity-'A';//the one city
            y=Ycity-'A';//the other city
            hl=abs(cityx[x]-cityx[y]);//horizen length
            vl=abs(cityy[x]-cityy[y]);
            pmap[x][y]=sqrt((double)(hl*hl+vl*vl));
            pmap[y][x]=pmap[x][y];
        }
        i++;
        
    }
    OpenFile.close();
}

void print_out()
{
    char pc[N];
    int i=0;
    pc[0]=tp;
    int a=p[tn];
    while(a!=-1)
    {
        pc[++i]=a+'A';
        a=p[a];
    }
    i++;
    while(i--)
    {
        if(i>0)
            printf("%c->",pc[i]);
        else
            printf("%cn",tp);
    }
    printf("%0.4f",d[tn]);
    //cout<<endl;
}

void solve(int s,int t)
{
    inp.num=s;
    inp.dist=0;
    inp.pnum=-1;
    qo.insert(inp);
    it=qo.begin();
    int i;
    
    while(it->num!=t)
    {
        outp=*it;
        qc.insert(outp);
        qo.erase(it);
        for(i=0;i<N;i++)
            if(pmap[outp.num][i]!=0&&i!=outp.pnum)//the point can be expanded
            {
                inp.num=i;
                inp.dist=outp.dist+pmap[outp.num][i];
                inp.pnum=outp.num;
                if(d[inp.num]>inp.dist)
                {
                    d[inp.num]=inp.dist;
                    p[inp.num]=outp.num;
                }
                qo.insert(inp);
            }
        it=qo.begin();
    }
    print_out();
}
int main()
{
    input();
    sn=sp-'A';
    tn=tp-'A';
    for(int i=0;i<N;i++)
        d[i]=BG;
    d[sn]=0;
    p[sn]=-1;
    solve(sn,tn);
    
    
}

A算法：

#include <cstdio>//with this method,we can find all the shortest ways from the start point to any other points.
#include <iostream>
#include <algorithm>
#include <fstream>
#include <string>
#include <sstream>
#include <cmath>
#include <set>
#include <cstring>
using namespace std;
#define N 13//there are 13 cities,and it can be more in fact.
#define BG 1100000000
double pmap[N][N];//point map

char sp,tp;
int sn,tn;

struct point{
    int num;
    double gdis;
    double fdis;
    int pnum;
    bool operator < (const point &a)const
    {
        return a.fdis>fdis;//order the set by fdis(fdis=g[num]+h[num])
    }
};

multiset<point>qo;//balace tree~,every time we should find the point wihch is closest to the start point quickly.
multiset<point>qc;//to find the whole
multiset<point>::iterator it;
point inp,outp;
double d[N];
int p[N];//p[N] stores the best parent of every point
int cityx[N],cityy[N];
double h[N];//that's the straight diastance from i to t

void input()//the format of the first 8 lines is"cityname x y",and the following lines are the cities which are connected.
{
    cin>>sp>>tp;
    
    ifstream OpenFile("/Users/liuyuhan/Desktop/Blue_Home/MyTest/AMusic/LineLandMail/CityPoints.txt");
    string ch;
    
    int i;
    while(!OpenFile.eof())
    {
        int hl,vl;
        char city;
        int x,y;
        char Xcity,Ycity;
        getline(OpenFile,ch);
        stringstream seg;
        seg.str(ch);
        if(i<N)
        {
            
            seg>>city;
            seg>>x;
            seg>>y;
            cityx[city-'A']=x;//the horizen index of the city
            cityy[city-'A']=y;//the vertical index of the city
        }
        else
        {
            //int x,y;
            seg>>Xcity;
            seg>>Ycity;
            x=Xcity-'A';//the one city
            y=Ycity-'A';//the other city
            hl=abs(cityx[x]-cityx[y]);//horizen length
            vl=abs(cityy[x]-cityy[y]);
            pmap[x][y]=sqrt((double)(hl*hl+vl*vl));
            pmap[y][x]=pmap[x][y];
        }
        i++;
        
    }
    OpenFile.close();
}

void print_out()
{
    char pc[N];
    int i=0;
    pc[0]=tp;
    int a=p[tn];
    while(a!=-1)
    {
        pc[++i]=a+'A';
        a=p[a];
    }
    i++;
    while(i--)
    {
        if(i>0)
            printf("%c->",pc[i]);
        else
            printf("%cn",tp);
    }
    printf("%0.4fn",d[tn]);
    //cout<<endl;
}

void solve(int s,int t)
{
    inp.num=s;
    inp.gdis=0;
    inp.fdis=0+h[s];
    inp.pnum=-1;
    qo.insert(inp);
    it=qo.begin();
    int i;
    
    while(it->num!=t)
    {
        outp=*it;
        qc.insert(outp);
        qo.erase(it);
        for(i=0;i<N;i++)
            if(pmap[outp.num][i]!=0&&i!=outp.pnum)//the point can be expanded
            {
                inp.num=i;
                inp.gdis=outp.gdis+pmap[outp.num][i];
                inp.fdis=inp.gdis+h[i];//that's the A method's important part
                inp.pnum=outp.num;
                if(d[inp.num]>inp.gdis)
                {
                    d[inp.num]=inp.gdis;
                    p[inp.num]=outp.num;
                }
                qo.insert(inp);
            }
        it=qo.begin();
    }
    print_out();
}
int main()
{
    input();
    sn=sp-'A';
    tn=tp-'A';
    for(int i=0;i<N;i++)
        d[i]=BG;
    d[sn]=0;
    p[sn]=-1;
    int i;
    for(i=0;i<N;i++)
    {
        int hx=abs(cityx[i]-cityx[tn]);
        int hy=abs(cityy[i]-cityy[tn]);
        h[i]=sqrt((double)(hx*hx+hy*hy));
    }
    solve(sn,tn);
    
    
}