主页
题目
状态
排名
OI排名
统计
题解
请登录
常用链接
AOJ考试平台
老赵的Gitee代码
编译原理模拟考试平台
Java技术手册
FCC网站
菜鸟网
在线工具箱
字节豆包GPT
代码可视化
力扣网
牛客网
洛谷
杭电OJ
CodeForce
隐藏编译器
Problem C: 2025AHCPC_C强化学习
上一题
正确率: $63.89\%$
下一题
Time Limit
$1$ 秒/Second(s)
Memory Limit
$128$ 兆字节/Megabyte(s)
提交总数
$72$
正确数量
$46$
"
裁判形式
标准裁判/Standard Judge
我的状态
尚未尝试
难度
分类标签
×
为本题添加算法分类(请不要超过5个)
当前分类(单击移除):
单击选择分类:
Description
<p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> 在人工智能迅猛发展的今天,强化学习 (RL) 已经成为智能体构建,大模型对齐等技术的重要支柱. Q 学习是强化学习的一种经典算法,而迷宫问题是 Q 学习的一个经典问题,小明设计了利用 Q 学习走迷宫的智能体,这个迷宫是三维的,内含很多障碍物,但是他编程基础太差,只完成了代码框架,所以需要你的帮助,完成整个智能体.</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> Q 学习是一种无监督学习方法,他主要有以下几个部分组成.</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <br /> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> </span><span style="color:#000000;">1.</span><span style="font-weight:bolder;color:#000000;">状态 (state)</span><span style="color:#000000;">:智能体所处的环境表示,在当前问题下,即为智能体目前所处的位置 (x0,y0,z0).</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <br /> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> </span><span style="color:#000000;">2.</span><span style="font-weight:bolder;color:#000000;">动作 (Action)</span><span style="color:#000000;">:智能体在某个状态下可执行的操作,在当前问题中,包括在 (x,y,z) 三个方向的六种移动,包括向前,向后,向左,向右,向上,向下移动一格和停留在原地七种,不允许在多个维度上同时移动,也不能移动到障碍物上和地图之外,形式化地:</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> </span><span style="color:#000000;">Ai∈{(0,0,1),(0,0,−1),(0,1,0),(0,−1,0),(1,0,0),(−1,0,0),(0,0,0)}</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <br /> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> </span><span style="color:#000000;">3.</span><span style="font-weight:bolder;color:#000000;">奖励 (Reward)</span><span style="color:#000000;">:智能体执行动作后环境返回地即时反馈 R(s,a),在此问题中定义如下:</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <br /> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> </span><span style="color:#000000;">到达目标每执行一次动作但未达到目标R(s,a)={N3,到达目标−1,每执行一次动作但未达到目标</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <br /> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> </span><span style="color:#000000;">4.</span><span style="font-weight:bolder;color:#000000;">Q 表 (Q−Table)</span><span style="color:#000000;">:存储某一状态 (State) 下的预期累计奖励 (Q 值 ),即 Q(s),他表示</span><span style="font-weight:bolder;color:#000000;">从初始状态 Sbegin 到当前状态 S1 的所进行操作序列的奖励值之和</span><span style="color:#000000;">.</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <br /> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> </span><span style="color:#000000;">小杨正在帮小明优化奖励函数,他想知道,从起点 (1,1,1) 出发,到达终点 (N,N,N) 状态 Send 下的 Qend 值最大是多少.但小明视力非常不好,如果给他太多的数字会头晕眼花,所以小明采用了一种新颖的方法将地图数据告诉小明和你,请你帮他解决这个问题.</span> </p> <span style="color:#000000;"></span><br />
Input
<p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> </span><span style="font-weight:bolder;color:#000000;">题目有多组测试数据</span><span style="color:#000000;">.</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> </span><span style="color:#000000;">输入的第一行,为一个正整数 T,代表数据组数.</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> </span><span style="color:#000000;">对于每一组数据,第一行输入一个整数 N,表示指定的三维地图每一维度的大小.</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;"> </span><span style="color:#000000;">第 2∼N+1 行,每行输入 N 个数,共 N2 个数,对于 (i,j) 位置上的数 ai,j,其二进制下的第 k 位代表地图中位置 (i,j,k+1) 的值 mapi,j,k+1,其中 mapi,j,k+1∈{0,1},值为 0 代表地图中该位置为空,值为 1 代表地图中该位置为障碍物.</span> </p> <span style="color:#000000;"></span><br />
Output
<span style="color:#000000;font-family:Google_sans;font-size:17px;"> </span><span style="color:#000000;font-family:Google_sans;font-size:17px;">输出 </span><span style="color:#000000;">T</span><span style="color:#000000;font-family:Google_sans;font-size:17px;"> 行,每行一个正整数,代表从起点 </span><span style="color:#000000;">(1,1,1)</span><span style="color:#000000;font-family:Google_sans;font-size:17px;"> 出发,到达终点 </span><span style="color:#000000;">(N,N,N)</span><span style="color:#000000;font-family:Google_sans;font-size:17px;"> 状态 </span><span style="color:#000000;">Send</span><span style="color:#000000;font-family:Google_sans;font-size:17px;"> 下的 </span><span style="color:#000000;">Q(Send)</span><span style="color:#000000;font-family:Google_sans;font-size:17px;"> 最大值,若无法到达终点,请输出 </span><span style="color:#000000;">IMPOSSIBLE</span><span style="color:#000000;font-family:Google_sans;font-size:17px;">.</span><span style="background-color:;"></span><br />
Sample Input
复制
2 3 6 0 7 1 0 7 0 0 2 3 6 1 7 1 0 7 0 0 2
Sample Output
复制
22 IMPOSSIBLE
提示
<h3 style="font-family:Google_sans, Lato, "color:#FFFFFF;font-size:1.6rem;"> <span style="color:#000000;">样例解释</span> </h3> <hr /> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;">对于样例 1,机器人通过 6 步到达终点,其中前 5 步的奖励为 −1,最后一步的奖励为 27,总和为 22.</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;">对于样例 2,机器人无法到达终点.</span> </p> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="background-color:;"></span> </p> <h3 style="font-family:Google_sans, Lato, "color:#FFFFFF;font-size:1.6rem;"> <span style="color:#000000;">数据规模与约定</span> </h3> <hr /> <p style="color:#FFFFFF;font-family:Google_sans;font-size:17px;"> <span style="color:#000000;">对于 100% 的数据, 1≤T≤100,1≤N≤64,0<mapi,j<2N−1.</span> </p> <br />
AOJ
Please Login