#include <stdlib.h>
#include <stdio.h>
#include <math.h>
typedef struct Node
{//节点结构体
    int data[9];
    double f,g;
    struct Node * parent;
}Node,*Lnode;
typedef struct Stack
{//OPEN CLOSED 表结构体
    Node * npoint;
    struct Stack * next;
}Stack,* Lstack;
Node * Minf(Lstack * Open)
{//选取OPEN表上f值最小的节点，返回该节点地址
    Lstack temp = (*Open)->next,min = (*Open)->next,minp = (*Open);
    Node * minx;
    while(temp->next != NULL)
    {
        if((temp->next ->npoint->f) < (min->npoint->f))
        {
            min = temp->next;
            minp = temp;
        }
        temp = temp->next;
    }
    minx = min->npoint;
    temp = minp->next;
    minp->next = minp->next->next;
    free(temp);
    return minx;
}
int Canslove(Node * suc, Node * goal)
{//判断是否可解
    int a = 0,b = 0,i,j;
    for(i = 1; i< 9;i++)
        for(j = 0;j < i;j++)
        {
            if((suc->data[i] > suc->data[j]) && suc->data[j] != 0)a++;
            if((goal->data[i] > goal->data[j]) && goal->data[j] != 0)b++;
        }
    if(a%2 == b%2)return 1;
    else return 0;
}
int Equal(Node * suc,Node * goal)
{//判断节点是否相等，相等，不相等
    for(int i = 0; i < 9; i ++ )
        if(suc->data[i] != goal->data[i])return 0;
    return 1;
}
Node * Belong(Node * suc,Lstack * list)
{//判断节点是否属于OPEN表或CLOSED表，是则返回节点地址，否则返回空地址
    Lstack temp = (*list) -> next ;
    if(temp == NULL)return NULL;
    while(temp != NULL)
    {
        if(Equal(suc,temp->npoint))return temp -> npoint;
        temp = temp->next;
    }
    return NULL;
}
void Putinto(Node * suc,Lstack * list)
{//把节点放入OPEN 或CLOSED 表中
    Stack * temp;
    temp =(Stack *) malloc(sizeof(Stack));
    temp->npoint = suc;
    temp->next = (*list)->next;
    (*list)->next = temp;
}
///////////////计算f值部分-开始//////////////////////////////
double Fvalue(Node suc, Node goal, float speed)
{//计算f值
    double Distance(Node,Node,int);
    double h = 0;
    for(int i = 1; i <= 8; i++)
        h = h + Distance(suc, goal, i);
    return h*speed + suc.g; //f = h + g;(speed值增加时搜索过程以到目标为优先因此可能不会返回最优解)                                     
}
double Distance(Node suc, Node goal, int i)
{//计算方格的错位距离
    int k,h1,h2;
    for(k = 0; k < 9; k++)
    {
        if(suc.data[k] == i)h1 = k;结构体sizeof
        if(goal.data[k] == i)h2 = k;
    }
    return double(fabs(h1/3 - h2/3) + fabs(h1%3 - h2%3));
}
///////////////计算f值部分-结束//////////////////////////////
///////////////////////扩展后继节点部分的函数-开始/////////////////
int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,float speed)
{//判断子节点是否属于OPEN或CLOSED表并作出相应的处理
    Node * temp = NULL;
    int flag = 0;
    if((Belong(*suc,Open) != NULL) || (Belong(*suc,Closed) != NULL))
    {
        if(Belong(*suc,Open) != NULL) temp = Belong(*suc,Open);
        else temp = Belong(*suc,Closed);
        if(((*suc)->g) < (temp->g))
        {
            temp->parent = (*suc)->parent;
            temp->g = (*suc)->g;
            temp->f = (*suc)->f;
            flag = 1;
        }
    }
    else
    {
        Putinto(* suc, Open);
        (*suc)->f = Fvalue(**suc, goal, speed);
    }
    return flag;
}
int Canspread(Node suc, int n)
{//判断空格可否向该方向移动，，，表示空格向上向下向左向右移
    int i,flag = 0;
    for(i = 0;i < 9;i++)
        if(suc.data[i] == 0)break;
    switch(n)
    {
    case 1:
        if(i/3 != 0)flag = 1;break;
    case 2:
        if(i/3 != 2)flag = 1;break;
    case 3:
        if(i%3 != 0)flag = 1;break;
    case 4:
        if(i%3 != 2)flag = 1;break;
    default:break;
    }
    return flag ;
}
void Spreadchild(Node * child,int n)
{//扩展child节点的字节点n表示方向，，，表示空格向上向下向左向右移
    int i,loc,temp;
    for(i = 0;i < 9;i++)
        child->data[i] = child->parent->data[i];
    for(i = 0;i < 9;i++)
        if(child->data[i] == 0)break;
    if(n==0)
        loc = i%3+(i/3 - 1)*3;
    else if(n==1)
        loc = i%3+(i/3 + 1)*3;
    else if(n==2)
        loc = i%3-1+(i/3)*3;
    else
        loc = i%3+1+(i/3)*3;
    temp = child->data[loc];
    child->data[i] = temp;
    child->data[loc] = 0;
}
void Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, float speed)
{//扩展后继节点总函数
    int i;
    Node * child;
    for(i = 0; i < 4; i++)
    {
        if(Canspread(**suc, i+1))                              //判断某个方向上的子节点可否扩展
        {
                child = (Node *) malloc(sizeof(Node));          //扩展子节点
                child->g = (*suc)->g +1;                        //算子节点的g值
                child->parent = (*suc);                        //子节点父指针指向父节点
                Spreadchild(child, i);                          //向该方向移动空格生成子节点
                  if(BelongProgram(&child, Open, Closed, goal, speed)) //    判断子节点是否属于OPEN或CLOSED表并作出相应的处理
                    free(child);
        }
    }
}
///////////////////////扩展后继节点部分的函数-结束//////////////////////////////////
Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, float speed)
{//总执行函数
    while(1)
    {
        if((*Open)->next == NULL)return NULL;                    //判断OPEN表是否为空，为空则失败退出
        Node * minf = Minf(Open);                                //从OPEN表中取出f值最小的节点

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。