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

提供: ORWiki
ナビゲーションに移動 検索に移動
("セービング法" を保護しました。 [edit=sysop:move=sysop])
(相違点なし)

2007年7月20日 (金) 11:33時点における版

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

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