两组N人可以围绕一圈找到对方吗？

Question

这是一个算法问题,我不确定它是否有解决方案.我认为这是一个更通用的计算机科学问题的具体案例,没有解决方案,但我宁愿不披露哪一个避免种植偏见.它来自现实生活中的情况,其中手机没有信用,因此,我们没有远程通信.

两组人,每人有2人(但可能适用于N人)安排在公园中心见面,但在会议时,公园关闭.现在,他们将不得不在公园周围的其他地方见面.是否有一个算法,每个人都可以遵循以在一个点汇合所有？

例如,如果每个小组分成两个并四处走动,当他们发现另一个人继续跟那个人一起时,他们都会聚集在公园的另一边.但是,如果另一组做同样的事情,那么他们将无法将其他组的成员带到他们身边.这不是一个可能的解决方案.

我不确定我是否解释得很好.我可以尝试绘制图表.

Answer 1

确定性的解决方案 N > 1, K > 1

适用N于K每个人群.

由于问题是基于手机信用不足的人,我们假设每组中的每个人都有自己的手机.如果这是不可接受的,那么用电话卡,社会保障,驾驶执照或任何其他具有保证唯一的数字标识的项目代替电话.

在每个组中,每个人必须记住该组中最高的数字,并且具有最高编号(标记leader)的人必须顺时针绕周边行进,而其他人保持放置.

在leader每个小组遇到下一组之后,他们将他们的号码与小组的前一个leader号码进行比较.

如果领导者的数量高于该组织的前一个领导者的数量,那么领导者和小组都将继续沿着公园的周边.如果该组织的前一个领导者的数量更高,那么他们都会保持不变.

最终,leader具有最高数字的数字将在整个周长内完全旋转1圈,收集整个组.

确定性解决方案N > 1, K = 1(事先有一个合理的知识假设)

在这种情况下,每个组只包含一个人.我们假设使用的号码是电话号码,因为假设至少有一对人知道对方的号码是合理的,因此其中一个人会保持不变.

因为N = 2,这变得简单地减少到一个人留下来,另一个人顺时针走动.

对于其他情况,事实上,至少有两个人最初知道对方的号码将最大有效地提高K到至少2(因为谁留在原地的人或人将继续留在原地,如果他们知道这个人有一个较大的数字比该leader谁显示,以满足它们),但我们还是要引入一个新的一步算法,以确保它会终止.

额外的一步是,如果a leader在周围继续进行一次旋转而没有向组中添加任何人,则leader必须将他们的组留在后面并重新开始围绕周界旋转一圈.这意味着leader没有团体的人将无限期地继续,直到他们找到其他人,这是好的.

有了这个额外的步骤,很容易明白为什么我们必须假设,至少有一对的人需要提前知道对方的电话号码,因为那样的话,我们可以保证,谁原地踏步的人最终会积累整个组.

如果您认为我错过了边缘案例,请随意留下评论或建议以改进我已经列出的算法或挑战我.如果没有,那么我希望你喜欢我的回答.

更新

为了好玩,我决定用这个问题写一个关于我的问题解决方案的视觉演示d3.随意使用参数并在任何初始状态下重新启动模拟.这是链接:

https://jsfiddle.net/patrob10114/c3d478ty/show/

键

• 黑人 - 领导者
• 白人 - 追随者
• 点击时
  • 蓝色 - 选定的人
  • 绿色 - 被选定的人所知
  • 红色 - 被选中的人所知

请注意,这collaboration发生在每个开始时step,因此如果在当前步骤中刚刚合并了两个组,则大多数人在step调用下一个组之后才会知道来自相反组的人员.

Answer 2

他们应该走向公园的最北端.

Answer 3

我会随机向两个小组发送信息.如果他们在没有遇到另一组的情况下进行了半圈,则重新随机化指示.这将使他们在大多数时间内在几轮中相遇,但是他们仍然永远不会遇到的可能性非常小.

Answer 4

它是不可能有确定性的算法,如果

• •我们必须在周边的某个地方相遇,
• •我们无法区分周边的点(或者算法不允许使用这种区别),
• •我们无法区分群体中的个体(或者不允许算法使用这种区别),
• •周长是圆形的(更常见的情况见下文),
• •我们都遵循相同的算法,并且
• •初始点可能位于周边的任何位置.

证明:使用确定性算法,我们可以从初始位置推导出最终位置,但是这些组可以围绕周边均匀地间隔开始,在这种情况下问题具有旋转对称性,因此解决方案将保持1/n旋转不变,但是在外围没有固定点.

假设的状态 正如其他人已经观察到各种解决方案一样,各种假设下降导致:

• 非确定性:正如其他人所观察到的那样,各种非确定性算法确实提供了一种解决方案,当时间趋于无穷大时,终止概率趋于确定; 我怀疑几乎任何随机游走都会.(很多答案)
• 点数无法区分:如果需要,就达成一个固定点达成一致:flyx的回答.
• 个体难以区分:如果存在完美的哈希算法,请选择具有最低哈希值的哈希算法来收集其他哈希算法:Patrick Roberts的解决方案.
• 相同的算法:提前选择一个来收集其他算法(适应Patrick Roberts的解决方案).

其他假设可能会被削弱:

• 非圆形周长:周长为圆形的条件相当人为,但如果周长在拓扑上等效于圆,则此等效可用于将任何解决方案转换为圆问题的解.
• 无限制的初始点:即使初始点不能均匀分布,只要某些点不同,拓扑等价(如非圆形周长)就会减少解决圆形案例的解决方案,表明没有解决方案可以存在.

我认为这个问题确实属于计算机科学堆栈交换.

Answer 5

这个问题在很大程度上取决于我们拥有什么样的操作以及您认为您的环境是什么样的.我问你这个问题没有回复,所以这是我的解释:

公园是一个2d空间,2组随机,每组有相同的右/左(都面向公园).两者都有相同的操作编程完成相同的事情(没有像我走的那样,你走左边,因为这使得问题显而易见).所以操作是:向右/向左/停止x单位时间.他们还可以发现他们通过了原来的位置(他们开始的位置).它们可以循环编程.

如果你有能力使用随机性 - 一切都很简单.你可以提出很多解决方案.例如:概率为0.5,他们每个人都决定他们要么做3步并等待.或者一步吧,等一下.如果您将在循环中执行此操作并且他们将选择不同的选项,那么显然他们将会遇到(一个比另一个快,所以他将达到一个较慢的人).如果它们都选择相同的操作,那么它们将形成一个圆圈并且两者都达到它们的起始位置.在这种情况下,掷骰子一次.N圈后,他们将遇到的概率为1 - 0.5 ^ n(非常接近1)