Consider a model of fire spreading through a graph; initially some vertices are burning, and at every given time-step fire spreads from burning vertices to their neighbours. The firefighter problem is a solitaire game in which a player is allowed, at every time-step, to protect some non-burning vertices (by effectively deleting them) in order to contain the fire growth. How many vertices per turn, on average, must be protected in order to stop the fire from spreading infinitely? Here we consider the problem on $\mathbb{Z}^2\times [h]$ for both nearest neighbour adjacency and strong adjacency. We determine the critical protection rates for these graphs to be $1.5h$ and $3h$, respectively. This establishes the fact that using an optimal two-dimensional strategy for all layers in parallel is asymptotically optimal.


翻译:考虑一个通过图表传播火的模型; 最初有些顶端正在燃烧, 并且在每个特定时间段从燃烧的脊椎向邻居扩散火力。 消防员的问题是一个单调游戏, 允许玩家在每一个时间段保护一些非燃烧的脊椎( 有效删除它们), 以遏制火灾的蔓延。 平均来说, 每转圈要保护多少个顶端, 才能阻止火灾无穷无尽的蔓延 。 我们在这里认为, $\ mathbb ⁇ 2\\ times 上的问题对于近邻的相邻关系和强相邻关系来说都是 $h] 。 我们确定这些图形的关键保护率分别为 1.5 h 美元 和 3 h 美元 。 这证明了一个事实, 对所有平行层使用最佳的二维策略是同样最佳的 。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
84+阅读 · 2020年12月5日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
72+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
110+阅读 · 2020年5月15日
一份循环神经网络RNNs简明教程,37页ppt
专知会员服务
172+阅读 · 2020年5月6日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
153+阅读 · 2019年10月12日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【推荐】(Keras)LSTM多元时序预测教程
机器学习研究会
24+阅读 · 2017年8月14日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年6月24日
Arxiv
0+阅读 · 2021年6月23日
Optimizing Ansatz Design in QAOA for Max-cut
Arxiv
0+阅读 · 2021年6月22日
Arxiv
6+阅读 · 2017年12月7日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
84+阅读 · 2020年12月5日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
72+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
110+阅读 · 2020年5月15日
一份循环神经网络RNNs简明教程,37页ppt
专知会员服务
172+阅读 · 2020年5月6日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
153+阅读 · 2019年10月12日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【推荐】(Keras)LSTM多元时序预测教程
机器学习研究会
24+阅读 · 2017年8月14日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员