摘要
在實際空間中，直接求解路徑問題的困難度相當高，因而衍生出將路徑投射在網格的圖形上，以網格圖(Mesh)的圖形表示法來探討路徑最佳化的問題。網格圖為最原始的圖形表示法，造成許多研究論文以網格圖為出發點，將實際空間的結構加以簡化，以求取路徑問題的最佳解。 在三度空間中找出一條最佳路徑的問題是近代許多研究學者致力專精研究的主題，如：郵差問題(CPP)與旅行推銷員問題(TSP)等等，皆屬NP-complete的路徑問題，隨著節點數(vertices)越多，求解的困難度也越高。許多學者將實際的路徑問題簡化為2D的網格圖，試以所提之演算法求解，但求解前須判斷路徑是否有解，這方面一直是學者忽略的重點。 本論文研究可分為兩大部分，分別為：(1)矩形網格圖是否有漢米爾頓路徑；以及(2)劃分矩形網格圖成為2×2、2×3、3×2與3×3之基本單元的基本網格圖中是否有漢米爾頓路徑。上述兩個問題皆未有文獻探究。有鑑於此，本研究先後針對該兩項議題提出證明，爾後對其未來延展性詳加敘述，以利於對路徑問題有更深入的探討。
並列摘要
The essence of this thesis is to study the Hamiltonian path over a given mesh graph. The problem of solving Hamiltonian path is known as an NP-complete problem, and it is hard to handle in mathematics. The mesh is a special type of graph. All the edge of a mesh have the same length that locate along either the horizontal or the vertical directions. The rectangular mesh graphs are divided into the basic graphs in this thesis that include 2×2、2×3、3×2 and 3×3 subgraphs. The point of this research is to prove that a Hamiltonian path exists over the rectangular mesh graph that is a combination of the basic mesh graphs.