`
xglv2013
  • 浏览: 38060 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Java实现的矩阵链乘法动态规划算法Swing动态演示器

阅读更多
    矩阵链乘法问题,是动态规划的一个经典问题。目的是使一个相乘的矩阵序列所用的乘法次数最少。这里用Java Swing实现了矩阵链乘法的动态演示。用到两个二维数组,m和s。其中m[i][j]的值表示第i个矩阵和第j个矩阵之间的最优的加括号的方案。s[i][j]的值表示第i个矩阵和第j个矩阵最外层的两部分在何处断开。关于矩阵、矩阵相容性和矩阵链乘法算法的详细介绍请查阅《算法导论》第15章《动态规划》,在此不做赘述。
   
算法运行之前:



算法运行中(其中绿色方块表示已经计算出的值,黄色方块表示正在计算的值,蓝色方块表示当前计算的值所依靠的值):



算法运行结束:


代码:
import java.awt.Color;
import java.awt.Container;
import java.awt.EventQueue;
import java.awt.Font;
import java.awt.Frame;
import java.awt.Graphics;
import java.awt.Polygon;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.JButton;
import javax.swing.JComboBox;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
import javax.swing.WindowConstants;
 
	
public class MatrixChainGUI extends JFrame
{
	int n;//矩阵个数
    int di;//正方形斜对角线长
    int XMStart;//m值菱形数组最左边的x坐标
    int YStart;//菱形数组最左边的y坐标
    int xSStart;//s值菱形数组最左边的x坐标
	int rstStrXStart;//最优加括号矩阵链起始横坐标
	Polygon[][] polygonArrayM;//m值菱形数组
	Polygon[][] polygonArrayS;//s值菱形数组
	int[] p;
	JPanel charPanel;
	JComboBox change;
    JButton calculate = new JButton("开始/暂停");
    Container pane;
    DrawPolygon d;//画表格
    DrawCalculateRst dr;//计算并向屏幕写结果的任务
    Thread algThread;//计算向屏幕写结果的线程
    PauseOrResume pOR;//暂停、恢复的任务
    Thread pORThread;//暂停、恢复的线程
    SynObj so = new SynObj();//用以同步
	int interval;//计算速度
    boolean awake = false;//暂停、恢复计算线程初始化为睡眠状态
    Font fontLetter = new Font("letter", 0, 18);//字母字体
    Font fontNumber = new Font("number", 0, 10);//角标字体
    Font fontBracket = new Font("number", 0, 17);//括号字体
	public MatrixChainGUI(int[] p, int di)
	{
        super();
        n = p.length - 1;
        if(n <= 2)
        {
        	JOptionPane.showMessageDialog(MatrixChainGUI.this, 
  		          "矩阵数目最少为3", "", JOptionPane.ERROR_MESSAGE);
        	System.exit(0);
        }
        this.p = p;
        this.di = di;
        XMStart = di/2;//m值菱形数组最左边的x坐标
        YStart = di * (n+2)/2;//菱形数组最左边的y坐标
        xSStart = XMStart + n*di;//s值菱形数组最左边的x坐标
    	rstStrXStart = XMStart;//最优加括号矩阵链起始横坐标
    	polygonArrayM = new Polygon[n+1][n+1];//m值菱形数组
    	polygonArrayS = new Polygon[n+1][n+1];//s值菱形数组
        
		pane = this.getContentPane();
	    d = new DrawPolygon();
	    d.setIgnoreRepaint(true);
	    charPanel = new JPanel();
	    String str[] = { "1", "2", "3" };
	    change = new JComboBox(str);
	    charPanel.add(new JLabel("速度:"));
	    charPanel.add(change);
	    charPanel.add(calculate);
	    pane.add("South", charPanel);
	    pane.add("Center", d);
	    
	    calculate.addActionListener(new ActionListener()
	    {
	    	public void actionPerformed(ActionEvent arg0) 
			{
				if(so.status.equals("0"))
				{
				    pOR = new PauseOrResume();
				    pORThread = new Thread(pOR);
				    pORThread.start();//启动暂停或恢复计算的线程
				    
					if(change.getSelectedItem().toString().equals("1"))
					{
						interval = 1000;
					}
					else if(change.getSelectedItem().toString().equals("2"))
					{
						interval = 600;
					}
					else
					{
						interval = 200;
					}
				    dr = new DrawCalculateRst();
					pane.add(dr);
				    algThread = new Thread(dr);
					algThread.start();//启动开始计算的线程
				}
				//若正在运行,则进入暂停状态;若已经暂停,则恢复
				else if(so.status.equals("2") || so.status.equals("1"))
				{
					awake = true;
				}
			}
	    });
	}
	
	public class DrawPolygon extends JPanel
	{
	    public void paintComponent(Graphics g)
	    {
	    	super.paintComponents(g);
	    	
	    	//绘制m值表格
		    int outCount = 1;
		    int q = 0;//纵坐标偏移单位
		    while(outCount < n + 1)
		    {
			    int inCount = 1;
			    int p = 0;//横坐标偏移单位
			    int j = outCount, i = 1;
			    while(inCount < n + 2 - outCount)
			    {
				    int X[] = {XMStart+di*p+di/2*q,XMStart+di/2+di*p+di/2*q,XMStart+di+di*p+di/2*q,XMStart+di/2+di*p+di/2*q};
	                int Y[] = {YStart-di/2*q,YStart+di/2-di/2*q,YStart-di/2*q,YStart-di/2-di/2*q};
			        polygonArrayM[i][j] = new Polygon(X,Y,4);
			        g.drawPolygon(polygonArrayM[i][j]);
			        p++;
			        i++;
			        j++;
			        inCount++;
			    }
			    q++;
			    outCount++;
		    }
		    
		    g.drawString("m", XMStart + di * n/2, YStart - di * (n + 1)/2);
		    
		    //绘制m值编号
		    for(int i = 1; i <= n; i++)
			{
				int xl = polygonArrayM[1][i].xpoints[0];
				int yl = polygonArrayM[1][i].ypoints[0];
				int xr = polygonArrayM[i][n].xpoints[0];
				int yr = polygonArrayM[i][n].ypoints[0];
				
				setColorAndDrawStr(g, Color.BLACK, i, xl, yl, 0, -9*di/25);
				setColorAndDrawStr(g, Color.BLACK, i, xr, yr, 4*di/5, -9*di/25);
			}
		    
		    //绘制i,j字母
		    int xj = polygonArrayM[1][n/2].xpoints[0];
		    int yj = polygonArrayM[1][n/2].ypoints[0];
		    int xi = polygonArrayM[n/2 + 1][n].xpoints[0];
		    int yi = polygonArrayM[n/2 + 1][n].ypoints[0];
		    
		    setColorAndDrawStr(g, Color.BLACK, "j", xj, yj, 0, -di);
		    setColorAndDrawStr(g, Color.BLACK, "i", xi, yi, di, -di);
		    
		    //绘制s值表格
		    int outCount1 = 2;
		    int q1 = 1;//纵坐标偏移单位
		    while(outCount1 < n + 1)
		    {
			    int inCount = 1;
			    int p = 1;//横坐标偏移单位
			    int j = outCount1, i = 1;
			    while(inCount < n + 2 - outCount1)
			    {
				    int X[] = {xSStart+di*p+di/2*q1,xSStart+di/2+di*p+di/2*q1,xSStart+di+di*p+di/2*q1,xSStart+di/2+di*p+di/2*q1};
	                int Y[] = {YStart-di/2*q1,YStart+di/2-di/2*q1,YStart-di/2*q1,YStart-di/2-di/2*q1};
			        polygonArrayS[i][j] = new Polygon(X,Y,4);
			        g.drawPolygon(polygonArrayS[i][j]);
			        p++;
			        i++;
			        j++;
			        inCount++;
			    }
			    q1++;
			    outCount1++;
		    }
		    
		    g.drawString("s", xSStart + di * (n + 2)/2, YStart - di * (n + 1)/2);
		    
		    //绘制s值编号
		    for(int i = 2; i <= n; i++)
			{
				int xl = polygonArrayS[1][i].xpoints[0];
				int yl = polygonArrayS[1][i].ypoints[0];
				
				setColorAndDrawStr(g, Color.BLACK, i, xl, yl, 0, -9*di/25);
			}
		    for(int i = 1; i <= n - 1; i++)
		    {

				int xr = polygonArrayS[i][n].xpoints[0];
				int yr = polygonArrayS[i][n].ypoints[0];
				
				setColorAndDrawStr(g, Color.BLACK, i, xr, yr, 4*di/5, -9*di/25);
		    }
		    
		    int matrixXStart = XMStart;
		    for(int i = 1; i <= n; i++)
		    {
		    	g.setFont(fontLetter);
		    	g.drawString("A", matrixXStart, YStart + di);
		    	matrixXStart = matrixXStart + 12;
		    	g.setFont(fontNumber);
		    	g.drawString(String.valueOf(i), matrixXStart, YStart + di);
		    	matrixXStart = matrixXStart + 10;
		    	g.setFont(fontLetter);
		    	g.drawString(": " + p[i - 1] + "*" + p[i] + " ", matrixXStart, YStart + di);
		    	matrixXStart = matrixXStart + di * 3/2;
		    }
	    }
	}
	
	public class SynObj
	{
		String status = "0";
	}
	
	public class DrawCalculateRst extends JPanel implements Runnable
	{
		public void run() 
		{
			synchronized(so)
			{
			    so.status = "2";
			}
			matrixChainMul(d.getGraphics());
		}
	}
	
	public class PauseOrResume implements Runnable
	{

		public void run() 
		{
			while(true)
			{
				while(!awake)
				{
					try 
					{
						Thread.sleep(50);
					} 
					catch (InterruptedException e) 
					{
						e.printStackTrace();
					}
				}
				if(so.status.equals("1"))
				{
					if(change.getSelectedItem().toString().equals("1"))
					{
						interval = 1000;
					}
					else if(change.getSelectedItem().toString().equals("2"))
					{
						interval = 600;
					}
					else
					{
						interval = 200;
					}
					synchronized(so)
					{
					    so.status = "2";
					    so.notifyAll();
					}
				}
				else if(so.status.equals("2"))
				{
					so.status = "1";
				}
				awake = false;
			}
		}
		
	}
	
	//矩阵链乘法最优算序寻找算法
	public void matrixChainMul(Graphics g) 
	{
		long[][] m = new long[n + 1][n + 1];
		int[][] s = new int[n][n + 1];
		
		for(int i = 1; i <= n; i++)
		{
			m[i][i] = 0;
			int x = polygonArrayM[i][i].xpoints[0];
			int y = polygonArrayM[i][i].ypoints[0];
			
			setColorAndFill(g, Color.GREEN, polygonArrayM[i][i]);
			setColorAndDrawStr(g, Color.BLACK, m[i][i], x, y, 10, 5);
			sleepAndPossiblePause(interval);
		}
		
		for(int l = 2; l <= n; l++)
		{
			for(int i = 1; i <= n - l + 1; i++)
			{
				int j = i + l - 1;
				m[i][j] =  Integer.MAX_VALUE;
				int x = polygonArrayM[i][j].xpoints[0];
				int y = polygonArrayM[i][j].ypoints[0];
				int xs = polygonArrayS[i][j].xpoints[0];
				int ys = polygonArrayS[i][j].ypoints[0];
			    setColorAndFill(g, Color.YELLOW, polygonArrayM[i][j]);
			    setColorAndFill(g, Color.YELLOW, polygonArrayS[i][j]);
			    
			    sleepAndPossiblePause(interval);
			    
				for(int k = i; k <= j - 1; k++)
				{
					int x1 = polygonArrayM[i][k].xpoints[0];
					int y1 = polygonArrayM[i][k].ypoints[0];
					int x2 = polygonArrayM[k+1][j].xpoints[0];
					int y2 = polygonArrayM[k+1][j].ypoints[0];
				    setColorAndFill(g, Color.BLUE, polygonArrayM[i][k]);
				    setColorAndDrawStr(g, Color.BLACK, m[i][k], x1, y1, 10, 5);
				    setColorAndFill(g, Color.BLUE, polygonArrayM[k+1][j]);
					setColorAndDrawStr(g, Color.BLACK, m[k+1][j], x2, y2, 10, 5);
					long q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
					if(q < m[i][j])
					{
						m[i][j] = q;
						s[i][j] = k;
					}
					
					sleepAndPossiblePause(interval);
					
				    setColorAndFill(g, Color.GREEN, polygonArrayM[i][k]);
				    setColorAndDrawStr(g, Color.BLACK, m[i][k], x1, y1, 10, 5);
				    setColorAndFill(g, Color.GREEN, polygonArrayM[k+1][j]);
					setColorAndDrawStr(g, Color.BLACK, m[k+1][j], x2, y2, 10, 5);
				}
			    setColorAndFill(g, Color.GREEN, polygonArrayM[i][j]);
				setColorAndDrawStr(g, Color.BLACK, m[i][j], x, y, 10, 5);
				setColorAndFill(g, Color.GREEN, polygonArrayS[i][j]);
		        setColorAndDrawStr(g, Color.BLACK, s[i][j], xs, ys, 10, 5);
				
		        sleepAndPossiblePause(interval);
		    }
	    }
		
		
		g.drawString("最优的加括号的序列: ", rstStrXStart, YStart + di * 2);
		rstStrXStart = rstStrXStart + 120;
		printRstSequence(s, 1, n, g);
    }
	
	//打印加括号顺序
	public void printRstSequence(int[][] s, int i, int j, Graphics g)
	{
		if(i == j)
		{
			g.setFont(fontLetter);
			g.drawString("A", rstStrXStart, YStart + di * 2);
			rstStrXStart = rstStrXStart + di/4;
			g.setFont(fontNumber);
			g.drawString(String.valueOf(i), rstStrXStart, YStart + di * 2);
			rstStrXStart = rstStrXStart + di/4;
			System.out.print("A" + i + " ");
		}
		else
		{
			g.setFont(fontBracket);
			g.drawString("(", rstStrXStart, YStart + di * 2);
			rstStrXStart = rstStrXStart + di/4;
			System.out.print("(");
			printRstSequence(s, i, s[i][j], g);
			printRstSequence(s, s[i][j] + 1, j, g);
			g.setFont(fontBracket);
			g.drawString(")", rstStrXStart, YStart + di * 2);
			rstStrXStart = rstStrXStart + di/4;
			System.out.print(")");
		}
	}
	
	//睡眠并可能暂停
	private void sleepAndPossiblePause(int interval)
	{
		try
	    {
			Thread.sleep(interval);
			synchronized(so)
			{
				while(so.status.equals("1"))
			    {
					so.wait();
				}
			}
		}
		catch (InterruptedException e)
		{
			e.printStackTrace();
		}
	}

	private void setColorAndFill(Graphics g, Color c, Polygon p)
	{
		g.setColor(c);
	    g.fillPolygon(p);
	    g.setColor(Color.BLACK);
	    g.drawPolygon(p);
	}
	
	private void setColorAndDrawStr(Graphics g, Color c, Object value, int x, int y, int xDeviation, int yDeviation)
	{
		g.setColor(c);
		g.drawString(String.valueOf(value), x + xDeviation, y + yDeviation);
	}
	
	private static class FrameShower implements Runnable 
	{
		  
	    private final Frame frame;
	    
	    FrameShower(Frame frame) 
	    {
	      this.frame = frame;
	    }
	    
	    public void run() 
	    {
	     frame.setVisible(true);
	    }
	    
	}	
	
	public static void main(String[] args)
	{
		SwingUtilities.invokeLater(new Runnable()
		{
			public void run() 
			{
				//矩阵行列数组
				int[] p = {27, 33, 20, 18, 15, 18, 25};
				int di = 50;
				int n = p.length - 1;
				MatrixChainGUI c = new MatrixChainGUI(p, di);
				c.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
		        c.pack();
		        c.setSize(di * (2 * n + 2), di * (n+2)/2 + 200);
		        c.setResizable(false);
		        c.setTitle("矩阵链乘法的动态规划算法");
		        EventQueue.invokeLater(new FrameShower(c));
			}
		});
	}
}


main方法中的矩阵行列数组p决定矩阵个数

  • 大小: 20.4 KB
  • 大小: 22.2 KB
  • 大小: 20.5 KB
1
2
分享到:
评论
2 楼 xglv2013 2013-05-24  
bewithme 写道
实际中有啥用呢

个人感觉就是帮我们直观的看看算法工作的过程吧
1 楼 bewithme 2013-05-24  
实际中有啥用呢

相关推荐

    java实现银行家算法(Swing界面)

    Java 实现银行家算法(Swing 界面) 银行家算法是操作系统中非常重要的一种资源分配算法,用于避免死锁和饥饿的出现。下面我们将通过 Java 语言来实现银行家算法,并使用 Swing 库来设计一个友好的图形用户界面。 ...

    java swing 多选下拉框 支持动态加载数据

    Java Swing 是Java GUI(图形用户界面)库,用于构建桌面应用程序。在Swing中,多选下拉框通常由JComboBox类实现,但默认的JComboBox只支持单选。为了实现多选功能,我们需要扩展JComboBox或者使用第三方库,如JList...

    java Swing多Jpanel动态滑动切换效果

    java Swing多Jpanel仿安卓苹果桌面动态切换滑动效果

    Java Swing实现的生命游戏.zip

    Java Swing实现的生命游戏Java Swing实现的生命游戏Java Swing实现的生命游戏 Java Swing实现的生命游戏Java Swing实现的生命游戏Java Swing实现的生命游戏 Java Swing实现的生命游戏Java Swing实现的生命游戏Java ...

    Java Swing 组件全演示

    在设计Swing应用时,提前规划界面结构,使用适当的容器和布局管理器,以及合理的继承关系,可以提高代码的可读性和维护性。 总之,Java Swing组件全演示旨在通过实际项目引导学习者深入理解Swing组件的使用和界面...

    基于java swing实现答题系统

    基于Java Swing实现答题系统的技术要点 本文将详细介绍基于Java Swing实现答题系统的技术要点,涵盖了GUI设计、事件处理、swing组件使用、Java图形化编程等多个方面的知识点。 一、GUI设计 在本文中,我们使用了...

    Java 实现swing中嵌入html 实例 适合新手

    DJNativeSwing.jar是纯Swing实现,而DJNativeSwing-SWT.jar则利用了Eclipse的SWT库来增强功能,提供更好的渲染效果。 接下来,我们将探讨如何在Java项目中集成这些库。首先,将这两个JAR文件添加到项目的类路径中。...

    银行家算法JAVA代码实现,附带图形化界面

    4. **GUI.java**:图形化界面的实现,可能使用了Java Swing或JavaFX库,显示当前系统状态,如资源分配情况、进程状态等,并提供交互功能,如启动算法、模拟进程请求等。 5. **Util.java**:辅助工具类,可能包含一些...

    Java Swing 组件全演示源代码

    Java Swing 组件全演示源代码-Java Swing components entire demo source code

    java swing实现pdf阅读器

    在Java Swing中实现PDF阅读器是一项技术挑战,涉及到对PDF文件格式的理解、IO操作、Swing组件的使用以及可能的第三方库集成。 PDF(Portable Document Format)是一种广泛使用的文件格式,用于存储文档,包括文本...

    Java+Swing实现打飞机游戏

    Java+Swing实现打飞机游戏。Java+Swing实现打飞机游戏。Java+Swing实现打飞机游戏。Java+Swing实现打飞机游戏。Java+Swing实现打飞机游戏。Java+Swing实现打飞机游戏。Java+Swing实现打飞机游戏。Java+Swing实现打...

    java Swing Jtable 下拉动态加载数据

    JTable实现下拉动态加载数据,滑动动态加载数据,纯原生态java。

    java swing漂亮界面 超酷 javaswing教程

    在“Java Swing教程”中,我们会详细讲解如何使用这些组件、布局管理器、事件处理和外观定制,通过实例代码演示如何一步步构建出美观且功能丰富的应用程序。无论是初学者还是有一定经验的开发者,都能从中学习到如何...

    纯JAVA实现修改本地IP(swing界面版)

    总结起来,"纯JAVA实现修改本地IP(swing界面版)"项目涉及到了Java编程、Swing GUI设计、IP地址处理、文件I/O、事件处理、多线程以及错误处理等多个核心知识点。通过这个项目,开发者不仅可以提升Java编程技能,也能...

    java实现gif动画效果(java显示动态图片)

    在Java编程语言中,实现GIF动画效果实际上是对一系列静态图像进行定时切换,模拟出动态效果。本示例主要展示了如何在Java环境下显示动态图片,特别是GIF格式的动画。以下将详细介绍实现这一功能的关键步骤和相关知识...

    多边形填充算法java实现

    Java作为一种跨平台的编程语言,提供了丰富的库和API,如Java AWT(Abstract Window Toolkit)和Swing,用于创建图形用户界面,因此使用Java实现这样的算法对于学习和理解图形绘制非常有帮助。 在实际应用中,...

    基于Java swing组件实现简易计算器

    "基于Java swing组件实现简易计算器" 本文主要介绍了基于Java swing组件实现简易计算器的知识点,以下是相关知识点的总结: 1. JFrame组件:JFrame是Java swing组件中的一种顶层容器,用于创建一个窗口框架。通过...

    javaswing实现贪吃蛇源码

    java贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇javaswing实现贪吃蛇...

    JavaSwing实现简单计算器

    本项目"JavaSwing实现简单计算器"就是利用这些组件来创建一个功能基础的计算器应用,可以处理基本的数学运算,包括加、减、乘、除,同时也支持负数、小数以及括号的使用。下面我们将详细探讨实现这样一个计算器所需...

    java swing漂亮界面(超酷) javaswing教程

    Java Swing 是Java编程语言中用于构建桌面应用程序用户界面的一个库,它是Java Foundation Classes (JFC) 的一部分。Swing 提供了一系列组件,如按钮、文本框、菜单等,用于创建功能丰富的图形用户界面(GUI)。在...

Global site tag (gtag.js) - Google Analytics