optmatmult.java

java算法大全

import java.lang.*;
import java.awt.*;
import java.util.*;

class OptMatMult extends Object {
    int n;
    IntMatrix cost, best, dimMat;
    DrawingPanel drawingPanel;
    AlgAnimFrame frame;
    Dimension[] dims;

    static final int horizSpace = 66;
    static final int vertSpace = 19;
    
    /**
     * Dimension is used to represent the dimension of the matrices,
     * where the number of columns is represented by the 'width' attribute
     * and the number of rows is represented by the 'height' attribute from
     * java.awt.Dimension
     */
    public OptMatMult(Dimension[] dims, IntMatrix costMat, IntMatrix bestMat,
		DrawingPanel drawingPanel, AlgAnimFrame frame,
		IntMatrix dimMat ) {
	this.drawingPanel = drawingPanel;
	this.frame = frame;
	this.cost = costMat;
	this.best = bestMat;
	this.dimMat = dimMat;
	this.dims = dims;
	this.n = dims.length;
    }

    private int CostSubTree( int j, int k ) {
	int c;
	if ( (j<0) || (j>=k) || (j>=n) || (k>=n) )
	    c = 0;
	else {
	    c = cost.elem(j,k);
	}
	return c;
    }

/*-----------------------------------------------------------------------*/
    // Evaluate trees of size k
    public void matEvaluate( int numMat ) { /*-*/int line = 1;
	/*-*/frame.Highlight(line);
	int left, right, c_index, k, c, best_cost, best_index;

	// For matrix starting at 0, n-numMat
	/*-*/frame.Highlight(line + 4);
	for (left = 0; left < (n-numMat+1); left++) {
	    right = left+numMat-1;
	    /*-*/frame.Highlight(line + 5);
	    /*-*/ComBox com = highlightDimMat(left, right);
	    best_cost = cost.elem(left,right); // Best cost
	    /*-*/frame.Highlight(line + 6);
	    best_index = left;
	    /*-*/frame.Highlight(line + 7);
	    // If left tree has k nodes, right tree has numMat - k - 1
	    /*-*/DrawingObj[] objs, bestObjs = null;
	    /*-*/frame.Highlight(line + 9);
	    for (c_index = left; c_index < right; c_index++) {
		// Check each candidate index
		/*-*/frame.Highlight(line + 11);
		c = CostSubTree(left, c_index) + 
		    CostSubTree(c_index+1, right) +
		    dims[left].height * dims[c_index].width * 
			dims[right].width; 

		/*-*/objs = animateCost(left, c_index, right);
	    	/*-*/frame.Highlight(line + 16);
		if ( c < best_cost ) {
		    best_cost = c;
		    /*-*/frame.Highlight(line + 17);
		    best_index = c_index;
		    /*-*/frame.Highlight(line + 18);
		    /*-*/bestObjs = animateBest(objs, bestObjs);
		} /*-*/else animateRemoveObjs(objs);
	    }
	    /*-*/frame.Highlight(line + 20);

	    // Update the cost, best matrices
	    /*-*/frame.Highlight(line + 23);
	    /*-*/frame.Highlight(line + 24);
	    /*-*/animateStoreInMat(bestObjs, left, right, best_index);
	    best.setElem(left,right,best_index);
	    cost.setElem(left,right,best_cost);
	    /*-*/restoreDimMat(left, right, com);
    	}
	/*-*/frame.Highlight(line + 25);
    } // matEvaluate()

    public void start() { /*-*/int line = 28;
	/*-*/frame.Highlight(line);
	// Build all the sub-trees in turn
	/*-*/frame.Highlight(line + 3);
	/*-*/frame.Highlight(line + 4);
	/*-*/frame.Highlight(line + 5);
	for (int i = 0; i < n-1; i++)
	    cost.setElem(i, i+1,
		dims[i].height * dims[i].width * dims[i+1].width);
	/*-*/frame.Highlight(line + 6);
	/*-*/frame.Highlight(line + 7);
	for(int k=0;k<n-1;k++)
	    best.setElem( k, k+1, k );
	/*-*/animateInit();
	/*-*/frame.waitSkip();
	/*-*/frame.Highlight(line + 8);
	for( int k=3; k<=n; k++ ) {
	    /*-*/frame.Highlight(line + 9);
	    this.matEvaluate( k );
	    /*-*/frame.waitSkip();
	    /*-*/frame.Highlight(line + 10);
	}
	/*-*/frame.Highlight(line + 11);
	formBestParenthesisation();
	/*-*/frame.Highlight(line + 12);
    }
//----------------------------------------------------------------

    private Color darkGreen = new Color(0, 150, 0);
    private void animateInit() {
	ComBox com = new ComBox(420, 20, "Initialization...",
		drawingPanel.getFixFont());
	drawingPanel.addCom(com);
	drawingPanel.repaint(); drawingPanel.delay();

	ShadowLabel mesg1 = new ShadowLabel(
	   "There is only one possible way to multiply two");
	mesg1.setColor(darkGreen);
	mesg1.move(420, 70);
	drawingPanel.addDrawingObj(mesg1);
	drawingPanel.repaint(); drawingPanel.delay();drawingPanel.delay();

	ShadowLabel mesg2 = new ShadowLabel(
	   "matrices in order...");
	mesg2.setColor(darkGreen);
	mesg2.move(420, 90);
	drawingPanel.addDrawingObj(mesg2);
	drawingPanel.repaint(); drawingPanel.delay();drawingPanel.delay();

	ShadowLabel mesg3 = new ShadowLabel(
	   "The entries of the cost matrix are intialized.");
	mesg3.setColor(darkGreen);
	mesg3.move(420, 110);
	drawingPanel.addDrawingObj(mesg3);
	drawingPanel.repaint(); drawingPanel.delay();drawingPanel.delay();

	for (int i = 0; i < n-1; i++)
	    cost.setHighlight(i, i+1);
	drawingPanel.repaint(); drawingPanel.delay();
	for (int i = 0; i < n-1; i++)
	    cost.restoreHighlight(i, i+1);
	drawingPanel.repaint(); drawingPanel.delay();
	for (int i = 0; i < n-1; i++)
	    cost.setHighlight(i, i+1);
	drawingPanel.repaint(); drawingPanel.delay();
	for (int i = 0; i < n-1; i++)
	    cost.restoreHighlight(i, i+1);
	drawingPanel.repaint(); drawingPanel.delay();
	for (int i = 0; i < n-1; i++)
	    cost.setHighlight(i, i+1);
	drawingPanel.repaint(); drawingPanel.delay();
	for (int i = 0; i < n-1; i++)
	    cost.restoreHighlight(i, i+1);
	frame.waitStep();

	mesg1.setText(mesg2.getText()); mesg2.setText(mesg3.getText());
	mesg3.setText("For example, this entry is the cost for");
	drawingPanel.repaint(); drawingPanel.delay();drawingPanel.delay();
	mesg1.setText(mesg2.getText()); mesg2.setText(mesg3.getText());
	mesg3.setText("multiplying A0 and A1, which is the number");
	drawingPanel.repaint(); drawingPanel.delay();drawingPanel.delay();

	mesg1.setText(mesg2.getText()); mesg2.setText(mesg3.getText());
	mesg3.setText("of scalar multiplications during the matrix product.");
	drawingPanel.repaint(); drawingPanel.delay();drawingPanel.delay();

	FloatingBox fb = new FloatingBox("" + cost.elem(0, 1),
		drawingPanel.getFixFont());
	fb.move(cost.getPosn(0, 1).x, cost.getPosn(0, 1).y);
	drawingPanel.addDrawingObj(fb);
	drawingPanel.repaint(); drawingPanel.delay();
	Vector traj = new Vector();
	traj.addElement(new Point(fb.getX(), fb.getY()));
	traj.addElement(new Point(420, fb.getY()));
	traj.addElement(new Point(420, 130));
	drawingPanel.animate(fb, traj);

	ShadowLabel eq = new ShadowLabel("=");
	eq.setColor(darkGreen);
	eq.move(488, 142);
	drawingPanel.addDrawingObj(eq);
	drawingPanel.repaint(); drawingPanel.delay();

	FloatingBox fb2 = new FloatingBox("" + dims[0].height,
		drawingPanel.getFixFont());
	fb2.move(dimMat.getPosn(0, 0).x, dimMat.getPosn(0, 0).y);
	drawingPanel.addDrawingObj(fb2);
	drawingPanel.repaint(); drawingPanel.delay();
	traj = new Vector();
	traj.addElement(new Point(fb2.getX(), fb2.getY()));
	traj.addElement(new Point(500, fb2.getY()));
	traj.addElement(new Point(500, 130));
	drawingPanel.animate(fb2, traj);

	ShadowLabel mult1 = new ShadowLabel("*");
	mult1.setColor(darkGreen);
	mult1.move(568, 145);
	drawingPanel.addDrawingObj(mult1);
	drawingPanel.repaint(); drawingPanel.delay();

	FloatingBox fb3 = new FloatingBox("" + dims[0].width,
		drawingPanel.getFixFont());
	fb3.move(dimMat.getPosn(1, 0).x, dimMat.getPosn(1, 0).y);
	drawingPanel.addDrawingObj(fb3);
	drawingPanel.repaint(); drawingPanel.delay();
	traj = new Vector();
	traj.addElement(new Point(fb3.getX(), fb3.getY()));
	traj.addElement(new Point(580, fb3.getY()));
	traj.addElement(new Point(580, 130));
	drawingPanel.animate(fb3, traj);

	ShadowLabel mult2 = new ShadowLabel("*");
	mult2.setColor(darkGreen);
	mult2.move(648, 145);
	drawingPanel.addDrawingObj(mult2);
	drawingPanel.repaint(); drawingPanel.delay();

	FloatingBox fb4 = new FloatingBox("" + dims[1].width,
		drawingPanel.getFixFont());
	fb4.move(dimMat.getPosn(1, 1).x, dimMat.getPosn(1, 1).y);
	drawingPanel.addDrawingObj(fb4);
	drawingPanel.repaint(); drawingPanel.delay();
	traj = new Vector();
	traj.addElement(new Point(fb4.getX(), fb4.getY()));
	traj.addElement(new Point(660, fb4.getY()));
	traj.addElement(new Point(660, 130));
	drawingPanel.animate(fb4, traj);

	frame.waitStep();

	mesg1.setText(mesg2.getText()); mesg2.setText(mesg3.getText());
	mesg3.setText("The entries initialized in the best matrix");
	drawingPanel.repaint(); drawingPanel.delay();drawingPanel.delay();
	mesg1.setText(mesg2.getText()); mesg2.setText(mesg3.getText());
	mesg3.setText("are only the indices of the first matrices of");
	drawingPanel.repaint(); drawingPanel.delay();drawingPanel.delay();
	mesg1.setText(mesg2.getText()); mesg2.setText(mesg3.getText());
	mesg3.setText("the matrix-pair multiplications...");
	drawingPanel.repaint(); drawingPanel.delay();drawingPanel.delay();

	drawingPanel.removeObj(eq);
	drawingPanel.removeObj(mult1);
	drawingPanel.removeObj(mult2);
	drawingPanel.removeObj(fb);
	drawingPanel.removeObj(fb2);
	drawingPanel.removeObj(fb3);
	drawingPanel.removeObj(fb4);

	for (int i = 0; i < n-1; i++)
	    best.setHighlight(i, i+1);
	drawingPanel.repaint(); drawingPanel.delay();
	for (int i = 0; i < n-1; i++)
	    best.restoreHighlight(i, i+1);
	drawingPanel.repaint(); drawingPanel.delay();
	for (int i = 0; i < n-1; i++)
	    best.setHighlight(i, i+1);
	drawingPanel.repaint(); drawingPanel.delay();
	for (int i = 0; i < n-1; i++)
	    best.restoreHighlight(i, i+1);
	frame.waitStep();
	drawingPanel.repaint(); drawingPanel.delay();

	drawingPanel.removeCom(com);
	drawingPanel.removeObj(mesg1);
	drawingPanel.removeObj(mesg2);
	drawingPanel.removeObj(mesg3);
    } // animateInit()

    private ComBox highlightDimMat(int left, int right) {
	ComBox com = new ComBox(420, 20, "Finding optimal order for these " +
		(right - left + 1) + " matrices product..",
		drawingPanel.getFixFont());
	drawingPanel.addCom(com);
	for (int i = left; i < right+1; i++) {
	    dimMat.setHighlight(0, i);
	    dimMat.setHighlight(1, i);
	}
	drawingPanel.repaint(); drawingPanel.delay();
	return com;
    } // highlightDimMat()

    private void restoreDimMat(int left, int right, ComBox com) {
	for (int i = left; i < right+1; i++) {
	    dimMat.restoreHighlight(0, i);
	    dimMat.restoreHighlight(1, i);
	}
	drawingPanel.removeCom(com);
	frame.waitStep();
	drawingPanel.repaint(); drawingPanel.delay();
    } // restoreDimMat()

    private DrawingObj[] animateCost(int left, int c_index, int right) {
	DrawingObj[] objs = new DrawingObj[3];

	ComBox com = new ComBox(420, 70, "Checking this parenthesisation...",
		drawingPanel.getFixFont());
	drawingPanel.addCom(com);

	Subscript[] s1 = new Subscript[c_index-left+1];
	for (int i = left; i <= c_index; i++)
	    s1[i-left] = new Subscript("A", ""+i);
	Subscript[] s2 = new Subscript[right-c_index];
	for (int i = c_index+1; i <= right; i++)
	    s2[i-c_index-1] = new Subscript("A", ""+i);

	Parenthesis p1 = new Parenthesis(s1, drawingPanel.getFixFont());
	Parenthesis p2 = new Parenthesis(s2, drawingPanel.getFixFont());

	p1.move(450, 120); p2.move(p1.getRight(), 120);
	drawingPanel.addDrawingObj(p1);
	drawingPanel.addDrawingObj(p2);
	drawingPanel.repaint(); drawingPanel.delay();
	frame.waitStep();

	FloatingBox fb1 = null, fb2 = null;
	Parenthesis tmpL = null, tmpR = null;
	if (s1.length > 1) {
	    Subscript[] tmpS1 = new Subscript[c_index-left+1];
	    for (int i = left; i <= c_index; i++)
	    	tmpS1[i-left] = new Subscript("A", ""+i);
	    tmpL = new Parenthesis(tmpS1, drawingPanel.getFixFont());
	    
	    com.setText("The optimal cost for this obtained from cost matrix.");
	    DimIndicator d = new DimIndicator((p1.getX()+p1.getRight())/2,
		p1.getY() + 2, p1.getX(), p1.getRight(),
		"cost["+left+","+c_index+"]",
		drawingPanel.getFixFont());
	    drawingPanel.addDrawingObj(d);
	    drawingPanel.repaint(); drawingPanel.delay();

	    fb1 = new FloatingBox(""+cost.elem(left,c_index),
		drawingPanel.getFixFont());
	    Point p = cost.getPosn(left, c_index);
	    fb1.move(p.x, p.y);
	    drawingPanel.addDrawingObj(fb1);
	    drawingPanel.repaint(); drawingPanel.delay(); drawingPanel.delay();
	    Vector traj = new Vector();
	    traj.addElement(new Point(fb1.getX(), fb1.getY()));
	    traj.addElement(new Point(d.getX()-32, fb1.getY()));
	    traj.addElement(new Point(d.getX()-32, d.getY()+15));
	    drawingPanel.animate(fb1, traj);
	    frame.waitStep();

	    drawingPanel.removeObj(d);
	    traj = new Vector();
	    traj.addElement(new Point(fb1.getX(), fb1.getY()));
	    traj.addElement(new Point(p2.getRight() + 150, fb1.getY()));
	    drawingPanel.animate(fb1, traj);
	    tmpL.move(fb1.getX(), p1.getY());
	    drawingPanel.addDrawingObj(tmpL);
	    drawingPanel.repaint(); drawingPanel.delay();
	}

	if (s2.length > 1) {
	    Subscript[] tmpS2 = new Subscript[right-c_index];
	    for (int i = c_index+1; i <= right; i++)
	    	tmpS2[i-c_index-1] = new Subscript("A", ""+i);
	    tmpR = new Parenthesis(tmpS2, drawingPanel.getFixFont());

	    com.setText("The optimal cost for this obtained from cost matrix.");