动态规划通用算法的java实现

谁说动态规则算法不能通用？我写了个通用算法，不知道能否通用，欢迎交流qq 15367481。

使用示例：

		
		//定义状态
		State a=new State("a"),
		b1=new State("b1"),
		b2=new State("b2"),
		b3=new State("b3"),
		c1=new State("c1"),
		c2=new State("c2"),
		c3=new State("c3"),
		d1=new State("d1"),
				d11=new State("d11"),
		d2=new State("d2"),
		e=new State("e");
		
		DynamicProgram prog=new DynamicProgram();
		//起点
		prog.start=a;
//		终点
		prog.end=e;
		
//		加入多阶段状态
		prog.addPhase(b1, b2);
		prog.addPhase(c1,c2,c3);
		prog.addPhase(d1,d11, d2);
		
//		加入状态转移时的决策
		prog.addDecision(a, b1,2);
		prog.addDecision(a, b2,5);
		prog.addDecision(a, b3,1);

		prog.addDecision(b1,c1,12 );
		prog.addDecision(b1,c2,14 );
		
		prog.addDecision(b2,c1,6 );
		prog.addDecision(b2,c2 ,10);
		prog.addDecision(b2,c3 ,4);
		
		prog.addDecision(b3,c1,10 );
		prog.addDecision(b3,c2 ,12);
		prog.addDecision(b3,c3 ,11);
		prog.addDecision( c1,d1,3);
		prog.addDecision( c1,d11,1);
		prog.addDecision( c1,d2,9);
		prog.addDecision( c2,d1,6);
		prog.addDecision( c2,d2,5);
		prog.addDecision( c3,d2,10);
		prog.addDecision(d1,e ,5);
		prog.addDecision(d11,e ,7);
		prog.addDecision( d2,e,2);
		
		//状态变量的比较，取优
		prog.chosePolicy=new Choose() {
			
			@Override
			public int compare(Object newStateVal,Object oldStateVal) {
//				本示例中，最短路问题，找总距离小的
				int oldV = ((Integer)oldStateVal).intValue();
				int newV = ((Integer)newStateVal).intValue();
				if(oldV==newV)
					return 0;
				else if(newV<oldV)
					return 1;
				else return -1;
			}
			
			@Override
			public Object getStateVal(Decision decision) { 
//				本示例中，总距离=上次距离+这次决策的距离
				int stateVal = ((Integer)decision.from.stateVal ).intValue();
				int cost = ((Integer)decision.cost).intValue();
				return stateVal+ cost;
			}
		};
		
		//求解
		prog.start();
		
		//打印路径
		System.out.println("最小费用示例，找到2个最优的策略：");
		System.out.println(e.stateVal);
		//最优策略集合
		HashSet<LinkedList<State>> strategies = new HashSet<LinkedList<State>>();
		prog.getStrategyState(strategies,new LinkedList<State>(),e);
		for(LinkedList<State> strategy:strategies){
//			打印所有策略
			System.out.println(strategy);
			System.out.println(prog.getStrategyPath(strategy));
		}
	
		System.out.println("\n最优路径中的子路径也是最优的：\n"+d1.stateVal);
		 strategies = new HashSet<LinkedList<State>>();
		prog.getStrategyState(strategies,new LinkedList<State>(),d1);
		for(LinkedList<State> strategy:strategies){
			System.out.println(strategy);
			System.out.println(prog.getStrategyPath(strategy));
		}

 

 运行结果：

 

最小费用示例，找到2个最优的策略：
19
[a, b2, c1, d1, e]
[a->b2:5, b2->c1:6, c1->d1:3, d1->e:5]
[a, b2, c1, d11, e]
[a->b2:5, b2->c1:6, c1->d11:1, d11->e:7]

最优路径中的子路径也是最优的：
14
[a, b2, c1, d1]
[a->b2:5, b2->c1:6, c1->d1:3]