基于有向图的装箱问题的算法研究

邓冬林¹，王海燕²，徐建华³

1. 云南农业大学基础与信息工程学院2. 云南财经大学统计与数学学院3. 昆明理工大学学生社区教育管理中心

摘 要：本文基于经典一维装箱问题进行深入研究.首先将装箱问题与有向图相结合,研究了无有向圈的有向图上的装箱问题以及基础圈有向图上的装箱问题,同时对这两个问题设计了相应的近似算法;其次,深化研究成果,将装箱问题同染色问题相结合,研究了无有向圈的有向图上的染色装箱问题以及基础圈有向图上的染色装箱问题,并对这两个问题分别设计了相应的近似算法和启发式算法.

关键词：有向图;装箱问题;染色装箱问题;FF算法;FFD算法;NP-完备性;