八数码问题源代码（人工智能八数码问题代码）

本篇文章给大家谈谈八数码问题源代码，以及人工智能八数码问题代码对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、八数码问题（即九宫问题）的C++代码。跪求高手解答。
• 2、八数码问题 C语言 广度优先 其他也OK
• 3、求课设代码

八数码问题（即九宫问题）的C++代码。跪求高手解答。

#includeiostream

#includecstdio

#includecstring

using namespace std;

const int N=370000,HN=1000003;

int data[N][10],f[N],step[N],z[N];//data用于BFS队列存储，f记录节点的父亲，step记录节点的步数

int mv[10][5]={0,0,0,0,0,

2,2,4,0,0,

3,3,1,5,0,

2,2,6,0,0,

3,1,5,7,0,

4,2,4,6,8,

3,3,5,9,0,

2,4,8,0,0,

3,5,7,9,0,

2,6,8,0,0,};

int en[10],head[HN],next[N];//en记录目标状态，head记录hash表头，next记录hash后继指针

void shuchu(int k) //输出路径

{

if(f[k]!=0) shuchu(f[k]);

for(int i=1;i=9;i++)

{

coutdata[k][i]" ";

if(i==3||i==6) coutendl;

}

coutendlendl;

}

int hash(int a)

{

int x=0;

for(int i=1;i=9;i++)

x=x*10+data[a][i]; //将新节点的状态映射成9位整数

return x%HN; //确保hash值不超过hash表的大小；

}

bool can(int a)

{

int h=hash(a);//取回当前节点的hash值

int u=head[h];//取回当前节点hash值的链表的表头

while(u)

{

if(memcmp(data[u],data[a],sizeof(data[0]))==0)

return 0; //状态重复，返回假

u=next[u]; //利用链表找到下一个余数相同的节点

}

next[a]=head[h]; //新节点的next指针指向原来的hash值的表头

head[h]=a; //新节点成为新的hash值的表头

return 1; //合法的新节点

}

void bfs()

{

int h=0,t=1;

while(ht)

{

h++; //扩展队首

for(int i=1;i=mv[z[h]][0];i++) //z[h]队头（当前扩展节点）空格所在位置

{

memcpy(data[t+1],data[h],sizeof(data[h]));//把父节点的内容复制到扩展节点中

data[t+1][z[h]]=data[h][mv[z[h]][i]]; //原来（父节点）空格位置填值（交换）

data[t+1][mv[z[h]][i]]=0; //新的（子节点）空格置空

z[t+1]=mv[z[h]][i]; //记录新的空格位置

if(can(t+1))

{

t++; //增加新节点

f[t]=h;

step[t]=step[h]+1;

if(memcmp(data[t],en,sizeof(en))==0)

{

coutstep[t]endl;

shuchu(t);

fclose(stdin);

fclose(stdout);

exit(0);

}

}

}

}

}

int main()

{

freopen("eight.in","r",stdin);

freopen("eight.out","w",stdout);

for(int i=1;i=9;i++) //将出发状态直接装入队列

{

cindata[1][i];

if(data[1][i]==0) z[1]=i;

}

f[1]=0;

step[1]=0;

for(int i=1;i=9;i++) //存储目标状态

cinen[i];

if(memcmp(data[1],en,sizeof(en))==0) //memcmp是比较内存区域buf1和buf2的前count个字节。该函数是按字节比较的

{ //特殊情况，出发状态跟目标状态一样

cout0endl;

shuchu(1);

fclose(stdin);

fclose(stdout);

return 0;

}

bfs();

return 0;

}

八数码问题 C语言 广度优先 其他也OK

nclude "stdio.h"

typedef int datatype; /*假定线性表元素的类型为整型*/

#define maxsize 1024 /*假定线性表的最大长度为1024*/

# define n 100 /* 图的顶点最大个数 */

typedef char VEXTYPE; /* 顶点的数据类型 */

typedef float ADJTYPE; /* 权值类型 */

typedef struct

{ VEXTYPE vexs[n] ; /* 顶点信息数组 */

ADJTYPE arcs[n][n] ; /* 边权数组 */

int num ; /* 顶点的实际个数 */

}GRAPH;

/***********************1。置空图**********************/

void GraphInit(GRAPH *L)

{

L-num=0;

}

/***********************2。求结点数**********************/

int GraphVexs(GRAPH *L)

{

return(L-num);

}

/***********************3。创建图**********************/

void GraphCreate(GRAPH *L)

{

int i,j;

GraphInit(L);

printf("请输入顶点数目：");

scanf("%d",L-num);

printf("请输入各顶点的信息(单个符号）：");

for(i=0;iL-num;i++)

{

fflush(stdin);

scanf("%c",L-vexs[i]);

}

printf("请输入边权矩阵的信息：");

for(i=0;iL-num;i++)

{

for(j=0;jL-num;j++)

{

scanf("%f",L-arcs[i][j]);

}

}

printf("图已经创建完毕！");

}

/***********************4。图的输出**********************/

void GraphOut(GRAPH L)

{

int i,j;

printf("\n图的顶点数目为：%d",L.num);

printf("\n图的各顶点的信息为：\n");

for(i=0;iL.num;i++)

printf("%c ",L.vexs[i]);

printf("\n图的边权矩阵的信息为：\n");

for(i=0;iL.num;i++)

{

for(j=0;jL.num;j++)

{

printf("%6.2f ",L.arcs[i][j]);

}

printf("\n");

}

printf("图已经输出完毕！");

}

/***********************5。图的深度周游**********************/

void DFS(GRAPH g,int qidian,int mark[])

//从第qidian个点出发深度优先周游图g中能访问的各个顶点

{

int v1;

mark[qidian]=1;

printf("%c ",g.vexs[qidian]);

for(v1=0;v1g.num;v1++)

{

if(g.arcs[qidian][v1]!=0mark[v1]==0)

DFS(g,v1,mark);

}

}

/***********************6。图的深度周游**********************/

void GraphDFS(GRAPH g)

//深度优先周游图g中能访问的各个顶点

{

int qidian,v,v1,mark[maxsize];

printf("\n深度周游：");

printf("\n请输入起点的下标：");

scanf("%d",qidian);

for(v=0;vg.num;v++)

{

mark[v]=0;

}

for(v=qidian;vg.num+qidian;v++)

{

//printf("v=%d ",v);

v1=v%g.num;

if(mark[v1]==0)

DFS(g,v1,mark);

}

}

typedef int DATATYPE; //队列元素的数据类型

typedef struct

{

DATATYPE data[maxsize]; //队中元素

int front,rear; //队头元素下标、队尾元素后面位置的下标

} SEQQUEUE;

/*****************************************************************************/

void QueueInit(SEQQUEUE *sq)

//将顺序循环队列sq置空（初始化）

{

sq-front=0;

sq-rear=0;

}

/*****************************************************************************/

int QueueIsEmpty(SEQQUEUE sq)

//如果顺序循环队列sq为空，成功返回1，否则返回0

{

if (sq.rear==sq.front)

return(1);

else

return(0);

}

/*****************************************************************************/

int QueueFront(SEQQUEUE sq,DATATYPE *e)

//将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0

{

if (QueueIsEmpty(sq))

else

}

/*****************************************************************************/

int QueueIn (SEQQUEUE *sq,DATATYPE x)

//将元素x入队列sq的队尾，成功返回1，失败返回0

{

if (sq-front==(sq-rear+1)%maxsize)

{

printf("queue is full!\n");

return 0;

}

else

{

sq-data[sq-rear]=x;

sq-rear=(sq-rear+1)%maxsize;

return(1);

}

}

/*****************************************************************************/

int QueueOut(SEQQUEUE *sq)

//将队列sq队首元素出队列，成功返回1,失败返回0

{

if (QueueIsEmpty(*sq))

{

printf("queue is empty!\n");

return 0;

}

else

{

sq-front=(sq-front+1)%maxsize;

return 1;

}

}

/***********************7。图的广度周游**********************/

void BFS(GRAPH g,int v,int mark[])

//从v出发广度优先周游图g中能访问的各个顶点

{

int v1,v2;

SEQQUEUE q;

QueueInit(q);

QueueIn(q,v);

mark[v]=1;

printf("%c ",g.vexs[v]);

while(QueueIsEmpty(q)==0)

{

QueueFront(q,v1);

QueueOut(q);

for(v2=0;v2g.num;v2++)

{

if(g.arcs[v1][v2]!=0mark[v2]==0)

{

QueueIn(q,v2);

mark[v2]=1;

printf("%c ",g.vexs[v2]);

}

}

}

}

/***********************8。图的广度周游**********************/

void GraphBFS(GRAPH g)

//深度优先周游图g中能访问的各个顶点

{

int qidian,v,v1,mark[maxsize];

printf("\n广度周游：");

printf("\n请输入起点的下标：");

scanf("%d",qidian);

for(v=0;vg.num;v++)

{

mark[v]=0;

}

for(v=qidian;vg.num+qidian;v++)

{

v1=v%g.num;

if(mark[v1]==0)

BFS(g,v1,mark);

}

}

/***********************主函数**********************/

void main()

{

GRAPH tu;

GraphCreate(tu);

GraphOut(tu);

GraphDFS(tu);

GraphBFS(tu);

}

另外,虚机团上产品团购,超级便宜

求课设代码

基于A算法求解八数码问题是一种规划问题，即用有限步骤把初始状态转换成目标状态的过程。A算法是一种带有启发式函数的搜索算法，用于通过估价函数指导搜索，提高搜索效率。

为了实现上述功能，需要定义若干个变量和函数，如下所示：

定义变量：

init_state：初始状态，即八数码问题的初始排列；

goal_state：目标状态，即八数码问题的最终排列；

f_score：估价函数值，即启发函数和实际代价之和；

g_score：实际代价，即当前状态到起始状态的实际步数；

h_score：启发函数值，即当前状态到目标状态的估计步数。

定义函数：

get_successor_states()：用于获取当前状态的所有后继状态；

get_heuristic_value()：用于计算当前状态到目标状态的估计步数，即启发函数值；

get_g_value()：用于计算当前状态到起始状态的实际步数；

get_f_value()：用于计算当前状态的估价函数值，即启发函数值与实际代价之和；

compare_f_values()：用于比较两个状态的估价函数值的大小；

A*_search()：用于执行A*搜索算法，求解八数码问题。

在定义了上述变量和函数后，我们就可以编写A*搜索算法的代码了。下面是一个可能的实现方式：

Copy code

# 定义估价函数

def get_heuristic_value(state):

h_value = 0

# 计算估价函数值

for i in range(len(state)):

for j in range(len(state[i])):

if state[i][j] != goal_state[i][j]:

h_value += 1

return h_value

# 定义实际代价函数

def get_g_value(state):

g_value = 0

# 计算实际代价值

for i in range(len(state)):

for j in range(len(state[i])):

if state[i][j] != init_state[i][j]:

g_value += 1

return g_value

# 定义估价函数值函数

def get_f_value(state):

# 计算估价函数值

f_value = get_g_value(state) + get_heuristic_value(state)

return f_value

# 定义估价函数值比较函数

def compare_f_values(state1, state2):

# 比较两个状态的估价函数值

f1 = get_f_value(state1)

f2 = get_f_value(state2)

if f1 f2:

return -1

elif f1 f2:

return 1

else:

return 0

# 定义A*搜索算法

def A*_search():

# 初始化OPEN表和CLOSED表

open_list = []

closed_list = []

# 将初始状态加入OPEN表

并更新估价函数值 open_list.append(init_state) f_values[init_state] = get_f_value(init_state)

# 循环执行直到OPEN表为空

while len(open_list) 0:

# 从OPEN表中选择估价函数值最小的状态

current_state = min(open_list, key=get_f_value)

# 如果当前状态是目标状态，则算法执行成功

if current_state == goal_state:

return True

# 将当前状态从OPEN表中移除，并加入CLOSED表

open_list.remove(current_state)

closed_list.append(current_state)

# 获取当前状态的所有后继状态

successor_states = get_successor_states(current_state)

# 遍历所有后继状态

for successor_state in successor_states:

# 如果后继状态已在CLOSED表中，则跳过

if successor_state in closed_list:

continue

# 如果后继状态不在OPEN表中，则加入OPEN表并更新估价函数值

if successor_state not in open_list:

open_list.append(successor_state)

f_values[successor_state] = get_f_value(successor_state)

# 如果新的路径更优，则更新估价函数值

elif get_f_value(successor_state) f_values[successor_state]:

f_values[successor_state] = get_f_value(successor_state)

# 如果OPEN表为空，则算法执行失败

return False

上面的代码实现了A*搜索算法的基本流程，包括初始化、主循环、状态扩展和结束条件判断。它使用了估价函数值来比较

不同状态的优劣，从而决定搜索的方向和顺序。

为了实现上述需求，我们还需要对代码进行一些改进和完善，如下所示：

定义3种不同的启发式函数：我们可以定义3种不同的启发式函数，分别用于计算曼哈顿距离、欧几里得距离和拼图曼哈顿距离。这些启发式函数的实现方式略有不同，但都基于当前状态与目标状态之间的位置关系进行计算。

提供可视化界面：我们可以创建一个可视化界面，用于展示搜索过程。该界面应能够显示搜索树、估价函数值、OPEN表和CLOSED表的动态变化情况。同时，用户应能够选择预定义的启发式函数，随机初始化初始状态，单步执行或连续执行搜索算法。

统计扩展节点数和执行时间：为了对采用不同启发式函数的A*算法进行性能对比研究，我们需要统计算法执行过程中的扩展节点数和执行时间。这些信息可以用来评估算法的效率和优劣。

通过上述

改进和完善，我们就可以实现一个能够求解八数码问题的A*算法，具有较好的可视化展示和性能分析能力。

八数码问题源代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于人工智能八数码问题代码、八数码问题源代码的信息别忘了在本站进行查找喔。