巡回セールスマン問題のL-システムによる近似解

摘要

L-システムとは、単純な規則から複雑な形状を生成することが可能な形式文法である[1]。特定の形状を生成するために確率的0L-システムなどが研究されている[2]。また、生成だけでなく死滅も規則に組み込hだ拡張L-システムが提案されており、パラメータの制御により空間的な複雑さの異なる形状の生成を可能としている[3]。そこで本研究では、死滅を組み込hだ拡張L-システムをベースとして巡回セールスマン問題の近似解を求めるL-システムを提案した。