「セービング法」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: ''''【せーびんぐほう (saving method)】''' 運搬経路問題に対する古典的な近似解法であるが, 巡回セールスマン問題に対しても適用でき...')
 
 
(3人の利用者による、間の3版が非表示)
1行目: 1行目:
 
'''【せーびんぐほう (saving method)】'''
 
'''【せーびんぐほう (saving method)】'''
  
運搬経路問題に対する古典的な近似解法であるが, 巡回セールスマン問題に対しても適用できる. 前者の場合, 2点 $i,j$ 間の距離を $d_{ij}$ , デポ(depot)を点 $0$ と記す. 点 $0$ 以外の点 のペア $i,j$ に対して, セービング値 $s_{ij}$ $s_{ij} = d_{i0}+d_{0j}-d_{ij}$ と定義する. すべての点を通過する前に閉路ができたり, 点の次数が $2$ を超えないように, $s_{ij}$ の大きい順に枝 $(i,j)$ を加えていくことによって運搬経路を構築する.
+
運搬経路問題に対する古典的な近似解法. 2点 <math>i,j \,</math> 間の距離を <math>d_{ij} \,</math> , デポ(depot)を点 <math>0 \,</math> と記す. 点 <math>0 \,</math> 以外の点 のペア <math>i,j \,</math> に対して, セービング値 <math>s_{ij} \,</math> <math>s_{ij} = d_{i0}+d_{0j}-d_{ij} \,</math> と定義する. すべての点を通過する前に閉路ができたり, 点の次数が <math>2 \,</math> を超えないように, <math>s_{ij} \,</math> の大きい順に枝 <math>(i,j) \,</math> を加えていくことによって運搬経路を構築する.巡回セールスマン問題に対しても適用できる

2007年9月2日 (日) 18:49時点における最新版

【せーびんぐほう (saving method)】

運搬経路問題に対する古典的な近似解法. 2点 間の距離を , デポ(depot)を点 と記す. 点 以外の点 のペア に対して, セービング値 と定義する. すべての点を通過する前に閉路ができたり, 点の次数が を超えないように, の大きい順に枝 を加えていくことによって運搬経路を構築する.巡回セールスマン問題に対しても適用できる