国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專(zhuān)欄INFORMATION COLUMN

八數(shù)碼問(wèn)題求解(1)深度優(yōu)先搜索

jayce / 2961人閱讀

摘要:老師讓用中方式都實(shí)現(xiàn)一遍,分別是廣度優(yōu)先搜索深度優(yōu)先搜索和啟發(fā)式搜索。先分享深度優(yōu)先搜索,后兩篇我會(huì)分享廣度優(yōu)先搜索和啟發(fā)式搜索的實(shí)現(xiàn)。

人工智能課,第一個(gè)實(shí)驗(yàn)就是八數(shù)碼問(wèn)題。老師讓用3中方式都實(shí)現(xiàn)一遍,分別是廣度優(yōu)先搜索、深度優(yōu)先搜索和啟發(fā)式搜索。心塞╮(╯▽╰)╭。緊急補(bǔ)了一些數(shù)據(jù)結(jié)構(gòu)的知識(shí),就匆匆上陣。先分享深度優(yōu)先搜索,后兩篇我會(huì)分享廣度優(yōu)先搜索和啟發(fā)式搜索的實(shí)現(xiàn)。

概念就不講了,百度就行了。簡(jiǎn)單說(shuō)一下我的實(shí)現(xiàn):Situation類(lèi)存儲(chǔ)節(jié)點(diǎn)信息,包括父節(jié)點(diǎn)的code值(code是一個(gè)字符串,存儲(chǔ)的是八數(shù)碼的狀態(tài),比如“138427056”),當(dāng)前節(jié)點(diǎn)的code值,以及深度(深度從0開(kāi)始,即起始節(jié)點(diǎn)深度為0);在Test.cpp的main函數(shù)中,我定義了兩個(gè)鏈表open和closed分別存放未被擴(kuò)展的節(jié)點(diǎn)和被擴(kuò)展的節(jié)點(diǎn)。深度優(yōu)先,新生成的有效的子節(jié)點(diǎn)存放在open表的開(kāi)頭。每次擴(kuò)展,拿open表的開(kāi)頭的那個(gè)節(jié)點(diǎn)來(lái)擴(kuò)展,方法是把open表的頭節(jié)點(diǎn)移動(dòng)到closed表的末端,生成的最多4個(gè)有效的子節(jié)點(diǎn)存放在open表的開(kāi)頭。其他就是比較生成的節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)是否相等了。

以下代碼在win8.1下VS2013中測(cè)試成功。

頭文件Deep.h:

#include
#include"queue"
#include"string"
#include

using namespace std;

const string GOAL = "803214765";

class Situation{
private:
    
public:
    string father;
    string code;//當(dāng)前狀態(tài)
    int deep;
    Situation up();
    Situation down();
    Situation left();
    Situation right();
    bool isGoal();
    bool isInOpen(deque &open);
    bool isInClosed(deque &closed);
    void show() const;
    void show(string) const;
    void show_deque(deque &) const;
    deque showWay(deque &closed);
    void showAnswer(deque &closed);//顯示解答
    Situation() :father(""), code(""), deep(-1){};
};

Deep.cpp:

#include"Deep.h"

Situation Situation::up(){
    string::size_type loc = code.find("0");//0的位置,從0開(kāi)始計(jì)數(shù)
    Situation son;
    son.code = code;
    son.deep = deep + 1;
    if (loc>=3){
        char temp = son.code[loc];//即0
        son.code[loc] = son.code[loc - 3];
        son.code[loc-3] = temp;
    }
    else{
        son.code = "";
    }
    return son;
}

Situation Situation::down(){
    string::size_type loc = code.find("0");//0的位置,從0開(kāi)始計(jì)數(shù)
    Situation son;
    son.code = code;
    son.deep = deep + 1;
    if (loc<=5){
        char temp = son.code[loc];//即0
        son.code[loc] = son.code[loc + 3];
        son.code[loc + 3] = temp;
    }
    else{
        son.code = "";
    }
    return son;
}

Situation Situation::left(){
    string::size_type loc = code.find("0");//0的位置,從0開(kāi)始計(jì)數(shù)
    Situation son;
    son.code = code;
    son.deep = deep + 1;
    if (loc!=0&&loc!=3&&loc!=6){
        char temp = son.code[loc];//即0
        son.code[loc] = son.code[loc - 1];
        son.code[loc - 1] = temp;
    }
    else{
        son.code = "";
    }
    return son;
}

Situation Situation::right(){
    string::size_type loc = code.find("0");//0的位置,從0開(kāi)始計(jì)數(shù)
    Situation son;
    son.code = code;
    son.deep = deep + 1;
    if (loc!=2&&loc!=5&&loc!=8){
        char temp = son.code[loc];//即0
        son.code[loc] = son.code[loc + 1];
        son.code[loc + 1] = temp;
    }
    else{
        son.code = "";
    }
    return son;
}

bool Situation::isGoal(){
    return code == GOAL;
}

bool Situation::isInOpen(deque &open){
    /*deque::iterator it = open.begin();
    while (it != open.end()){
        if (code == (*it).code){
            return true;
        }
        it++;
    }*/
    for (int i = 0; i < open.size();i++){
        if (code==open.at(i).code){
            return true;
        }
    }
    return false;
}

bool Situation::isInClosed(deque &closed){
    /*deque::iterator it = closed.begin();
    while (it!=closed.end()){
        if (code == (*it).code){
            return true;
        }
        it++;
    }*/
    for (int i = 0; i < closed.size(); i++){
        if (code == closed.at(i).code){
            return true;
        }
    }
    return false;
}

void Situation::show() const{
    if (!code.empty()){
        cout << code[0] << code[1] << code[2] << endl
            << code[3] << code[4] << code[5] << endl
            << code[6] << code[7] << code[8] << endl << endl;
    }
    else{
        cout << "空的" << endl;
    }
}

void Situation::show(string code) const{
    if (!code.empty()){
        cout << code[0] << code[1] << code[2] << endl
            << code[3] << code[4] << code[5] << endl
            << code[6] << code[7] << code[8] << endl << endl;
    }
    else{
        cout << "空的" << endl;
    }
}

void Situation::show_deque(deque &m_deque) const{
    /*deque::iterator it = m_deque.begin();
    while (it!=m_deque.end())
    {
        (*it).show();
        it++;
    }*/
    for (int i = 0; i < m_deque.size();i++){
        m_deque.at(i).show();
    }
}

//路徑
deque Situation::showWay(deque &closed){
    //cout << closed.size() << endl;
    deque dequeList;
    Situation temp = closed.back();
    dequeList.push_back(temp);

    //closed表從后往前,根據(jù)father值找到路徑
    for (int i = closed.size()-1; i >= 0;i--){
        if (temp.father==closed.at(i).code){
            dequeList.push_back(closed.at(i));
            temp = closed.at(i);
        }
    }
    //cout << dequeList.size() << endl;
    return dequeList;
}

void Situation::showAnswer(deque &closed){
    deque way(showWay(closed));
    cout << "共需要" << way.size() << "步" << endl;
    for (int i = way.size() - 1; i >= 0; i--)
    {
        way.at(i).show();
    }
    //輸出目標(biāo)
    show(GOAL);
}

Test.cpp:

#include
#include"Deep.h"

using namespace std;

void loop(deque &open, deque &closed, int range);

int main(){
    string original = "283164705";
    Situation first;
    deque open, closed;//open存放未擴(kuò)展節(jié)點(diǎn),closed存放已擴(kuò)展節(jié)點(diǎn)
    int range = 10;//深度界限

    first.code = original;
    first.deep = 0;
    open.push_back(first);
    loop(open,closed,range);
    return 0;
}

void loop(deque &open, deque &closed,int range){
    Situation a;
    int i = 0;
    while (!open.empty()){
        cout << i++ << endl;
        if (open.front().code == GOAL){
            cout << "成功:" << endl;
            a.showAnswer(closed);
            return;
        }
        if (open.empty()){
            cout << "失敗" << endl;
            return;
        }
        closed.push_back(open.front());
        open.pop_front();
        //節(jié)點(diǎn)n的深度是否等于深度界限
        if (closed.back().deep == range){
            //loop(open,closed,range);不能用遞歸
            continue; 
        }
        else{
            //擴(kuò)展節(jié)點(diǎn)n,把其后裔節(jié)點(diǎn)放入OPEN表的末端
            Situation son1 = closed.back().up();
            Situation son2 = closed.back().down();
            Situation son3 = closed.back().left();
            Situation son4 = closed.back().right();
            /*
            廣度優(yōu)先搜索和深度優(yōu)先搜索的唯一區(qū)別就是子節(jié)點(diǎn)放到open表的位置:
            (1)廣度優(yōu)先搜索放到open表的后面
            (2)深度優(yōu)先搜索放到open表的前面
            */
            if (!son1.code.empty()){
                if (!son1.isInOpen(open)&&!son1.isInClosed(closed)){
                    son1.father = closed.back().code;
                    open.push_front(son1);
                }
            }
            if (!son2.code.empty()){
                if (!son2.isInOpen(open) && !son2.isInClosed(closed)){
                    son2.father = closed.back().code;
                    open.push_front(son2);
                }
            }
            if (!son3.code.empty()){
                if (!son3.isInOpen(open) && !son3.isInClosed(closed)){
                    son3.father = closed.back().code;
                    open.push_front(son3);
                }
            }
             if (!son4.code.empty()){
                if (!son4.isInOpen(open) && !son4.isInClosed(closed)){
                    son4.father = closed.back().code;
                    open.push_front(son4);
                }
                
            }
            //是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)
            if (son1.isGoal()){
                cout << "后繼節(jié)點(diǎn)中有目標(biāo)節(jié)點(diǎn):" << endl;
                son1.showAnswer(closed);
                break;
            }
            if (son2.isGoal()){
                cout << "后繼節(jié)點(diǎn)中有目標(biāo)節(jié)點(diǎn):" << endl;
                son2.showAnswer(closed);
                break;
            }
            if (son3.isGoal()){
                cout << "后繼節(jié)點(diǎn)中有目標(biāo)節(jié)點(diǎn):" << endl;
                son3.showAnswer(closed);
                break;
            }
            if (son4.isGoal()){
                cout << "后繼節(jié)點(diǎn)中有目標(biāo)節(jié)點(diǎn):" << endl;
                son4.showAnswer(closed);
                break;
            }
        }
    }
}

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/19590.html

相關(guān)文章

  • 基于JavaScript求解數(shù)碼最短路徑并生成動(dòng)畫(huà)效果

    摘要:寫(xiě)在最前本次分享一下通過(guò)廣度優(yōu)先搜索解決八數(shù)碼問(wèn)題并展示其最短路徑的動(dòng)畫(huà)效果。一個(gè)排列中逆序的總數(shù)就稱(chēng)為這個(gè)排列的逆序數(shù)。如果起始狀態(tài)與結(jié)束狀態(tài)的逆序數(shù)的奇偶性相同,則說(shuō)明狀態(tài)可達(dá),反之亦然。 寫(xiě)在最前 本次分享一下通過(guò)廣度優(yōu)先搜索解決八數(shù)碼問(wèn)題并展示其最短路徑的動(dòng)畫(huà)效果。 歡迎關(guān)注我的博客,不定期更新中—— 效果預(yù)覽 該效果為從[[2, 6, 3],[4, 8, 0],[7, 1, ...

    Jioby 評(píng)論0 收藏0
  • 人工智能導(dǎo)論 (七) - 搜索求解策略

    摘要:搜索的概念盲目搜索與啟發(fā)式搜索狀態(tài)空間知識(shí)表示法狀態(tài)空間的表示法狀態(tài)空間的圖描述啟發(fā)式圖搜索啟發(fā)式策略運(yùn)用啟發(fā)式策略的兩種基本情況啟發(fā)信息和估價(jià)函數(shù)啟發(fā)信息估價(jià)函數(shù)注意八數(shù)碼問(wèn)題的啟發(fā)函數(shù)搜索算法搜索算法及其特性分析可采納性單調(diào)性信息性 showImg(https://segmentfault.com/img/remote/1460000017465711);showImg(https...

    yanwei 評(píng)論0 收藏0
  • 如何求ABC的全排列?--如何理解回溯算法?

    摘要:它真的是深度優(yōu)先搜索嗎是真的嗎是真的如果是的話(huà),那它的搜索空間解空間是什么是向量組成的集合,而。既然深度優(yōu)先搜索剪枝回溯。 什么是全排列?從n個(gè)不同元素中任取m(m≤n)個(gè)元素,按照一定的順序排列起來(lái),叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列。那么ABC的全排列有哪些?根據(jù)定義得到:ABCACBBACBCACABCBA 如何通過(guò)程序求解?方法一:暴力...

    zero 評(píng)論0 收藏0
  • 算法思想

    摘要:基礎(chǔ)算法思想類(lèi)別遞推枚舉遞歸分治貪婪回溯試探模擬遞推遞推分類(lèi)順推法從已知條件出發(fā),逐步推算出要解決問(wèn)題的方法。貪心算法的局限不能保證最后的解是最優(yōu)的不能求最大最小解問(wèn)題只能求滿(mǎn)足某些約束條件的可行解范圍。 基礎(chǔ)算法思想類(lèi)別 遞推 枚舉 遞歸 分治 貪婪 回溯(試探) 模擬 遞推 遞推分類(lèi) 順推法:從已知條件出發(fā),逐步推算出要解決問(wèn)題的方法。 逆推法:從已知結(jié)果出發(fā),用迭代表達(dá)式...

    sshe 評(píng)論0 收藏0
  • 《AI之矛》(1)【數(shù)獨(dú)Agent】

    摘要:而此處針對(duì)進(jìn)一步的搜索,有兩個(gè)問(wèn)題需要考慮如何選取搜索起點(diǎn)方格確定哪種搜索策略深度優(yōu)先搜索,廣度優(yōu)先搜索關(guān)于第一個(gè)問(wèn)題,無(wú)論選擇哪個(gè)方格起始搜索,對(duì)于能否解決問(wèn)題來(lái)說(shuō)并不存在差異。 Github倉(cāng)庫(kù)地址 學(xué)習(xí)是為了尋找解決問(wèn)題的答案,若脫離了問(wèn)題只為知曉而進(jìn)行的打call,那么隨時(shí)間流逝所沉淀下來(lái)的,估計(jì)就只有重在參與的虛幻存在感了,自學(xué)的人就更應(yīng)善于發(fā)現(xiàn)可供解決的問(wèn)題。為了入門(mén)AI,...

    CatalpaFlat 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<