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

摘要

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