Re: [問題] 請問有關鋸木問題寫成程式比較快的方法
我寫了一段code, 不過只是單純的 recursive traversal而已,
還沒用上DP技巧. 所以時間複雜度為O(n!), 不過應有很大的改善空間.
這是用php寫的, 可以透過這個網址試run看看:
http://bobju.dyndns.org/cuts/form.html
因為只是要驗證程式邏輯而已, 所以很多防呆防弊機制都沒做, 預計時間
複雜度為O(n!), 所以測試資料請給小量就好, 大量的話恐怕會跑到掛. :P
若有錯誤, 敬請指教; 若無錯誤又有需要的話, 歡迎自行修改.
<?php
$MIN_COST=9999999;
$LENGTH=$_REQUEST['length'];
$nodes=explode(",",$_REQUEST['nodes']);
if(count($nodes)>7){
echo "節點超過7個, 恕不受理";
echo "<a href='http://bobju.dyndns.org/cuts/form.html'>返回</a>";
exit;
}
//定義節點串列結構:
//將所有節點由小到大依序排好, 並指定初值.
//每個節點有兩項屬性需要記錄: isCut為true, 代表此節點已被截取, isCut為false,
代表此節點尚未被截取.
//cost代表該節點被截取時所產生的成本, 初始值為0.
$list=array();
foreach($nodes as $n){
$list[$n]=array('isCut'=>false,'cost'=>0);
}
//用來記錄節點被截取的序列.
$ans=array();
//
traversal($list,1,$ans);
echo "最小總成本: $MIN_COST";
/* 以遞迴方式列舉所有節點被截取之順序的所有排列情形
* 在列舉的過程當中, 計算節點被截取時所產生的成本, 並記錄起來.
* list為pass by reference的方式傳入, 在遞迴過程中處理的都是同一份記錄.
* layer代表處理的層數, 同時也代表目前所處理的截點序數.
* ans用來記錄節點被截取的序列, 也是以pass by reference的方式由外部傳入.
*/
function traversal(&$list,$layer,&$ans){
//用來記錄所有traversal路徑中的最小總成本.
global $MIN_COST;
//對於list中的所有節點, 進行以下處理:
foreach($list as $k=>&$v){
//若此節點已被截取, 則略過.
if($v['isCut'])
continue;
//若此節點尚未被截取過, 則進行處理:
//計算截取成本:
$cost=count_cost($list,$k);
//將此截點記錄起來:
array_push($ans,array($k,$cost));
//若目前的處理層數已達到list的所有節點總數, 代表已形成一個完整的截點序列, 進
行以下處理:
if($layer==count($list)){
//將結果以特定格式輸出
echo nl2br(array_dump($ans,$tcost));
//記錄目前最小總成本
$MIN_COST=($tcost<$MIN_COST)?$tcost:$MIN_COST;
//輸出完畢後, 最近剛處理的截點狀態還原成未截取狀態.
$v['isCut']=false;
$v['cost']=0;
//將此截點的記錄彈掉.
array_pop($ans);
//返回
return;
}
//若目前處理層數尚未達到list的所有節點總數, 則:
else{
//將此節點標記為'截取'
$v['isCut']=true;
//繼續往下一層進行處理:
traversal($list,$layer+1,$ans);
//當下層都處理完返回時, 將此截點標記為'未截取'
$v['isCut']=false;
//將此截點的記錄彈掉.
array_pop($ans);
}
}
}
/* 輸出結果
*
*
*/
function array_dump($ans,&$tcost){
$output='';
$tcost=0;
foreach($ans as $v){
$output.=sprintf("(%d,%d)",$v[0],$v[1]);
$tcost+=$v[1];
}
$output.=sprintf(" cost:%5d\n",$tcost);
return $output;
}
/* 計算成本:
* 給予一個點座標$k, 計算此點向左(右)量測到最近截點(或邊界點)之間的距離和.
* $list記錄著所有節點目前的截取狀態及截取時所產生的成本.
*
*/
function count_cost(&$list,$k){
global $LENGTH;
$list[$k]['cost']=0;
$left_bound=0;
$i=$k-1;
while(!$list[$i]['isCut'] && $left_bound<$i){
$i--;
}
$list[$k]['cost']+=abs($k-$i);
$right_bound=$LENGTH;
$i=$k+1;
while(!$list[$i]['isCut'] && $i<$right_bound){
$i++;
}
$list[$k]['cost']+=abs($k-$i);
return $list[$k]['cost'];
}
?>
※ 引述《king19880326 (OK的啦～我都可以接受)》之銘言：
: ※ [本文轉錄自 C_and_CPP 看板]
: 作者: king19880326 (OK的啦～我都可以接受) 看板: C_and_CPP
: 標題: [問題] 請問有關鋸木問題寫成程式比較快的方法
: 時間: Mon Apr 27 08:51:15 2009
: 題目敘述如下
: 有一個木頭, 長度是 L, 假設位於座標 (0, L)中間, 現給 n 個點 p1, p2...pn
: 0 <= pi <= L (1 <= i <= n). 希望可以將原本的木頭切成這 n+1 段
: 現在定義切木頭的cost如下 : 如果木頭長度是 L1, 則切此木頭的 cost 就是L1
: (不論切在哪一個點). 試問該用何種順序才能使得切出這 n+1 段的 cost 為最小
: 舉例:
: 假設木頭位於 (0, 9) 要切的 3 個點 分別為 3, 4, 8
: 則如果由右往左切 cost 為 9(0 -> 9 中切 3 這個位置) + 6(3 -> 9中切 4 這
: 個位置) + 5(4 -> 9中切 8 這個位置) = 20
: 如果是由左往右切 cost 為 9(0 -> 9 中切 8 這個位置) + 8(0 -> 8中切 4 這
: 個位置 + 4(0 -> 4中切 3 這個位置) = 21
: 我的想法如下 :
: 定義 P(i,j) 為 (1 <= i <= n, 1 <= j <= n) 為 切第 i 刀時, 所切的位置在
: j 的 cost 最小.
: 以下是一個簡單的觀察 : min{P(n,1), P(P,2), ... P(n,n)} = 所求
: (因為共要切 n 刀, 而第 n-1 刀有可能是切在 p1, p2, ...pn 這 n 種可能)
: P(i, j) = min{P(i-1,1) + 切在 j 的代價, P(i-1, 2) 切在 j 的代價, ...P(i-1,n)
: + 切在 j 的代價} (令P(i-1,j) = 負無限大)
: P(1, j) = L (1 <= j <= n)
: 因此用 DP 填表格的方式 共 n * n 格要填
: 填每一格需要的時間複雜度 為 O(n)
: 所以時間複雜度是 O(n^3)
: 這樣的時間複雜度好像有點高 @@>, 請問有什麼方法可以把它的時間複雜度往下降嗎??
: 感謝感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.104.186.105
推
04/28 18:06, , 1F
04/28 18:06, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 3 篇)：