概念
- 求解决策过程最优化的结果 (可能有多个)
- 把多阶段过程转化为一系列单阶段过程,利用各阶段之间的关系,逐个求解
- 计算过程中会把结果都记录下,最终结果在记录中找到.
举例
- 求两个字符串的最长公共子序列
- 字符串如下
x : bdcaba 纵坐标
y : abcbdab 横坐标
矩阵展示
| x/y | a | b | c | b | d | a | b |
|---|---|---|---|---|---|---|---|
| b | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| d | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
| c | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| a | 1 | 1 | 2 | 2 | 2 | 3 | 3 |
| b | 0 | 2 | 2 | 3 | 3 | 3 | 4 |
| a | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
填表公式:
image.png
php代码实现
/**
* php 实现动态规划 最长公共子序列LCS
*/
class LcsTest
{
private $xa;
private $ya;
private $max;
private $wayCount;
private $matrix;
private $indexs;
private $results;
private $moves;
public function lcs($x,$y){
//属性重置
$this->max = 0;
$this->wayCount = 0;
$this->matrix = [];
$this->indexs = [];
$this->results = [];
$this->moves = [];
//字符串拆分为数组
$this->xa = str_split($x);
$this->ya = str_split($y);
//1、生成矩阵
$this->createMatrix();
//1、输出矩阵页面到屏幕并且记录最优解的下标
$this->writeMatrix();
//3、获取所有可能走向
foreach($this->indexs as $index){
$data = $this->getWay($index['i'],$index['j'],$this->wayCount);
$this->wayCount++;
}
//4、输出结果
$this->writeResults();
}
/**
* 从后向前寻找可能走向
* @param integer $xlen
* @param integer $ylen
* @param integer $n
* @return
*/
private function getWay($xlen,$ylen,$n){
isset($this->results[$n]) || $this->results[$n] = [];
isset($this->moves[$n]) || $this->moves[$n] = [];
while ($xlen>=0&&$ylen>=0) {
if($this->xa[$xlen]==$this->ya[$ylen]){
//移动位置过程
$this->moves[$n][] = sprintf('%s:%s:%s:true',$this->xa[$xlen],$this->ya[$ylen],$this->matrix[$xlen][$ylen]);
//移动点数据
$this->results[$n][] = $this->xa[$xlen];
$xlen--;
$ylen--;
}
else{
//移动位置过程
$this->moves[$n][] = sprintf('%s:%s:%s:false',$this->xa[$xlen],$this->ya[$ylen],$this->matrix[$xlen][$ylen]);
if($this->matrix[$xlen-1][$ylen]>$this->matrix[$xlen][$ylen-1]){
$xlen--;
}
//如果相等证明2条路可走需要进行扩散
else if($this->matrix[$xlen-1][$ylen]==$this->matrix[$xlen][$ylen-1]){
$this->wayCount++;
//新开辟一条
$this->results[$this->wayCount] = $this->results[$n];
$this->getWay($xlen,$ylen-1,$this->wayCount);
//之前的继续走
$this->getWay($xlen-1,$ylen,$n);
break;
}
else{
$ylen--;
}
}
}
}
/**
* 生成矩阵
* @return
*/
private function createMatrix(){
foreach ($this->xa as $xi => $xv) {
foreach ($this->ya as $yi => $yv) {
if($xv==$yv){
$this->matrix[$xi][$yi] = $xi==0||$yi==0?1:$this->matrix[$xi-1][$yi-1]+1;
}
else {
$this->matrix[$xi][$yi] = $xi==0||$yi==0?0:max([$this->matrix[$xi-1][$yi],$this->matrix[$xi][$yi-1]]);
}
if($this->matrix[$xi][$yi]>$this->max){
$this->max = $this->matrix[$xi][$yi];
}
}
}
}
/**
* 输出矩阵到屏幕方便分析并且记录最优解所在坐标
* @return
*/
private function writeMatrix(){
echo '----------矩阵列表--------------',PHP_EOL,PHP_EOL;
echo " ",implode(" ",$this->ya),PHP_EOL;
foreach ($this->matrix as $ri => $rv) {
echo $this->xa[$ri]," ";
foreach ($rv as $rvi => $rvv) {
//取出所有的最优解
if($rvv == $this->max){
$this->indexs[] = [
'i' => $ri,
'j' => $rvi,
];
}
echo $rvv," ";
}
echo PHP_EOL;
}
}
/**
* 输出结果到屏幕方便对比
* @return
*/
private function writeResults(){
echo '----------移动过程--------------',PHP_EOL;
echo '格式 纵坐标:横坐标:层级:是否符合',PHP_EOL,PHP_EOL;
foreach ($this->moves as $move) {
if(empty($move)){
continue;
}
//输出从后向前找的过程 纵坐标：横坐标 : 层级
echo implode(" -> ",$move),PHP_EOL;
}
echo '----------最终结果--------',PHP_EOL;
foreach ($this->results as $result) {
if(empty($result)){
continue;
}
//得到的是逆序结果 反转数组后输出
$data = array_reverse($result);
echo implode(" ",$data),PHP_EOL;
}
}
}
$test = new LcsTest();
$test->lcs("bdcaba","abcbdab");
执行结果
----------矩阵列表--------------
a b c b d a b
b 0 1 0 1 0 0 1
d 0 1 1 1 2 2 2
c 0 1 2 2 2 2 2
a 1 1 2 2 2 3 3
b 0 2 2 3 3 3 4
a 1 2 2 3 3 4 4
----------移动过程--------------
格式 纵坐标:横坐标:层级:是否符合
b:b:4:true -> a:a:3:true -> c:d:2:false -> d:d:2:true -> b:b:1:true
c:b:2:false -> c:c:2:true -> d:b:1:false -> b:b:1:true
a:a:4:true -> b:d:3:false -> b:b:3:true -> a:c:2:false -> c:c:2:true -> d:b:1:false -> b:b:1:true
a:b:4:false -> b:b:4:true -> a:a:3:true -> c:d:2:false -> d:d:2:true -> b:b:1:true
a:a:4:true -> b:d:3:false -> b:b:3:true -> a:c:2:false -> c:c:2:true -> d:b:1:false -> b:b:1:true
c:b:2:false -> c:c:2:true -> d:b:1:false -> b:b:1:true
----------最终结果--------
b d a b
b c a b
b c b a
b d a b
b c b a
b c a b
总结分析
- 第一步主要生成列表
- 第一步主要获取最优解的最大长度 并且符合长度的下标都取出
- 第三步 根据所有最优解下标从后向左前方向一步一步走,哪里大走向哪里
- 重点部分 如果值相等说明出现2种情况 需要扩散第二条路 无限扩散
- 最终得到所有情况 输出即可
