这个是很早很早之前写的了。看人工智能的书的时候看到了启发式图搜索算法，完全不难理解，书上使用它来实现排序拼图的路径搜索，看完挺想自己实现一个，但是又觉得没啥难度，然后就想啊，能不能写个通用的抽象基类，要用这个方法解决什么问题时，就继承这个Class，然后写把与问题相关的几个函数写一下，就可以直接用了，这样的话以后想用暴力搜索解决一些临时问题，就可以随便写一写就可以了。

算法原理大概是：

先建立两个列表，一个是有序列表OPEN，另一个叫CLOSED

然后在列表OPEN中插入初始节点，CLOSED清空

每次循环时都将OPEN列表中评估函数最优的节点，将其放入CLOSED。如果该节点符合搜索完成条件，程序结束。

放入CLOSED表示该节点检测完毕

将该节点的所有不在CLOSED中的子节点全部放入OPEN中

重复上述过程。

额。。。讲的简单了点，不懂就google一下。。

以下就是Node.h和Node.cpp文件。

使用时继承Node，实现里面的虚函数就可以了。

#ifndef ___XXX___SEARCH_NODE___XXX__
#define ___XXX___SEARCH_NODE___XXX__

#include <list>
#include <iostream>
#include <stdlib .h>
#include <time .h>
using namespace std;

/************************************************************************/
//Myoil* root = new Myoil(0,0);
//root->SetFGH(1);
//root->Search();
/************************************************************************/
class node{
public:
    node* GetParent();
    int GetF();
    int GetG();
    int GetH();
    list<node *> child_node;
    node* IsInG(node*,int);
    list</node><node *> GetAnswerOrder(node*);

    void SetParent( node*);
    void SetFGH(int);
    virtual int IsGoal() = 0;
    /*
    CreateChildNode:内部要包括
        对每一种设置状态
        压入child_node
        SetParent
        SetFGH
    */
    virtual void CreateChildNode() = 0;
    virtual int CaculH() = 0;
    virtual void Display() = 0;
    virtual int NodeIsEqual(node*) = 0;
    virtual void ShowAnswei(list</node><node *>) = 0;

    void Search();
    node* GetMinfNodeFromOPEN();
    void ExtendNode(node*);
protected:
    node* parent_node;
    int f;//评估函数
    int g;//代价函数
    int h;//启发式函数

    void SetF();
    void SetG(const int);
    void SetH(const int);

};

static list</node><node *> G_OPEN;
static list</node><node *> G_CLOSED;

#endif

#include "Node.h"

#define ITERATOR list</node><node *>::iterator
#define MAX_INT 2147483647

node* node::GetParent()
{
    return parent_node;
}

void node::SetParent( node* parent)
{
    parent_node = parent;
}

int node::GetF()
{
    return f;
}

int node::GetG()
{
    return g;
}

int node::GetH()
{
    return h;
}

void node::SetF()
{
    f = g + h;
}

void node::SetG( const int gg)
{
    g = gg;
}

void node::SetH( const int hh)
{
    h = hh;
}

void node::SetFGH(int gg)
{
    SetG(gg);
    SetH(CaculH());
    SetF();
}

void node::Search()
{
    G_OPEN.push_front(this);

    while (G_OPEN.size())
    {
        node* min_node = GetMinfNodeFromOPEN();
        if (min_node->IsGoal())
        {
            cout< <"共用节点数:\nOPEN:"<<G_OPEN.size()<<" CLOSED:"<<G_CLOSED.size()<<endl;
            cout<<"所花时间:"<<double(clock())/1000<<"s\n";
            ShowAnswei(GetAnswerOrder(min_node));
            return;
        }
        else
        {
            ExtendNode(min_node);
        }
    }
}

//从OPEN中取出节点，并把其放入CLOSED
node* node::GetMinfNodeFromOPEN()
{
    node* min_node = NULL;
    ITERATOR min_iterator;
    int min_f = MAX_INT;
    for (ITERATOR i = G_OPEN.begin();i != G_OPEN.end();i++)
    {
        if((*i)->GetF() < min_f)
        {
            min_node = *i;
            min_iterator = i;
            min_f = (*i)->GetF();
        }
    }
    G_CLOSED.push_front(min_node);
    G_OPEN.erase(min_iterator);
    return min_node;
}

void node::ExtendNode( node* min_node)
{
    min_node->CreateChildNode();
    for each (node* i in min_node->child_node)
    {
        node* temp = NULL;
        if ((temp = IsInG(i,1)) != NULL)
        {
            if (i->GetG() < temp->GetG())
            {
                temp->SetG(i->GetG());
                temp->SetF();
                temp->SetParent(min_node);
            }
        }
        else if ((temp = IsInG(i,0)) != NULL)
        {
            if (i->GetG() < temp->GetG())
            {
                temp->SetG(i->GetG());
                temp->SetF();
                temp->SetParent(min_node);
            }
        }
        else
        {
            G_OPEN.insert(G_OPEN.begin(),i);
        }
    }
}

//为1时判断是否在OPEN中，为0时判断是否在CLOSED中
node* node::IsInG(node* m_node,int IsOpen)
{
    list</node><node *>* G = NULL;
    if(IsOpen)
    {
        G = &G_OPEN;
    }
    else
    {
        G = &G_CLOSED;
    }
    for each (node* i in *G)
    {
        if (i->NodeIsEqual(m_node))
        {

            return i;
        }
    }
    return NULL;
}

list</node><node *> node::GetAnswerOrder( node* final_node)
{
    list</node><node *> answer;
    node* temp= final_node;
    for(int i = 0;i < final_node->GetG();i++)
    {
        answer.insert(answer.begin(),temp);
        temp = temp->GetParent();
    }
    return answer;
}

下面给上一个简单的调用方法，来解决排序拼图问题。

#ifndef ___XXX___SEARCH_PINGTU___XXX__
#define ___XXX___SEARCH_PINGTU___XXX__

#include "Node.h"

class Pintu_Node: public node
{
public:

    Pintu_Node(int n);
    void CreateChildNode();
    double CaculH();
    int IsGoal();
    int NodeIsEqual(node*);
    void ShowAnswei(list</node><node *>);

    void Display();
    void RandomInit();
    /************************************************************************/
    /*0代表空白                                                             */
    /************************************************************************/

    int** state;
    //list<pintu_node *> child_node;
    int m_size;
protected:
    void SetChildNode(int,int);
    void CopyState(int** &dst);
};
#endif

#include "pintunode.h"
#include <iostream>
#include <stdio .h>
#include <stdlib .h>
#include <time .h>
#include <math .h>
using namespace std;

#define  HASH_LENGTH_MAX 876543210/2

Pintu_Node::Pintu_Node( int n )
{
    m_size = n;
    state = new int*[n];
    for(int i = 0;i < n;i++)
    {
        state[i] = new int[n];
    }
}

void Pintu_Node::CopyState( int** &dst )
{
    for(int i = 0;i < m_size;i++)
    {
        for(int j = 0;j < m_size;j++)
        {
            dst[i][j] = state[i][j];
        }
    }
}

void Pintu_Node::SetChildNode( int i,int j)
{
    if(i != 0)
    {
        Pintu_Node* childnode = new Pintu_Node(m_size);
        this->CopyState(childnode->state);
        childnode->state[i][j] = childnode->state[i-1][j];
        childnode->state[i-1][j] = 0;
        child_node.push_back(childnode);
    }

    if(j != 0)
    {
        Pintu_Node* childnode = new Pintu_Node(m_size);
        this->CopyState(childnode->state);
        childnode->state[i][j] = childnode->state[i][j-1];
        childnode->state[i][j-1] = 0;
        child_node.insert(child_node.begin(),childnode);
    }

    if(i != m_size-1)
    {
        Pintu_Node* childnode = new Pintu_Node(m_size);
        this->CopyState(childnode->state);
        childnode->state[i][j] = childnode->state[i+1][j];
        childnode->state[i+1][j] = 0;
        child_node.insert(child_node.begin(),childnode);
    }

    if(j != m_size-1)
    {
        Pintu_Node* childnode = new Pintu_Node(m_size);
        this->CopyState(childnode->state);
        childnode->state[i][j] = childnode->state[i][j+1];
        childnode->state[i][j+1] = 0;
        child_node.insert(child_node.begin(),childnode);
    }

    for each (node* i in child_node)
    {
        i->SetParent(this);
        i->SetFGH(this->GetG() + 1);
    }
}

void Pintu_Node::CreateChildNode()
{
    for(int i = 0;i < m_size;i++)
    {
        for(int j = 0;j < m_size;j++)
        {
            if(0 == state[i][j])
            {
                SetChildNode(i,j);
            }
        }
    }
}

double Pintu_Node::CaculH()
{
    /*int temp = 0;
    int h_counter = 0;
    for(int i = 0;i < m_size;i++)
    {
        for(int j = 0;j < m_size;j++)
        {
            temp++;
            if(state[i][j] != temp)
                h_counter++;
        }
    }

    if(state[m_size-1][m_size-1] == 0)
        h_counter--;
    return h_counter;*/

    int h_counter = 0;
    int temp = 0;
    for(int i = 0;i < m_size;i++)
    {
        for(int j = 0;j < m_size;j++)
        {
            temp = state[i][j];
            if(temp == 0)
                temp = 9;
            h_counter += abs((temp-1)/m_size - i) + abs((temp-1)%m_size - j);
        }
    }
    return h_counter;
}

void Pintu_Node::RandomInit()
{
    int* flag = new int[m_size * m_size];
    for(int i = 0;i < m_size * m_size;i++)
    {
        flag[i] = 0;
    }
    srand(time(0));
    for(int i = 0;i < m_size;i++)
    {
        for(int j = 0;j < m_size;j++)
        {
            int rand_num = rand()%(m_size * m_size);
            while (flag[rand_num] == 1)
            {
                rand_num = rand()%(m_size * m_size);
            }
            state[i][j] = rand_num;
            flag[rand_num] = 1;
        }
    }
    SetFGH(1);
}

void Pintu_Node::Display()
{
    cout<<"g:"<<this->GetG()< <"\t "<<
        "h:"<<this->GetH()< <"\t "<<
        "f:"<<this->GetF()< <"\n";

    for(int i = 0;i < m_size;i++)
    {
        for(int j = 0;j < m_size;j++)
        {
            cout<<state[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

int Pintu_Node::IsGoal()
{
    return GetH()==0;

}

int Pintu_Node::NodeIsEqual(node* n)
{
    //if(((Pintu_Node*)n)->GetH() != GetH())
    //    return 0;
    if (((Pintu_Node*)n)->m_size != m_size)
    {
        cout< <"error"<<__LINE__<<endl;
        return 0;
    }

    for(int i = 0;i < m_size;i++)
    {
        for(int j = 0;j < m_size;j++)
        {
            if (((Pintu_Node*)n)->state[i][j] != state[i][j])
            {
            //    printf("%d != %d\t",((Pintu_Node*)n)->state[i][j],state[i][j]);
                return 0;
            }
        }
    }
    return 1;

}

void Pintu_Node::ShowAnswei(list<node *> answer)
{
    for each (node* i in answer)
        i->Display();
}

#include <iostream>
#include <stdlib .h>
#include "pintunode.h"
using namespace std;

#define PINTU_SIZE 3

int main(int argc,char* argv[])
{
    Pintu_Node* root = new Pintu_Node(PINTU_SIZE);    

    root->RandomInit();
    root->Search();
    system("pause");
    return 0;
}

【完】

本文内容遵从CC版权协议，转载请注明出自http://www.kylen314.com