[發明專利]一種基于等高線思維的哈密頓路徑求解方法

在審

• 申請號: 202011245037.2
• 申請日: 2020-11-10
• 公開（公告）號: CN112347312A
• 公開（公告）日: 2021-02-09
• 發明（設計）人: 魏金占;朱留存;陳進;盧玉南;錢偉文;陸韋春;黃曉生
• 申請（專利權）人: 北部灣大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/909
• 代理公司: 廣西中知科創知識產權代理有限公司 45130
• 代理人: 吳震輝

1.一種基于等高線思維的哈密頓路徑求解方法，其特征在于，包括以下步驟：

S1、獲取節點樣本數據；

S2、構建節點樣本的外包圖形，以將所有節點覆蓋在外包圖形中；

S3、分別以每一節點為中心構建泰森多邊形，形成泰森多邊形網，并將外包圖形的邊線作為泰森多邊形網的邊界線；

S4、以邊界線為基準，搜索與邊界線鄰接的泰森多邊形，并將搜索結果合并得到泰森多邊形環；

S5、搜索與泰森多邊形環鄰接的泰森多邊形，并將搜索結果合并得到新的泰森多邊形環；

S6、重復S5中的搜索步驟，直至搜索結果覆蓋所有的泰森多邊形，以得到若干泰森多邊形環；

S7、以其中一泰森多邊形環中的任一節點為起始點，依次連接該泰森多邊形環內的所有節點，并將最后一個連接的節點與相鄰的另一泰森多邊形環內的節點相連；

S8、重復S7中的連接步驟，直至將所有泰森多邊形環內的節點依次連接，以及相鄰的泰森多邊形環連接，結果即為哈密頓路徑的解。

2.根據權利要求1所述的一種基于等高線思維的哈密頓路徑求解方法，其特征在于，所述外包圖形為矩形或者圓形。

3.根據權利要求2所述的一種基于等高線思維的哈密頓路徑求解方法，其特征在于，所述外包圖形大于最小外包圖形，以使得所有的節點樣本未落在外包圖形的邊線上。

4.根據權利要求1所述的一種基于等高線思維的哈密頓路徑求解方法，其特征在于，所述步驟S7中，以最外圍的泰森多邊形環中的任一節點作為起始點。

5.根據權利要求1所述的一種基于等高線思維的哈密頓路徑求解方法，其特征在于，所述步驟S7中，同一泰森多邊形環中的節點在連接時，依次連接相鄰的節點。

6.根據權利要求5所述的一種基于等高線思維的哈密頓路徑求解方法，其特征在于，所述步驟S7中，若其中一節點與多個節點相鄰，將所述其中一節點與任一相鄰的節點進行連接。

7.根據權利要求1所述的一種基于等高線思維的哈密頓路徑求解方法，其特征在于，所述步驟S7中，其中一泰森多邊形環的最后一個連接的節點與相鄰的另一多邊形環中相鄰的任一節點連接。

8.根據權利要求1至7任一所述的一種基于等高線思維的哈密頓路徑求解方法，其特征在于，所述求解方法用于平面求解。