原型是最近玩《滞困:异星黎明》遇到的,游戏是类环世界那样的风格,设定中,一个区域(每个区域都是正方形)的四条边都至少有一条相邻边是空着的才能运行,于是在建仓库的时候经常遇到规划一个大区域,同时要在其中留好空隙让每个区域都能运作的问题。
转化为数学问题,可以想作,在一个大棋盘中填入0和1,其中,每个1至少有一个边上是0,那么怎么规划填入更多的1?
、
比如一个3x3的空,虽然第一想法肯定是所有的1和0错开放,至少不会出错,但是这样摆不一定是最优的。
我初步的想法是,这个问题反过来想,一个0可以提供4个1的位置,角上的0可以提供2个1,边上的0可以提供3个1,那么把各种0和他们提供的1组成一个图形,可以转变成在区域里填入特定图形的模式:

用黄色代表边上的0组成的T字形,绿色代表角上的0组成的三角形,多余的两块空白则2选1。
这样的好处是,组合好的图形会进一步把棋盘封闭,减少一个1被多个0反复占用的情况。

如果用填色法来给我的仓库规划,就会长成这个样子。
感觉这个规划问题还挺有意思的,有点像围棋里的气反过来的解法,不知道8u有没有过类似的经历
转化为数学问题,可以想作,在一个大棋盘中填入0和1,其中,每个1至少有一个边上是0,那么怎么规划填入更多的1?
、
比如一个3x3的空,虽然第一想法肯定是所有的1和0错开放,至少不会出错,但是这样摆不一定是最优的。
我初步的想法是,这个问题反过来想,一个0可以提供4个1的位置,角上的0可以提供2个1,边上的0可以提供3个1,那么把各种0和他们提供的1组成一个图形,可以转变成在区域里填入特定图形的模式:

用黄色代表边上的0组成的T字形,绿色代表角上的0组成的三角形,多余的两块空白则2选1。
这样的好处是,组合好的图形会进一步把棋盘封闭,减少一个1被多个0反复占用的情况。

如果用填色法来给我的仓库规划,就会长成这个样子。
感觉这个规划问题还挺有意思的,有点像围棋里的气反过来的解法,不知道8u有没有过类似的经历









