概念
- 求解決策過程最優(yōu)化的結(jié)果 (可能有多個(gè))
- 把多階段過程轉(zhuǎn)化為一系列單階段過程,利用各階段之間的關(guān)系,逐個(gè)求解
- 計(jì)算過程中會(huì)把結(jié)果都記錄下,最終結(jié)果在記錄中找到.
舉例
- 求兩個(gè)字符串的最長公共子序列
- 字符串如下
x : bdcaba 縱坐標(biāo)
y : abcbdab 橫坐標(biāo)
矩陣展示
| 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代碼實(shí)現(xiàn)
/**
* php 實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃 最長公共子序列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 = [];
//字符串拆分為數(shù)組
$this->xa = str_split($x);
$this->ya = str_split($y);
//1旗国、生成矩陣
$this->createMatrix();
//1鸵膏、輸出矩陣頁面到屏幕并且記錄最優(yōu)解的下標(biāo)
$this->writeMatrix();
//3具篇、獲取所有可能走向
foreach($this->indexs as $index){
$data = $this->getWay($index['i'],$index['j'],$this->wayCount);
$this->wayCount++;
}
//4、輸出結(jié)果
$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]){
//移動(dòng)位置過程
$this->moves[$n][] = sprintf('%s:%s:%s:true',$this->xa[$xlen],$this->ya[$ylen],$this->matrix[$xlen][$ylen]);
//移動(dòng)點(diǎn)數(shù)據(jù)
$this->results[$n][] = $this->xa[$xlen];
$xlen--;
$ylen--;
}
else{
//移動(dòng)位置過程
$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條路可走需要進(jìn)行擴(kuò)散
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);
//之前的繼續(xù)走
$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];
}
}
}
}
/**
* 輸出矩陣到屏幕方便分析并且記錄最優(yōu)解所在坐標(biāo)
* @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) {
//取出所有的最優(yōu)解
if($rvv == $this->max){
$this->indexs[] = [
'i' => $ri,
'j' => $rvi,
];
}
echo $rvv," ";
}
echo PHP_EOL;
}
}
/**
* 輸出結(jié)果到屏幕方便對(duì)比
* @return
*/
private function writeResults(){
echo '----------移動(dòng)過程--------------',PHP_EOL;
echo '格式 縱坐標(biāo):橫坐標(biāo):層級(jí):是否符合',PHP_EOL,PHP_EOL;
foreach ($this->moves as $move) {
if(empty($move)){
continue;
}
//輸出從后向前找的過程 縱坐標(biāo)：橫坐標(biāo) : 層級(jí)
echo implode(" -> ",$move),PHP_EOL;
}
echo '----------最終結(jié)果--------',PHP_EOL;
foreach ($this->results as $result) {
if(empty($result)){
continue;
}
//得到的是逆序結(jié)果 反轉(zhuǎn)數(shù)組后輸出
$data = array_reverse($result);
echo implode(" ",$data),PHP_EOL;
}
}
}
$test = new LcsTest();
$test->lcs("bdcaba","abcbdab");
執(zhí)行結(jié)果
----------矩陣列表--------------
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
----------移動(dòng)過程--------------
格式 縱坐標(biāo):橫坐標(biāo):層級(jí):是否符合
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
----------最終結(jié)果--------
b d a b
b c a b
b c b a
b d a b
b c b a
b c a b
總結(jié)分析
- 第一步主要生成列表
- 第一步主要獲取最優(yōu)解的最大長度 并且符合長度的下標(biāo)都取出
- 第三步 根據(jù)所有最優(yōu)解下標(biāo)從后向左前方向一步一步走,哪里大走向哪里
- 重點(diǎn)部分 如果值相等說明出現(xiàn)2種情況 需要擴(kuò)散第二條路 無限擴(kuò)散
- 最終得到所有情況 輸出即可
