2704: 2025AHCPC - 强化学习

         在人工智能迅猛发展的今天,强化学习 $(RL)$ 已经成为智能体构建,大模型对齐等技术的重要支柱. $Q$ 学习是强化学习的一种经典算法,而迷宫问题是 $Q$ 学习的一个经典问题,小明设计了利用 $Q$ 学习走迷宫的智能体,这个迷宫是三维的,内含很多障碍物,但是他编程基础太差,只完成了代码框架,所以需要你的帮助,完成整个智能体.

         $Q$ 学习是一种无监督学习方法,他主要有以下几个部分组成.

         $1$.状态 $(state)$:智能体所处的环境表示,在当前问题下,即为智能体目前所处的位置 $(x_0,y_0,z_0)$.

         $2$.动作 $(Action)$:智能体在某个状态下可执行的操作,在当前问题中,包括在 $(x,y,z)$ 三个方向的六种移动,包括向前,向后,向左,向右,向上,向下移动一格和停留在原地七种,不允许在多个维度上同时移动,也不能移动到障碍物上和地图之外,形式化地:

         $A_i\in \{(0,0,1),(0,0,-1),(0,1,0),(0,-1,0),(1,0,0),(-1,0,0),(0,0,0)\}$

         $3$.奖励 $(Reward)$:智能体执行动作后环境返回地即时反馈 $R(s,a)$,在此问题中定义如下:

         $R(s,a)=\left\{\begin{matrix}N^3,到达目标\\-1,每执行一次动作但未达到目标\end{matrix}\right.$

         $4$.$Q$ 表 $(Q-Table)$:存储某一状态 $(State)$ 下的预期累计奖励 $(Q$ 值 $)$,即 $Q(s)$,他表示从初始状态 $S_{begin}$ 到当前状态 $S_1$ 的所进行操作序列的奖励值之和.

         小杨正在帮小明优化奖励函数,他想知道,从起点 $(1,1,1)$ 出发,到达终点 $(N,N,N)$ 状态 $S_{end}$ 下的 $Q_{end}$ 值最大是多少.但小明视力非常不好,如果给他太多的数字会头晕眼花,所以小明采用了一种新颖的方法将地图数据告诉小明和你,请你帮他解决这个问题.

         题目有多组测试数据.

         输入的第一行,为一个正整数 $T$,代表数据组数.

         对于每一组数据,第一行输入一个整数 $N$,表示指定的三维地图每一维度的大小.

         第 $2 \sim N+1$ 行,每行输入 $N$ 个数,共 $N^2$ 个数,对于 $(i,j)$ 位置上的数 $a_{i,j}$,其二进制下的第 $k$ 位代表地图中位置 $(i,j,k + 1)$ 的值 $map_{i,j,k+1}$,其中 $map_{i,j,k+1}\in \left \{ 0,1 \right \} $,值为 $0$ 代表地图中该位置为空,值为 $1$ 代表地图中该位置为障碍物.

2
3
6 0 7
1 0 7
0 0 2
3
6 1 7
1 0 7
0 0 2

22
IMPOSSIBLE