有N個傳教士和N個野人來到河邊渡河，河岸有一條船，每次至多可供k人乘渡。河兩岸以及船上的野人數(shù)目總是不超過傳教士的數(shù)目(否則不安全，傳教士有可能被野人吃掉)。即求解傳教士和野人從左岸全部擺渡到右岸的過程中，任何時刻滿足M(傳教士數(shù))≥C(野人數(shù))和M+C≤k的擺渡方案。針對以上問題，采用java編程語言設(shè)計實現(xiàn)界面程序集成A*算法解決運輸方案。

一、程序設(shè)計

本次Java實現(xiàn)A*搜索算法界面模擬解決傳教士與野人問題程序主要內(nèi)容涉及：

主要功能模塊：參數(shù)設(shè)置、演示控制、動畫模擬、A算法實現(xiàn)與集成等
主要包含技術(shù)：JavaSwing，Java2D，算法
主要包含算法及方法：A搜索算法，動畫模擬

系統(tǒng)采用前端采用JavaSwing實現(xiàn)，后臺服務(wù)基于java編程語言實現(xiàn)算法，界面動畫，運輸方案過程計算，配合A*算法實現(xiàn)傳教士與野人問題輸送過程中的沖突問題，系統(tǒng)前后端數(shù)據(jù)交互，采用界面監(jiān)聽器調(diào)用傳輸實現(xiàn)。

二、效果實現(xiàn)

初始界面

image.png

動態(tài)模擬

gcys.gif

其他效果省略

三、A*算法設(shè)計

本次畢設(shè)系統(tǒng)在計算過程中，主要采用A*算法，針對運輸過程需要考慮的傳教士數(shù)據(jù)，野人數(shù)據(jù)等抽象成具體的實體類封裝各自屬性，實現(xiàn)運輸沖突解決，生成運輸方案等。

算法代碼

public class AStar {
    // 系統(tǒng)容忍最大數(shù)值
    final int N = 65535;
    // 船上可容納人數(shù)
    private int kofmc;
    // 野人和傳教士人數(shù)
    public int nofmc;
    // 當前已經(jīng)產(chǎn)生的結(jié)點序號
    private int number;
    // 存放狀態(tài)節(jié)點
    private Status tree[] = new Status[N];
    // 存放路徑
    public Display dp[] = new Display[N];
    // 找到最優(yōu)解的標識
    public int found = 0;
    public int Start = 0;
    // 路徑節(jié)點數(shù)
    public int num;
    private boolean large = false;
    public AStar(int nofmc, int kofmc) {
        this.nofmc = nofmc;
        this.kofmc = kofmc;
        if(this.nofmc >= N) {
            large = true;
            found = -1;
            System.out.println("輸入太大！");
            return;
        }
        for(int i = 0; i < N; i++) {
            tree[i] = new Status();
            dp[i] = new Display();
        }
    }
    // 估計函數(shù)
    private float estimate(int M,int C,int B,int depth) {
        float retu = depth+B+((float)M+C)/kofmc;
        return retu;
    }
    //總的約束條件
    private boolean res(int M,int C) {
        return ((M==C)&&(M<=nofmc)&&(C<=nofmc)&&(M>=0)&&(C>=0))||((M==0)&&(C<=nofmc)&&(C>=0))||((M==nofmc)&&(C>=0)&&(C<=nofmc));
    }
    //判斷是否為父結(jié)點
    private boolean isParent(int M, int C, int B, int depth, int target) {
        Status ps = null;
        ps=new Status();
        int point = target;
        ps.M = tree[point].M;
        ps.C = tree[point].C;
        ps.B = tree[point].B;
        ps.depth = tree[point].depth;
        ps.point = tree[point].point;
        while(ps.point != -1) {
            int ms,cs,bs;
            ms = ps.M;
            cs = ps.C;
            bs = ps.B;
            if((M==ms)&&(C==cs)&&(B!=bs)) {
                return true;
            }
            point = ps.point;
            ps.M = tree[point].M;
            ps.C = tree[point].C;
            ps.B = tree[point].B;
            ps.depth = tree[point].depth;
            ps.point = tree[point].point;
        }
        return false;
    }
    // 生成新節(jié)點
    private void create(int M,int C,int B,int depth,int target) {
        if(res(M,C)) {
            if(!(isParent(M,C,B,depth,target))) {
                // 在不在表中的標志
                int signal=0;
                for(int i = 0; i <= number; i++) {
                    int sign = tree[i].oorc;
                    int ms = tree[i].M;
                    int cs = tree[i].C;
                    int bs = tree[i].B;
                    int ds = tree[i].depth;
                    // 如果在open表中
                    if(sign == 0) {
                        if((M==ms)&&(C==cs)&&(B!=bs)) {
                            signal=1;
                            if(depth<(ds-1)) {
                                tree[i].point = target;
                                tree[i].depth = tree[target].depth+1;
                            }
                            break;
                        }
                    }
                    // 如果在closed表中
                    if(sign==1) {
                        if((M==ms)&&(C==cs)&&(B!=bs)) {
                            signal=1;
                            if(depth<(ds-1)) {
                                tree[i].point = target;
                                tree[i].depth = tree[target].depth+1;
                            }
                        }
                    }
                }
                //如果不在表中
                if(signal == 0) {
                    number++;
                    if(number >= N) {
                        found = -1;
                        System.out.println("數(shù)值太大！");
                        return;
                    }
                    tree[number].M=M;
                    tree[number].C=C;
                    tree[number].B=(B==0?1:0);
                    tree[number].depth=tree[target].depth+1;
                    tree[number].point = target;
                    tree[number].oorc = 0;
                }
            }
        }
    }
    //擴展節(jié)點
    private void extend(int M,int C,int B,int depth,int target) {
        if(B == 1) {
            for(int i = 1; i <= kofmc; i++) {
                M -= i;
                create(M,C,B,depth,target);
                M += i;
            }
            for(int j = 1; j <= kofmc; j++) {
                C -= j;
                create(M,C,B,depth,target);
                C += j;
            }
            for(int k = 1; k < kofmc; k++) {
                M -= k;
                for(int x = 1; x <= ((kofmc>2*k)?k:(kofmc-k)); x++) {
                    C -= x;
                    create(M,C,B,depth,target);
                    C += x;
                }
                M+=k;
            }
        } else {
            for(int i = 1; i <= kofmc; i++) {
                M += i;
                create(M,C,B,depth,target);
                M -= i;
            }
            for(int j = 1; j <= kofmc; j++) {
                C += j;
                create(M,C,B,depth,target);
                C -= j;
            }
            for(int k = 1; k < kofmc; k++) {
                M += k;
                for(int x=1; x<=((kofmc>2*k)?k:(kofmc-k)); x++) {
                    C += x;
                    create(M,C,B,depth,target);
                    C -= x;
                }
                M -= k;
            }
        }
    }
    private void change(int target) {
        tree[target].oorc=1;
    }
    private int excellent() {
        float min=32767;
        int target=-1;
        for(int i = 0; i <= number; i++) {
            int or=tree[i].oorc;
            if(or == 0) {
                int M, C, B, depth;
                float m;
                M = tree[i].M;
                C = tree[i].C;
                B = tree[i].B;
                depth = tree[i].depth;
                m = estimate(M, C, B, depth);
                if(m < min) {
                    min = m;
                    target = i;
                }
            }
        }
        return target;
    }
    public void start() {
        if(large) {
            found = -1;
            return;
        }
        Start=1;
        found=0;
        number=0;
        // 初始化tree
        tree[0].M=nofmc;
        tree[0].C=nofmc;
        tree[0].B=1;
        tree[0].depth=0;
        tree[0].oorc=0;
        tree[0].point = -1;
        int target=0;
        int point;
        point = target;
        while(point != -1) {
            int M,C,B,depth,mt,ct;
            M = tree[target].M;
            C = tree[target].C;
            B = tree[target].B;
            depth = tree[target].depth;
            extend(M,C,B,depth,target);
            change(target);
            target=excellent();
            if(target == -1) {
                System.out.println("no solution");
                break;
            }
            if(number >= N) {
                found = -1;
                System.out.println("too large number course exit!");
                break;
            }
            point = target;
            mt=tree[target].M;
            ct=tree[target].C;
            if((mt==0)&&(ct==0)) {
                int ps;
                ps = target;
                int numtemp=0;
                while(ps != -1) {
                    numtemp++;
                    ps = tree[ps].point;
                }
                num = numtemp;
                ps = target;
                while(ps != -1) {
                    numtemp--;
                    dp[numtemp].missi =tree[ps].M;
                    dp[numtemp].canni =tree[ps].C;
                    dp[numtemp].boat=tree[ps].B;
                    ps = tree[ps].point;
                }
                found=1;
                break;
            }
        }
    }
}