#c#用广度优先搜索求八数码最优解
#搜索遍历失败
using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace 拼图游戏1._0._4
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
public static int[][] map = new int[3][] { new int[3] { 0, 1, 2 }, new int[3] { 3, 4, 5 }, new int[3] { 6, 7, 8 } };//正确的地图
public static int[][] arr = new int[3][];//储存随机地图
public static int[] a = new int[9] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
public static int min = 99999;
public static int x, y;
public static int[][] Newsorting(int []a)//随机打乱
{
Random r = new Random();
for (int i = 0; i < a.Length; i++)
{
int temp = a[i];
int randomindex = r.Next(0, a.Length);
a[i] = a[randomindex];
a[randomindex] = temp;
}
int[][] arr= new int[][] { new int[] { a[0], a[1] ,a[2]},new int[] { a[3], a[4], a[5] },new int[] { a[6], a[7], a[8] } };
return arr;
}
public static void bfs()//广度优先搜素
{
HuaRongDao hua = new HuaRongDao();
int step=0, tx, ty,startx,starty;
bool flag = false;
ArrayList set = new ArrayList();//记录走过的路径
Queue q = new Queue();
int[][] next = new int[][]
{
new int[] { 0, 1 }, //向右
new int[] { 1, 0 }, //向下
new int[] { 0, -1 },//向左
new int[] { -1, 0 } //向上
};
q.Enqueue(arr);
//将初始地图加入到队列
set.Add(arr);//记录初始地图
while (q.Count>0) //当队列不为空时循环
{
hua.Startdirection(arr);//获取当前0的位置
startx = x;
starty = y;
for (int i = 0; i < next.Length; i++)
{
//计算下一步的坐标
tx = startx + next[i][0];
ty = starty + next[i][1];
//判断是否越界
if (tx < 0 || tx > 2 || ty < 0 || ty > 2)
{
continue;
}
else
{
arr = hua.Move(startx, starty, tx, ty);//交换位置
bool s = set.Contains(arr);//判断是否有重复
if (s == false)
{
set.Add(arr);//将交换后的地图保存
q.Enqueue(arr);
//把新的地图加到队列中
hua.Startdirection(arr);//更新0的坐标
startx = x;
starty = y;
}
}
}
flag = over(arr, map);//判断是否完成
if (flag == true)//如果找到终点，停止扩展，任务结束，退出while循环
{
break;
}
object used = q.Dequeue();
step++;
if (step < min) { min = step; }
}
}
public static bool over(int[][]arr,int[][]map)
{ for(int i=0;i<3;i++)
{ for (int j = 0; j < 3; j++) { if (arr[i][j] == map[i][j])
return true;
} }
return false; }
class HuaRongDao
{
public int Startdirection(int[][] arr)//找到地图中0的初始横纵坐标
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < arr[i].Length; j++)
{
if (arr[i][j] == 0)
{
x = i;
y = j;
}
}
}
return x&y;
}
public int[][] Move(int x,int y,int tx,int ty)
{
int temp;
temp = arr[tx][ty];
arr[tx][ty] = 0;
arr[x][y] = temp;
return arr;
}
}
private void button1_Click(object sender, EventArgs e)
{
arr = Newsorting(a);
label1.Text = Convert.ToString(arr[0][0]);
label2.Text = Convert.ToString(arr[0][1]);
label3.Text = Convert.ToString(arr[0][2]);
label4.Text = Convert.ToString(arr[1][0]);
label5.Text = Convert.ToString(arr[1][1]);
label6.Text = Convert.ToString(arr[1][2]);
label7.Text = Convert.ToString(arr[2][0]);
label8.Text = Convert.ToString(arr[2][1]);
label9.Text = Convert.ToString(arr[2][2]);
}
private void button2_Click(object sender, EventArgs e)
{
HuaRongDao hua = new HuaRongDao();
hua.Startdirection(arr);
bfs();
textBox1.Text = "最短路径：" + Convert.ToString(min);
}
}
}
代码中存在一些问题，可能导致搜索遍历失败。
在遍历时使用了一个死循环。当队列为空时，代码会一直进行下去。如果在遍历过程中发现无解，那么就会导致死循环。
其次代码中缺少了终止条件。在遍历过程中，应该判断当前地图状态是否与目标状态相同，如果相同就可以终止搜索。
代码中缺少了剪枝的操作。剪枝是指在搜索过程中，对一些不可能是最优解的路径进行剪去
仅供参考，望采纳。
在你的代码中，你使用了一个 set 集合来记录已经访问过的状态，并使用 set.Contains() 方法来判断当前状态是否已经访问过。这是正确的。
然而，我发现你在搜索过程中并没有使用队列来记录待搜索的状态。在你的代码中，你使用了一个 while 循环，并在循环内部枚举了每一种转移方式，然后改变当前状态。但是，你并没有将新的状态加入到队列中。因此，你的程序将无法正常运行。
为了解决这个问题，你需要在每次改变状态之后，将新的状态加入到队列中。例如，你可以在枚举每种转移方式后，使用 q.Enqueue(arr) 将新的状态加入到队列中。这样，你就可以保证每一个状态都能够被正确地搜索到。
此外，你还需要注意，在你的代码中，你使用了一个变量 min 来记录最小步数，并在每次更新 min 的值时使用一个 flag 变量来记录是否找到了最优解。但是，你并没有在每次转移状态后将 step 加一，也就是说，你的程序并没有统计每一次状态转移的步数。因此，你的程序将无法正常计算出最优解。
为了解决这个问题，你需要在每次转移状态后将 step 加一。例如，你可以在枚举每种转移方式后，使用 step++ 将 step 加一。这样，你就可以保证每一次状态转移的步数都能够被正确地统计。
最后，我还想提醒你，在你的代码中，你定义了一个 Newsorting() 函数用于随机打乱数组，并使用 Random r = new Random() 生成随机数。但是，你需要注意，使用这种方式生成的随机数并不是真正的随机数，而是伪随机数。伪随机数是由计算机算法生成的随机数，它的生成是基于一个种子数，如果种子数相同，则生成的随机数序列也是相同的。
如果你希望生成真正的随机数，你可以使用 System.Security.Cryptography.RandomNumberGenerator 类来生成随机数。这个类使用了真正的随机数生成算法，可以生成真正的随机数。
例如，你可以使用以下代码来生成一个随机数：
using System.Security.Cryptography;
RandomNumberGenerator rng = RandomNumberGenerator.Create();
byte[] bytes = new byte[4];
rng.GetBytes(bytes);
int randomNumber = BitConverter.ToInt32(bytes, 0);
这样，你就可以生成真正的随机数了。
public class PuzzleState
{
// Fields to store the puzzle configuration and metadata
private int[,] tiles;
private int depth;
private PuzzleState parent;
private int blankRow;
private int blankCol;
// Constructor to create a new puzzle state
public PuzzleState(int[,] tiles, int depth, PuzzleState parent, int blankRow, int blankCol)
{
this.tiles = tiles;
this.depth = depth;
this.parent = parent;
this.blankRow = blankRow;
this.blankCol = blankCol;
}
// Method to generate the valid next states from this puzzle state
public List<PuzzleState> GetNextStates()
{
List<PuzzleState> nextStates = new List<PuzzleState>();
// Try moving the blank tile up
if (blankRow > 0)
{
int[,] newTiles = (int[,])tiles.Clone();
newTiles[blankRow, blankCol] = newTiles[blankRow - 1, blankCol];
newTiles[blankRow - 1, blankCol] = 0;
nextStates.Add(new PuzzleState(newTiles, depth + 1, this, blankRow - 1, blankCol));
}
// Try moving the blank tile down
if (blankRow < 2)
{
int[,] newTiles = (int[,])tiles.Clone();
newTiles[blankRow, blankCol] = newTiles[blankRow + 1, blankCol];
newTiles[blankRow + 1, blankCol] = 0;
nextStates.Add(new PuzzleState(newTiles, depth + 1, this, blankRow + 1, blankCol));
}
// Try moving the blank tile left
if (blankCol > 0)
{
int[,] newTiles = (int[,])tiles.Clone();
newTiles[blankRow, blankCol] = newTiles[blankRow, blankCol - 1];
new
#include<stdio.h>
struct node
{
int xy[3][3];
int dir;
};
struct node sh[102], end;
int count = 1;
void init()
{
printf("输入起始节点的位置:n");
int i, j;
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
scanf("%d", &sh[0].xy[i][j]);
sh[0].dir = -1;
printf("输入目标节点的位置:n");
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
scanf("%d", &sh[101].xy[i][j]);
sh[101].dir = -1;
}
//找出0的位置
int loction(int num)
{
int i;
for (i = 0; i < 9; i++)
if (sh[num].xy[i / 3][i % 3] == 0) return i;
}
//进行标记
long long sign(int num)
{
long long sum;
sum = sh[num].xy[0][0]*100000000 + sh[num].xy[0][1]*10000000 + sh[num].xy[0][2]*1000000 + sh[num].xy[1][0]*100000 + sh[num].xy[1][1]*10000 + sh[num].xy[1][2]*1000 + sh[num].xy[2][0]*100 + sh[num].xy[2][1]*10 + sh[num].xy[2][2];
return sum;
}
void mobile(int num)
{
int temp;
int loc;
int up = 1, down = 1, left = 1, right = 1;
loc = loction(num);
int stand = sh[num].dir;
//dir的0 1 2 3分别代表左 上 右 下
if (loc / 3 != 0 && stand != 1)
{
sh[count] = sh[num];
temp = sh[count].xy[loc / 3][loc % 3];
sh[count].xy[loc / 3][loc % 3] = sh[count].xy[loc / 3 - 1][loc % 3];
sh[count].xy[loc / 3 - 1][loc % 3] = temp;
sh[count].dir = 3;
count++;
};
if (loc / 3 != 2 && stand != 3)
{
sh[count] = sh[num];
temp = sh[count].xy[loc / 3][loc % 3];
sh[count].xy[loc / 3][loc % 3] = sh[count].xy[loc / 3 + 1][loc % 3];
sh[count].xy[loc / 3 + 1][loc % 3] = temp;
sh[count].dir = 1;
count++;
}
if (loc % 3 != 0 && stand != 0)
{
sh[count] = sh[num];
temp = sh[count].xy[loc / 3][loc % 3];
sh[count].xy[loc / 3][loc % 3] = sh[count].xy[loc / 3][loc % 3 - 1];
sh[count].xy[loc / 3][loc % 3 - 1] = temp;
sh[count].dir = 2;
count++;
}
if (loc % 3 != 2 && stand != 2)
{
sh[count] = sh[num];
temp = sh[count].xy[loc / 3][loc % 3];
sh[count].xy[loc / 3][loc % 3] = sh[count].xy[loc / 3][loc % 3 + 1];
sh[count].xy[loc / 3][loc % 3 + 1] = temp;
sh[count].dir = 0;
count++;
}
}
void display(int num)
{
int i, j;
for (i = 0; i < 3; i++)
{
for (j = 0; j < 3; j++)
printf("%d ", sh[num].xy[i][j]);
printf("n");
}
}
int search()
{
int i = 0;
while (1)
{
printf("n");
display(i);
printf("n");
if (i == 100)
{
printf("超出了上限次数n");
return 0;
}
if (sign(i) == sign(101))
{
printf("在第%d次找到了", i);
display(i);
return i;
}
mobile(i);
i++;
}
}
int main()
{
init();
search();
return 0;
}
//测试用例
/*
2 8 3
1 6 4
7 0 5
1 2 3
7 8 4
0 6 5
*/
大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！
大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！
大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！
import numpy as np
class State:
def __init__(self, state, directionFlag=None, parent=None):
self.state = state
self.direction = ['up', 'down', 'right', 'left']
if directionFlag:
self.direction.remove(directionFlag)
self.parent = parent
self.symbol = ' '
def getDirection(self):
return self.direction
def showInfo(self):
for i in range(3):
for j in range(3):
print(self.state[i, j], end=' ')
print("\n")
print('->\n')
return
def getEmptyPos(self):
postion = np.where(self.state == self.symbol)
return postion
def generateSubStates(self):
if not self.direction:
return []
subStates = []
boarder = len(self.state) - 1
row, col = self.getEmptyPos()
if 'left' in self.direction and col > 0:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row, col-1]
s[row, col-1] = temp[row, col]
news = State(s, directionFlag='right', parent=self)
subStates.append(news)
if 'up' in self.direction and row > 0:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row-1, col]
s[row-1, col] = temp[row, col]
news = State(s, directionFlag='down', parent=self)
subStates.append(news)
if 'down' in self.direction and row < boarder:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row+1, col]
s[row+1, col] = temp[row, col]
news = State(s, directionFlag='up', parent=self)
subStates.append(news)
if self.direction.count('right') and col < boarder:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row, col+1]
s[row, col+1] = temp[row, col]
news = State(s, directionFlag='left', parent=self)
subStates.append(news)
return subStates
def solve(self):
openTable = []
closeTable = []
openTable.append(self)
steps = 1
while len(openTable) > 0:
n = openTable.pop(0)
closeTable.append(n)
subStates = n.generateSubStates()
path = []
for s in subStates:
if (s.state == s.answer).all():
while s.parent and s.parent != originState:
path.append(s.parent)
s = s.parent
path.reverse()
return path, steps+1
openTable.extend(subStates)
steps += 1
else:
return None, None
if __name__ == '__main__':
symbolOfEmpty = ' '
State.symbol = symbolOfEmpty
originState = State(np.array([[2, 8, 3], [1, 6 , 4], [7, symbolOfEmpty, 5]]))
State.answer = np.array([[1, 2, 3], [8, State.symbol, 4], [7, 6, 5]])
s1 = State(state=originState.state)
path, steps = s1.solve()
if path:
for node in path:
node.showInfo()
print(State.answer)
print("Total steps is %d" % steps)
大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！
大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！
大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！
大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！
大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！
大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！
import numpy as np
class State:
def __init__(self, state, directionFlag=None, parent=None):
self.state = state
self.direction = ['up', 'down', 'right', 'left']
if directionFlag:
self.direction.remove(directionFlag)
self.parent = parent
self.symbol = ' '
def getDirection(self):
return self.direction
def showInfo(self):
for i in range(3):
for j in range(3):
print(self.state[i, j], end=' ')
print("\n")
print('->\n')
return
def getEmptyPos(self):
postion = np.where(self.state == self.symbol)
return postion
def generateSubStates(self):
if not self.direction:
return []
subStates = []
boarder = len(self.state) - 1
row, col = self.getEmptyPos()
if 'left' in self.direction and col > 0:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row, col-1]
s[row, col-1] = temp[row, col]
news = State(s, directionFlag='right', parent=self)
subStates.append(news)
if 'up' in self.direction and row > 0:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row-1, col]
s[row-1, col] = temp[row, col]
news = State(s, directionFlag='down', parent=self)
subStates.append(news)
if 'down' in self.direction and row < boarder:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row+1, col]
s[row+1, col] = temp[row, col]
news = State(s, directionFlag='up', parent=self)
subStates.append(news)
if self.direction.count('right') and col < boarder:
s = self.state.copy()
temp = s.copy()
s[row, col] = s[row, col+1]
s[row, col+1] = temp[row, col]
news = State(s, directionFlag='left', parent=self)
subStates.append(news)
return subStates
def solve(self):
openTable = []
closeTable = []
openTable.append(self)
steps = 1
while len(openTable) > 0:
n = openTable.pop(0)
closeTable.append(n)
subStates = n.generateSubStates()
path = []
for s in subStates:
if (s.state == s.answer).all():
while s.parent and s.parent != originState:
path.append(s.parent)
s = s.parent
path.reverse()
return path, steps+1
openTable.extend(subStates)
steps += 1
else:
return None, None
if __name__ == '__main__':
symbolOfEmpty = ' '
State.symbol = symbolOfEmpty
originState = State(np.array([[2, 8, 3], [1, 6 , 4], [7, symbolOfEmpty, 5]]))
State.answer = np.array([[1, 2, 3], [8, State.symbol, 4], [7, 6, 5]])
s1 = State(state=originState.state)
path, steps = s1.solve()
if path:
for node in path:
node.showInfo()
print(State.answer)
print("Total steps is %d" % steps)
大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！
大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！
大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！大佬求采纳！！！