解铃还需系铃人 —— 请把绳子理顺


(Creative Commons. Some rights reserved. Thomas Good)






这个竞赛的灵感来自于Planarity游戏。它同时也来自于生活中的实际问题:如何快速地把绳子的“死结”打开(Gordian knot )。比如说:给你一个打了很多结的绳子(如毛线团),你能快速把它理顺么?

用数学术语可以这样来描述:在一个平面坐标系里,给一组可能有交叉的线段,通过移动线段的端点,使这些线段不再交叉。用下图这个动画可以清楚说明问题:

竞赛题目详述

先从一组有交叉的线段(绳子)开始,如下图所示,交叉的地方我们称之为”结“(注:在本文中,“结”等于交叉点)。

我们不希望绳子里有“结”,因为每一个“结”都有可能增加把绳子理顺的负担。所以我们希望能把这些“结”去掉。但是不能简单地用剪刀把“结”剪断。我们可以做的,就是通过移动(绳子)线段的端点(两端),直到线段(绳子)里含有最少的交叉点(“结”),如下图所示:

现在看起来简洁多了。在整个过程中,我们也付出了时间精力来移动线段的端点。所以这个竞赛的目的是:在尽可能减少移动端点的情况下,使线段交叉点的数目最少。

其他注意事项

最重要的考虑因素是得到最少的交叉点,那么一个近似的表达得分的方式为:

 Score = nKnots 
 注明: nKnots表示交叉点的个数。建议大家看一下下文的范例,范例里有更直观的表述。

在交叉点数目同样的情况下,那么我们考虑谁付出的时间精力最少。可以通过以下表达式来表示移动端点所付出的时间精力:

 sum(dist .* wts) / (max_dist*sum(wts))
 注明:dist表示每个端点所移动的距离,wts表示移动每个端点需要付出的单位权重,max_dist表示原始图中最远的2个端点之间的距离,sum(wts)是所有单位权重之和。

那么,总的得分标准如下:

 Score = nKnots + sum(dist .* wts) / (max_dis*sum(wts))
  • 端点的坐标都是整数。
  • 有可能不能获得没有任何交叉点的结果。
  • 一个坐标位置不可以含有多个端点。
  • 如果有端点坐落在其他线段上,那么认为此线段上有两个新的交叉点。

函数格式

请把你的函数命名为solver.m,并且可以通过以下方式调用:

 [xyOut] = solver(a, xyIn, wts)

端点的坐标用n x 2的矩阵xyIn表示,矩阵里每一行的两个数字表示该端点的坐标(x,y)。矩阵a表示端点之间的连接关系(1表示两个端点有连接,0表示没有)。因为线段是没有方向的。所以说矩阵a肯定是对称的。权重向量wts表示移动每个端点需要付出的单位权重。输出矩阵xyOut是端点移动后的位置坐标,与xyIn的端点一一对应。假设你没有移动任何端点,那么xyOut(n,:) = xyIn(n,:)。

范例

如下图所示,我们有5个端点,有2个交叉点:

用MATLAB语句,可以表达为:

 xyIn = [ 1 5;
         1 2;
         3 1;
         5 2;
         5 5]
 a = [ 0 1 1 0 0;
       1 0 0 1 0;
       1 0 0 0 1;
       0 1 0 0 1;
       0 0 1 1 0]
 wts = [1 4 2 1 2]

当然,根据以上数据,我们也可以使用MATLAB自带的gplot函数来画图,得到一个很直观的图形:

>> gplot(a,xyIn,'o-')

这里有两个重要的参数, 分别是移动每个端点所需要付出的单位权重之和,以及原图中任意两个端点之间的最长距离:

 sum(wts) = 1 + 4 + 2 + 1 + 2 = 10
 max_dist = 断点1和4之间的距离 = sqrt( (5-1)^2 + (2-5)^2 ) = sqrt( 16 + 9 ) = 5

我们看一下以下三种方案里,哪一种方案是最好的。当然,我们先看一下不做任何移动的结果。不做任何移动,那么每个端点所对应的移动距离为[0 0 0 0 0],但是图中有2个交叉点,所以得分结果为:

 dist = [0 0 0 0 0]
 wts  = [1 4 2 1 2]
 scoreA = knots + sum(dist .* wts)/(max_dist*sum(wts)) = 2 + 0/(5*10) = 2

方案A:

在这个方案里,我们把第三个端点向上移动2个位置。如果只移动1个位置的话,那么没有什么意义,因为端点3将会落在一条线段上,又产生了两个交叉点。向上移动2个位置,结果如下:

 dist = [0 0 2 0 0] 
 wts = [1 4 2 1 2] 
 scoreA = knots + sum(dist .* wts)/(max_dist*sum(wts)) = 0 + 4/(5*10) = 0.08

方案B:

在这个方案里,我们把第三个端点向左移动3个位置,这将减少一个交叉点,但是仍然有一个交叉点留下:

 dist = [0 0 3 0 0]
 wts  = [1 4 2 1 2]
 scoreB = knots + sum(dist .* wts)/(max_dist*sum(wts)) = 1 + 6/(5*10) = 1.12

方案C:

把端点4先向下移动2个位置,再向左移动2个位置:

 dist = [0 0 0 sqrt(8) 0]
 wts  = [1 4 2 1 2]
 scoreC = knots + sum(dist .* wts)/(max_dist*sum(wts)) = 0 + sqrt(8)/(5*10) = 0.0566

这是几个方案里最好的方案,你能想到更好的办法?

竞赛准备

若想参加此次竞赛,请按照以下步骤进行:

  • 下载竞赛使用的相关zip文件 (查看 资源区里的链接)。
  • 解压文件。
  • 根据上文提到的语法,写出算法 solver.m函数
  • 使用解压文件里的 runcontest.m 函数来测试你的算法。
  • 
     >> runcontest
    
    

评分

你的总分受以下几个因素影响,其中第一个和第二个因素的分量比较重,第三、四个因素所占分量比较轻。

  1. 对于不同的测试案例,你的算法的平均得分
  2. 你算法运行的快慢
  3. 你算法的圈复杂度 (见下面解释)
  4. 你算法的Node count(见下面解释)

圈复杂度

圈复杂度是一种代码复杂度的衡量标准(参考资料)。就是说在你所提交的程序文件(如m文件)里,可能包含多种可以独立运行的路径。当路径变得很多以后,将会给程序调试带来很多困难,因为程序员很难跟踪程序到底运行到哪里了。

由于一个程序文件可能含有多个函数,那么每个函数都有可能含有几种可独立运行的路径。因此,在一个文件的所有函数里,含有独立运行路径最多的函数的路径数目称之为该程序文件的圈复杂度。

在MATLAB里,我们可以轻易获得m函数的圈复杂度。试一下以下命令:

>> checkcode -cyc magic.m

Node count

这是用来衡量你代码的长短。注释语句多少和变量名称的长短不影响程序长短的判定。

MATLA提供以下命令来帮助你获得程序的长度:

 t = mtree(filename,'-file');
 length(t.nodesize)

程序运行时间和程序长短上限

为了保证参赛者都能顺利提交文件,我们对你的文件有如下限制:

  • 文件提交次数的限制
    每15分钟,你最多只能提交5个文件,平均每三分钟一个文件。请不要创建多个帐号来提交作品,一旦被我们发现,我们将取消你所提交的作品。

  • 程序运行时间
    如果你的程序运行时间超过180秒,那么你的程序将会被淘汰。

  • 文件大小
    程序长度不能超过65535个字节,超过此限制将会导致文件上传不成功。

协作和代码修改

一旦一个程序被提交,该程序将不能被改动。当然,你可以查看和修改,然后重新提交一个新程序。你可以随意阅读别人的程序。如果你通过修改别人程序而得到更好的结果,那么你将会是修改后的程序的”作者“。

同时,我们也鼓励你多与别人交流。 请参考 资源区 的讨论组信息。

其他帮助

你只能使用MATLAB基础包里的函数($MATLAB/toolbox/matlab)。请勿使用其他工具箱里的函数。你所提交的文件将会被用来与最新版本的MATLAB函数库进行对比。请参考 资源区 的最新版本信息。

不可使用以下函数、文件或命令:

  • MEX-files
  • Java commands or object creation
  • eval, feval, inline, and function handles
  • Shell escapes such as !, dos, unix, and system
  • Handle Graphics commands
  • ActiveX commands
  • File I/O commands
  • Debugging commands
  • Printing commands
  • Simulink commands
  • Benchmark commands such as tic, toc, flops, clock, and pause
  • error, clear, and persistent functions

关于作弊行为

为了对有参赛者的公平,我们要求你不要对系统有黑客行为,并且能遵守以下规定:

  • Entries compromising contest machinery are disallowed.
  • Extraction of puzzles in the test suite by manipulating the score, runtime, or error conditions is also disallowed.
  • While tuning the entry to the contest test suite using multiple entries is permitted, overwhelming the queue is discouraged.

相关资源

以下资源对你有帮助:

竞赛时间安排

整个竞赛日程分为以下四个时间段:

  • 黑夜 - 竞赛第一天,你看不到别人提交的程序或得分。
  • 黎明 - 竞赛第二天,你可以看到别人的得分,但是看不到别人的程序
  • 白天 - 竞赛第三天起,你可以看到别人提交的程序和得分。
  • 黄昏 - 竞赛结束。