一种基于线段相交排除方法的二维欧几里得坐标系下旅行商最短路径近似
2022-03-17 本文已影响0人
寽虎非虫003
实现步骤
step 1.对所有点生成一个二叉树,按照先后的优先级。
step 2.从根节点开始,按先序递归访问每一个节点,在每一个节点第一次被访问的时候,输出该节点到路线。
step 3.将step2中所有节点按顺序连接访问路线,若任意两条路线相交,则将这两条路线取消,重新尝试相关节点的不同的连线方法,直到没有任意两条直线相交。
特别说明
对于非欧的,非二维的无向图或有向图,可能不适用。