【BFS】八数码问题(c++基础算法)

简介: 【BFS】八数码问题(c++基础算法)

 目录

一.读题

二.在做题之前

1.康拓展开

2.DFS和BFS的区别

3.栈和队列的区别

三.做题

1.算法原理

2.算法实现

①队列

②康托展开

③标记

四.AC代码


一.读题

作为最经典的一道宽度优先搜索题,它的题面并不是很难懂。

【宽搜(难度:6)】8数码问题

题目描述

【题意】

 

在3×3的棋盘上摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围上下左右相邻的棋子可以移到空格中。

现给出原始状态和目标状态,求实现从初始布局到目标布局的最少步骤(初始状态的步数为0)。

如下图,答案为5。


 

image.gif 编辑

 

【输入格式】

   第一个3*3的矩阵是原始状态;

   第二个3*3的矩阵是目标状态。

【输出格式】

   输出移动所用最少的步数。

【样例1输入】

2 8 3

1 6 4

7 0 5

1 2 3

8 0 4

7 6 5

【样例1输出】

5

 

【样例2输入】

2 8 3

1 6 4

7 0 5

0 1 2

3 4 5

8 7 6

【样例2输出】

17

很显然,这是要我们求出矩阵1通过白色方块的上下左右移动转化向矩阵2的最小步数。


二.在做题之前

在做题之前,我们先要弄懂3个问题。

1.康拓展开

在这道题中,我们要利用康托展开判断是否重复。在文前,蒟蒻已经写了一篇文章,不懂的可以去看一下:【宽搜必备】康托展开(从公式解析到代码实现)

那么,我们就可以写出:

int kt(int a[],int n)
{
  int s=1;
  for(int i=1;i<=n;i++)
  {
    int index=1,f=1,count=0;
    for(int j=i+1;j<=n;j++)
    {
      f*=index;
      index++;
      if(a[i]>a[j]) count++; 
    }
    s=s+count*f;
  } 
  return s;
}

image.gif

2.DFS和BFS的区别

bfs 遍历节点是先进先出,dfs遍历节点是先进后出

bfs是按层次访问的,dfs 是按照一个路径一直访问到底,当前节点没有未访问的邻居节点时,然后回溯到上一个节点,不断的尝试,直到访问到目标节点或所有节点都已访问。

bfs 适用于求源点与目标节点距离最近的情况,例如:求最短路径。dfs 更适合于求解一个任意符合方案中的一个或者遍历所有情况,例如:全排列、拓扑排序、求到达某一点的任意一条路径。

3.栈和队列的区别

(1)栈和队列的出入方式不同:栈是后进先出、队列是先进先出

(2)栈和队列在具体实现的时候操作的位置不同:因为栈是后进先出,它在一段进行操作;而队列是先进先出,实现的时候在两端进行。

现在,我们搞懂了这三个问题,就可以做题了。


三.做题

1.算法原理

采用BFS遍历的方式寻找最优路径。

首先定义一个结构体ma来存放八数码的每一个状态信息,其中包括节点对应的矩阵,节点在BFS遍历树中的深度(相当于步数),以及节点对应的康托值。然后,定义visited数组存放已经访问过的节点状态。

利用队列实现遍历,具体步骤如下:

1.将初始状态的各种信息压入队列中。

2.判断队列是否为空,若为空,退出循环,打印移动步骤,结束。

3.取出队头元素判断是否与目标状态一致。若一致,则退出循环,输出移动步骤,程序结束。若不一致,则分别判断空格向左、向上、向下以及向右能否移动。                                                                 5.若可以移动,求其康托值,然后压进队列。并跳转到步骤四。

转载图,侵权必删image.gif编辑

2.算法实现

①队列

因为此队列要存的东西是一个结构体,因此也要把其类型定为结构体ma

②康托展开

在此代码中,康托展开用于判重。要将一个3*3的矩阵换为一个数。首先,我们要把此二维数组变为一维的。

int d[10],len = 0;
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++) 
        {
            d[++len] = ak.a[i][j];
        }
    }

image.gif

然后,进行康拓转化。最后就是这样

int kt(ma ak)
{
    int d[10],len = 0;
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++) 
        {
            d[++len] = ak.a[i][j];
        }
    }
    int s=1;
    for(int i=1;i<=9;i++)
    {
        int index=1,f=1,count=0;
        for(int j=i+1;j<=9;j++)
        {
            f=f*index,index++;
            if(d[i]>d[j]) count++;
        }
        s=s+count*f;
    }
    return s;
}

image.gif

③标记

很简单,用数组flag标记康托值即可


四.AC代码

#include<bits/stdc++.h>
using namespace std;
struct ma{
    int a[10][10],x0,y0,ans,kt; 
};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
queue<ma>q;
bool flag[400000];
int kt(ma ak)
{
    int d[10],len = 0;
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++) 
        {
            d[++len] = ak.a[i][j];
        }
    }
    int s=1;
    for(int i=1;i<=9;i++)
    {
        int index=1,f=1,count=0;
        for(int j=i+1;j<=9;j++)
        {
            f=f*index,index++;
            if(d[i]>d[j]) count++;
        }
        s=s+count*f;
    }
    return s;
}
int main()
{
    ma shi,mo;
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            scanf("%d",&shi.a[i][j]);
            if(shi.a[i][j]==0)
            {
                shi.x0=i,shi.y0=j;
            }
        }
    }
    shi.ans = 0;
    shi.kt = kt(shi);
    flag[shi.kt] = 1;
    q.push(shi);
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            scanf("%d",&mo.a[i][j]);
        }
    }
    mo.kt=kt(mo);
    while(!q.empty())//q非空,可以走
    {
        for(int i=0;i<4;i++)//四个方向
        {
            ma ac=q.front();
            int nx = ac.x0 + dx[i];
            int ny = ac.y0+ dy[i];
            if(nx>=1&&ny>=1&&nx<=3&&ny<=3)
            {
                swap(ac.a[ac.x0][ac.y0],ac.a[nx][ny]);
                ac.x0=nx;
                ac.y0=ny;
                //将0与目标数交换
                ac.ans++;//步数加1
                ac.kt=kt(ac);
                //康托判重
                 if (!flag[ac.kt])
                {
                    flag[ac.kt] = 1;
                    q.push(ac);
                    //加入队列
                    if(ac.kt==mo.kt)
                    { 
                        printf("%d",q.back().ans);
                        exit(0);
                    }
                }
            }
        }
        q.pop();
        //弹出已遍历完所有情况的矩阵
    }
}

image.gif


目录
打赏
0
0
0
0
3
分享
相关文章
|
12天前
|
算法系列之搜索算法-广度优先搜索BFS
广度优先搜索(BFS)是一种非常强大的算法,特别适用于解决最短路径、层次遍历和连通性问题。在面试中,掌握BFS的基本实现和应用场景,能够帮助你高效解决许多与图或树相关的问题。
29 1
算法系列之搜索算法-广度优先搜索BFS
|
15天前
|
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
37 15
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
42 12
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
13 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
65 19
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
55 2
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
3月前
|
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
67 4
超级好用的C++实用库之sha256算法
超级好用的C++实用库之sha256算法
218 1