如果我们愿意的话,我的一位教授给了我们一个在假日期间考虑的问题,而且我不确定解决问题的正确方法.
问题如下:我们有N条线(1≤N≤10^ 6)从A点到B点,但不知道哪条线末端对应于哪条线开始.有三种方法可以解决这个问题:
目标是计算A和B之间所需的最小旅行次数.
例如,对于3根电线,我们需要2次行程:我们连接两根电线并调用第三根电线A.然后我们前往另一点并测试哪根电线未连接到任何其他两根电线.这必须是电线A.然后我们将A与另一根电线连接,称之为B并返回.现在我们必须找到连接到A的电缆,这必须是B,第三个必须是C.
不幸的是,对于某些N来说,不可能弄清楚哪条线是哪条,例如N = 2.(我很确定N = 2是唯一的一条).N = 1表示零旅行.
任何关于如何处理这个问题的建议都非常感谢.