|
数模美赛里面用到元胞自动机比较多，这两天主要下研究这个。
何谓自动机，说白了就是给定输入状态和前一个状态和下一个状态的转移方式，然后程序自己跑。
所以运用元胞自动机的生命游戏就是一个无玩家游戏，也就是不需要人工介入，自己跑的游戏。
元胞就类似遗传算法里的基因，也就是一个特性（一个人，一辆车），它受上下左右四个状态影响（或者加上左上左下，右上右下）
首先介绍一下生命游戏：
每一个各自有两个状态，生或者死。
每个格子的生死遵循下面的原则：
1． 如果一个细胞周围有3个细胞为生（一个细胞周围共有8个细胞），则该细胞为生（即该细胞若原先为死，则转为生，若原先为生，则保持不变） 。
2． 如果一个细胞周围有2个细胞为生，则该细胞的生死状态保持不变；
3． 在其它情况下，该细胞为死（即该细胞若原先为生，则转为死，若原先为死，则保持不变）
也就是随机各格子生死（当然也可以自己输入），然后告诉程序状态转移方式，然后让程序自己跑去。
下面是模拟的java代码:
game类:
public class game extends JFrame implements ActionListener{
JMenuBar menuBar;
JMenu menu;
JMenuItem menuitem,menuitem2;
auto g;
Thread thread;
public game(){
setTitle("我的生命游戏");
setLayout(null);
setBounds(100,100,700,700);
g=new auto();
thread=new Thread(g);
g.setBounds(0,0,600,600);
Container container=getContentPane();
menuBar=new JMenuBar();//创建菜单栏对象
setJMenuBar(menuBar);//添加菜单栏对象
menu=new JMenu("开始");//创建菜单对象
menuBar.add(menu);//将菜单对象添加到菜单栏对象中
menuitem=new JMenuItem("开始游戏");
menu.add(menuitem);
menuitem.addActionListener(this);//添加监听事件
menuitem2=new JMenuItem("重置");
menu.add(menuitem2);
menuitem2.addActionListener(this);//添加监听事件
container.add(g);
setVisible(true);
g.setFocusable(true);//关键之关键，jpanel添加键盘监听事件要聚焦到画板
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
public void actionPerformed(ActionEvent e){
if (e.getSource()==menuitem){
g.startgame();
if (!thread.isAlive())
thread.start();
System.out.println("1");
}
if (e.getSource()==menuitem2){
g.Clear();
System.out.println("2");
}
}
public static void main(String []args){
new game();
}
}
auto类:
public class auto extends JPanel implements Runnable {
int[][]life=new int[10][10];//存储状态
public void startgame(){
rand();//生成随机数
}
@Override
public void run(){
while(true){
try{
Thread.sleep(1000);
next();
repaint();
}catch(InterruptedException e){
e.printStackTrace();
}
}
}
public void paint(Graphics g){
g.clearRect(0,0,600,600);
for (int i=0;i<10;i++)
for (int j=0;j<10;j++)
{
if (life[i][j]==0){
g.setColor(Color.RED);
}
if (life[i][j]==1){
g.setColor(Color.yellow);
}
g.fillRect(j*60, i*60, 60, 60);
}
}
public void next(){
for (int i=0;i<10;i++)
for (int j=0;j<10;j++)
{
int answer=search(i,j);
if (answer==3)
life[i][j]=1;
if ((answer==1)||(answer==4)||(answer==5)||(answer==6)||(answer==7)||(answer==8))
life[i][j]=0;
}
}
public void Clear(){
life=new int[10][10];
repaint();
}
public int search(int x,int y){
int sum=0;
if ((-1+x>=0)&&(-1+y>=0)&&life[x-1][y-1]==1){//左上角
sum++;
}
if ((-1+x>=0)&&(life[x-1][y]==1)){//上部
sum++;
}
if ((-1+x>=0)&&(y+1<10)&&life[x-1][y+1]==1){//右上部
sum++;
}
if ((y-1>=0)&&life[x][y-1]==1){//左部
sum++;
}
if ((y+1<10)&&life[x][y+1]==1){//右部
sum++;
}
if ((x+1<10)&&(y-1>=0)&&life[x+1][y-1]==1){//左下部
sum++;
}
if ((x+1<10)&&life[x+1][y]==1){//下部
sum++;
}
if ((x+1<10&&y+1<10&&life[x+1][y+1]==1)){//右下部
sum++;
}
return sum;
}
public void rand(){
for (int i=0;i<10;i++)
for (int j=0;j<10;j++)
life[i][j]=(int)Math.round(Math.random());
}
}
当然这个比较简单，但是我们可以参考国赛2003年非典那题和2014年美赛超车那题。
比如非典那题我们假设了传染率随时间变化的公式，那么每一次迭代传染率都会改变，然后当周围格子患病并且通过传染率，那么这个格子就病了。（当然为了模型更加符合实际，还要考虑抵抗率以及潜伏期之类的）
超车那题我们可以假设初始车速，当后面的车速大于前面的并且左右两边存在空位，那么就可以超车，都是可以用元胞自动机实现模拟，具体的代码只需要修改next函数即可。
元胞自动机其实就是一种大模拟，用处就是当公式直接推比较复杂，我们模拟空间上的传染（超车）变化，获得下一时刻状态。
| 
转播
