📄 a_and_list.txt
字号:
temp=temp->son4;
son_fn(temp,dg);
}
return NULL;
}
//=======================================================================
// Description : 迷宫A*搜索算法程序
// Parameters :链表定义，结合状态空间的定义等，已于上面完成
// Supplement : 无
//use========================================================================
void a_search(int a[][11],state_define2 s_n,state_define2 s_g)
{
if(step==0) /* 若是第一次扩展则将起始节点放入open表*/
{
step++;
open_list = insert_node(open_list, s_n->s_row2,s_n->s_collum2,0);
open_list->next->f_n=abs(s_n->s_row2-s_g->s_row2)+ abs(s_n->s_collum2-s_g->s_collum2); /* 计算起始节点的fn */
a_search(a,s_n, s_g);
}
if(isempty(open_list)) /* 若open表空或者不可能的步数出现失败退出*/
{
printf("没有路径！:(\n");
return;
}
else
{
list_node best_node = find_fn(open_list);
if((best_node->row==s_g->s_row2)&&(best_node->collum==s_g->s_collum2))
{
printf("找到路径！:)\n"); /* 找到路径打印路径 */
while (!((best_node->row==s_n->s_row2)&&(best_node->collum==s_n->s_collum2)))
{
printf("%d %d %d\n ", best_node->row,best_node->collum,best_node->f_n);
best_node = best_node->father;
}
printf("%d %d %d\n ", best_node->row,best_node->collum,best_node->f_n);
return;
}
//扩展节点bestnode生成全部子节点subnode
//计算subnode的f（n），设置指向bestnode的指针
//子节点subnodes全部放入open表
if(a[best_node->row][best_node->collum+1]==0)
{
list_node sub_node1= create_node(best_node->row,best_node->collum+1,0);
list_node temp=sub_node1;
sub_node1->g_n=best_node->g_n+1;
sub_node1->h_n=abs(sub_node1->row-s_g->s_row2)+ abs(sub_node1->collum-s_g->s_collum2);
sub_node1->f_n=sub_node1->g_n+sub_node1->h_n;
if((NULL==(find_closed(open_list,sub_node1->row,sub_node1->collum)))&&(NULL==(find_closed(closed_list,sub_node1->row,sub_node1->collum))))
{ /* 若节点不在closed或open表中设置sub-node指向best-node的指针 */
sub_node1->father=best_node;
best_node->son1=sub_node1;
open_list = insert_node2(open_list, sub_node1); /* 放入open表 */
}
else /* 若节点在closed或open表中比较gn谁小留谁 */
{
if(!(NULL==(find_closed(open_list,sub_node1->row,sub_node1->collum))))
{
temp=find_closed(open_list,sub_node1->row,sub_node1->collum);
}
else
{
temp=find_closed(closed_list,sub_node1->row,sub_node1->collum);
}
if(sub_node1->g_n<temp->g_n) /* 若新的较小泽用新的替代旧的 */
{
temp->g_n=sub_node1->g_n<temp->g_n;
temp->father=best_node;
if(!(NULL==(temp=find_closed(closed_list,sub_node1->row,sub_node1->collum))))
{ /* 若在closed表中重新计算subnode的子孙节点的fn */
dg_n=temp->g_n-sub_node1->g_n;
son_fn(temp,dg_n); /* 重新计算subnode的子孙节点的fn */
} /*从subnode中删除son即不宽展他*/
}
else
{ /* 若原先的较小则放弃新的，即不扩展它 */
}
}
}
if(a[best_node->row+1][best_node->collum]==0)
{
list_node sub_node2= create_node(best_node->row+1,best_node->collum,0);
list_node temp=sub_node2;
sub_node2->g_n=best_node->g_n+1;
sub_node2->h_n=abs(sub_node2->row-s_g->s_row2)+ abs(sub_node2->collum-s_g->s_collum2);
sub_node2->f_n=sub_node2->g_n+sub_node2->h_n;
if((NULL==(temp=find_closed(open_list,sub_node2->row,sub_node2->collum)))&&(NULL==(temp=find_closed(closed_list,sub_node2->row,sub_node2->collum))))
{ /* 若节点不在closed或open表中设置sub-node指向best-node的指针 */
sub_node2->father=best_node;
best_node->son2=sub_node2;
open_list = insert_node2(open_list, sub_node2); /* 放入open表 */
}
else /* 若节点在closed或open表中比较gn谁小留谁 */
{
if(!(NULL==(find_closed(open_list,sub_node2->row,sub_node2->collum))))
{
temp=find_closed(open_list,sub_node2->row,sub_node2->collum);
}
else
{
temp=find_closed(closed_list,sub_node2->row,sub_node2->collum);
}
if(sub_node2->g_n<temp->g_n) /* 若新的较小泽用新的替代旧的 */
{
temp->g_n=sub_node2->g_n<temp->g_n;
temp->father=best_node;
if(!(NULL==(temp=find_closed(closed_list,sub_node2->row,sub_node2->collum))))
{ /* 若在closed表中重新计算subnode的子孙节点的fn */
dg_n=temp->g_n-sub_node2->g_n;
son_fn(temp,dg_n); /* 重新计算subnode的子孙节点的fn */
} /*从subnode中删除son即不宽展他*/
}
else
{ /* 若原先的较小则放弃新的，即不扩展它 */
}
}
}
if(a[best_node->row][best_node->collum-1]==0)
{
list_node sub_node3= create_node(best_node->row,best_node->collum-1,0);
list_node temp=sub_node3;
sub_node3->g_n=best_node->g_n+1;
sub_node3->h_n=abs(sub_node3->row-s_g->s_row2)+ abs(sub_node3->collum-s_g->s_collum2);
sub_node3->f_n=sub_node3->g_n+sub_node3->h_n;
if((NULL==(temp=find_closed(open_list,sub_node3->row,sub_node3->collum)))&&(NULL==(temp=find_closed(closed_list,sub_node3->row,sub_node3->collum))))
{
/* 若节点不在closed或open表中设置sub-node指向best-node的指针 */
sub_node3->father=best_node;
best_node->son3=sub_node3;
open_list = insert_node2(open_list, sub_node3); /* 放入open表 */
}
else /* 若节点在closed或open表中比较gn谁小留谁 */
{
if(!(NULL==(find_closed(open_list,sub_node3->row,sub_node3->collum))))
{
temp=find_closed(open_list,sub_node3->row,sub_node3->collum);
}
else
{
temp=find_closed(closed_list,sub_node3->row,sub_node3->collum);
}
if(sub_node3->g_n<temp->g_n) /* 若新的较小泽用新的替代旧的 */
{
temp->g_n=sub_node3->g_n<temp->g_n;
temp->father=best_node;
if(!(NULL==(temp=find_closed(closed_list,sub_node3->row,sub_node3->collum))))
{ /* 若在closed表中重新计算subnode的子孙节点的fn */
dg_n=temp->g_n-sub_node3->g_n;
son_fn(temp,dg_n); /* 重新计算subnode的子孙节点的fn */
} /*从subnode中删除son即不宽展他*/
}
else
{ /* 若原先的较小则放弃新的，即不扩展它 */
}
}
}
if(a[best_node->row-1][best_node->collum]==0)
{
list_node sub_node4= create_node(best_node->row-1,best_node->collum,0);
list_node temp=sub_node4;
sub_node4->g_n=best_node->g_n+1;
sub_node4->h_n=abs(sub_node4->row-s_g->s_row2)+ abs(sub_node4->collum-s_g->s_collum2);
sub_node4->f_n=sub_node4->g_n+sub_node4->h_n;
if((NULL==(temp=find_closed(open_list,sub_node4->row,sub_node4->collum)))&&(NULL==(temp=find_closed(closed_list,sub_node4->row,sub_node4->collum))))
{ /* 若节点不在closed或open表中设置sub-node指向best-node的指针 */
sub_node4->father=best_node;
best_node->son4=sub_node4;
open_list = insert_node2(open_list, sub_node4); /* 放入open表 */
}
else /* 若节点在closed或open表中比较gn谁小留谁 */
{
if(!(NULL==(find_closed(open_list,sub_node4->row,sub_node4->collum))))
{
temp=find_closed(open_list,sub_node4->row,sub_node4->collum);
}
else
{
temp=find_closed(closed_list,sub_node4->row,sub_node4->collum);
}
if(sub_node4->g_n<temp->g_n) /* 若新的较小泽用新的替代旧的 */
{
temp->g_n=sub_node4->g_n<temp->g_n;
temp->father=best_node;
if(!(NULL==(temp=find_closed(closed_list,sub_node4->row,sub_node4->collum))))
{ /* 若在closed表中重新计算subnode的子孙节点的fn */
dg_n=temp->g_n-sub_node4->g_n;
son_fn(temp,dg_n); /* 重新计算subnode的子孙节点的fn */
} /*从subnode中删除son即不宽展他*/
}
else
{ /* 若原先的较小则放弃新的，即不扩展它 */
}
}
}
// open_list=link_list(open_list,sub_nodes);
// sub_node3->father=best_node;
//从open表中删除bestnode，放入closed表
del_node2(open_list,best_node);
closed_list=insert_node2(closed_list,best_node);
step++;
//递归算法，回到第二步判断open表是否为空
a_search(a,s_n,s_g);
return;
}
}
open_list = create_list(-1,-1,0); /* 创建open表 */
closed_list = create_list(-1,-1,0); /* 创建closed表 */
sub_nodes = create_list(-1,-1,0); /* 创建closed表 */
printf("生成的迷宫：\n");⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -