BFS解决八数码问题-java

2024-04-20 09:04
文章标签 java 问题 bfs 解决 数码

本文主要是介绍BFS解决八数码问题-java,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文主要通过BFS广度优先搜索来解决八数码问题。

文章目录

前言

一、八数码

二、算法思路

1.思路模拟

2.实现思路

三、代码

1.代码如下:

2.读入数据

3.代码运行结果

总结


前言

本文主要通过BFS广度优先搜索来解决八数码问题。


提示:以下是本篇文章正文内容,下面案例可供参考

一、八数码

在一个 3×3的网格中,1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。

例如:

1 2 3
x 4 6
7 5 8

我们可以通过x与它的上下左右四个方向之一的数字进行交换作来让最后的网格变成如下正确排列:

1 2 3
4 5 6
7 8 x

 上述过程的具体交换如下:

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

现在,给你一个初始网格,请你求出得到正确排列至少需要进行多少次交换。

输入格式:

输入占一行,将 3×3的初始网格描绘出来。

 上述输入例如:1 2 3 x 4 6 7 5 8

输出格式:

输出占一行,包含一个整数,表示最少交换次数。

如果不存在解决方案,则输出 −1。

二、算法思路

1.思路模拟

图1.1思路模拟 

如图1.1所示,x有四种交换方式,那我们可以把最后的结果抽象为x在当前位置,走各种情况且最短距离到达最右下角的时候,所得到的最后的序列与正确序列是否相同,相同了输出此时的交换次数即最小交换次数,如果不同,直接打印-1,说明得不到正确的序列。

 x的移动方式我们可以用两个一维数组分别x和y的变化量即dx,dy 

dx = (-1,1,0,0)

 dy = (0,0,-1,1)

 四个变化量分别表示上、下、左、右横纵坐标的变化量。

因为这道题是直接输入了一行,我们可以用字符串start来存储整个序列。

图1.2下标转换 

如图1.2所示矩阵中横坐标x:下标 / 3;矩阵中纵坐标y:下标 % 3

因此当我们用BFS进行时,每一个点的状态我们可以直接用字符串类型的队列queue<String>来存储即可,并且每一个从初始起点到该状态的步数即交换次数用一个键为String、值为Integer的集合dist来存储。   

2.实现思路

我们先向队列中添加起始状态strat,然后向dist中添加起始状态的交换次数0,然后进行循环,当队列非空时,弹出队头元素即此时的状态字符串pool,如果此时poll跟最后状态“12345678x”字符串end相同时说明我们此时已经完成了正确序列的交换并且我们上下左右操作每一次都是在原状态的操作次数加1,此时dist.get(end)就是我们的最小交换次数。当poll跟end不匹配时,那么我们通过图1.2来得到在3*3棋盘中的横纵坐标x、y,然后通过for循环来得到上下左右四个状态对应变化后的横纵坐标a、b。当然我们得判断a、b是否在棋盘中越界,并且我们得上下左右移动完成交换后的新字符串是否在dist集合中出现过,dist.get(str)不为空就说明我们已经走过这个状态,就不必再走了;为空就说明这个状态我们未交换过,那么我们就将新状态压入队列,然后得到原先字符串状态的交换次数即dist.get(poll),然后再把新状态和对应的交换次数(原状态交换次数+1)即dist.map(str,dist.get(pool)+1)放入集合dist。当我们队列为空且最后一个状态仍与结尾状态不一样说明无法得到最后的正确序列,返回-1即可。

三、代码

1.代码如下:


import java.io.*;
import java.util.*;
public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));//初始字符串static String start;public static void main(String[] args) {Scanner sc = new Scanner(br);//把输入的一行中的空格全部替换没了start = sc.nextLine().replaceAll("\\s+","");pw.println(bfs());pw.flush();}public static int bfs(){String end = "12345678x";Queue<String> queue = new LinkedList<>();Map<String,Integer>dist = new HashMap<>();queue.add(start);dist.put(start,0);//上下左右int[] dx = {-1,1,0,0};int[] dy = {0,0,-1,1};while (!queue.isEmpty()){//取出队头元素String pool = queue.poll();if(pool.equals(end)){return dist.get(end);}//找到x的下标int k = pool.indexOf('x');int x = k / 3;int y = k % 3;//表示上下左右四个状态for(int i = 0;i < 4;i++){//变化后的x坐标int a = x + dx[i];//变化后的y的坐标int b = y + dy[i];//判断下标是否在矩阵中越界if(a >= 0 && a < 3 && b >= 0 && b < 3){char[] arr = pool.toCharArray();//将x和此时变化后的字符进行交换swap(arr,k,a * 3 + b);//将字符数组转换成字符串String str = new String(arr);//说明此时的状态是未走过的if(dist.get(str) == null){//将新状态添加进队列queue.add(str);//走到新状态那就原本的状态对应的字符串交换次数+1dist.put(str, dist.get(pool) + 1);}}}}//当我们走完之后字符串与目标序列不同说明根本交换不到正确序列,返回结果-1return -1;}//地址传递 交换字符public static void swap(char[] arr,int a,int b){char temp = arr[a];arr[a] = arr[b];arr[b] = temp;}
}

2.读入数据

2  3  4  1  5  x  7  6  8 

3.代码运行结果

19

总结

上述也是通过BFS来解决最短路的问题,我们只要分清楚各个状态如何变化和存储,知道一个点是从哪个点抽象变化过来的,就可以解决这一类问题。

这篇关于BFS解决八数码问题-java的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/919833

相关文章

MybatisGenerator文件生成不出对应文件的问题

《MybatisGenerator文件生成不出对应文件的问题》本文介绍了使用MybatisGenerator生成文件时遇到的问题及解决方法,主要步骤包括检查目标表是否存在、是否能连接到数据库、配置生成... 目录MyBATisGenerator 文件生成不出对应文件先在项目结构里引入“targetProje

C#使用HttpClient进行Post请求出现超时问题的解决及优化

《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也... 目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧,

SpringBoot使用Apache Tika检测敏感信息

《SpringBoot使用ApacheTika检测敏感信息》ApacheTika是一个功能强大的内容分析工具,它能够从多种文件格式中提取文本、元数据以及其他结构化信息,下面我们来看看如何使用Ap... 目录Tika 主要特性1. 多格式支持2. 自动文件类型检测3. 文本和元数据提取4. 支持 OCR(光学

Java内存泄漏问题的排查、优化与最佳实践

《Java内存泄漏问题的排查、优化与最佳实践》在Java开发中,内存泄漏是一个常见且令人头疼的问题,内存泄漏指的是程序在运行过程中,已经不再使用的对象没有被及时释放,从而导致内存占用不断增加,最终... 目录引言1. 什么是内存泄漏?常见的内存泄漏情况2. 如何排查 Java 中的内存泄漏?2.1 使用 J

JAVA系统中Spring Boot应用程序的配置文件application.yml使用详解

《JAVA系统中SpringBoot应用程序的配置文件application.yml使用详解》:本文主要介绍JAVA系统中SpringBoot应用程序的配置文件application.yml的... 目录文件路径文件内容解释1. Server 配置2. Spring 配置3. Logging 配置4. Ma

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

java脚本使用不同版本jdk的说明介绍

《java脚本使用不同版本jdk的说明介绍》本文介绍了在Java中执行JavaScript脚本的几种方式,包括使用ScriptEngine、Nashorn和GraalVM,ScriptEngine适用... 目录Java脚本使用不同版本jdk的说明1.使用ScriptEngine执行javascript2.

Spring MVC如何设置响应

《SpringMVC如何设置响应》本文介绍了如何在Spring框架中设置响应,并通过不同的注解返回静态页面、HTML片段和JSON数据,此外,还讲解了如何设置响应的状态码和Header... 目录1. 返回静态页面1.1 Spring 默认扫描路径1.2 @RestController2. 返回 html2

numpy求解线性代数相关问题

《numpy求解线性代数相关问题》本文主要介绍了numpy求解线性代数相关问题,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 在numpy中有numpy.array类型和numpy.mat类型,前者是数组类型,后者是矩阵类型。数组

Spring常见错误之Web嵌套对象校验失效解决办法

《Spring常见错误之Web嵌套对象校验失效解决办法》:本文主要介绍Spring常见错误之Web嵌套对象校验失效解决的相关资料,通过在Phone对象上添加@Valid注解,问题得以解决,需要的朋... 目录问题复现案例解析问题修正总结  问题复现当开发一个学籍管理系统时,我们会提供了一个 API 接口去