今天我遇到了一个我无法解决的问题。
经常旅行的人收齐了他所有的旅行机票。票证只有两个属性,起点位置名称和目的地名称。例如从德里到纽约。在一年结束的时候,旅行者把他所有的票都集中在一起,试图绘制出他一年中的旅程。以可读的格式打印他可能的旅行路线。他不记得他的起点位置了。他可以多次访问一个位置,也可以多次来回访问一个地方。最初,我认为可以通过制作一个图(ticket-A to B意味着有向边A->B)并使用从索引为0(??)
图中描述的8x9网格图是欧拉图,用编织算法求解,该算法仅在N和M是相对素数的情况下才能工作。可以使用像Hierholzer这样的一般算法,但它的正则性意味着存在一个确定性算法来遍历图的(2N+1) x (2M +1)。我很难找到这个算法,但我确信它就在那里。这个问题的动机是用3D打印机连续挤压,依靠欧拉电路一次和一次遍历图的所有