图中描述的8x9网格图是欧拉图,用编织算法求解,该算法仅在N和M是相对素数的情况下才能工作。可以使用像Hierholzer这样的一般算法,但它的正则性意味着存在一个确定性算法来遍历图的(2N+1) x (2M +1)。我很难找到这个算法,但我确信它就在那里。
这个问题的动机是用3D打印机连续挤压,依靠欧拉电路一次和一次遍历图的所有边缘,这对于在塑料、粘土或水泥中创建强大的结构是可取的。

发布于 2021-12-22 17:05:18
我得到的解决方案是稍微修改Hierholzer算法。不要随机选择下一个相邻的顶点,如果可能的话,选择位于相同对角线方向的顶点。这意味着在算法进行时,用对角线方向的代码对每条边进行加权,并保持该方向。邻接结构是一组加权边的列表。
https://stackoverflow.com/questions/70402749
复制相似问题