解锁所有相交的线段
在最强大脑第五季的国际赛最终战中日对决的最后一场比赛中，参赛选手要为一个平面图移动顶点，解开所有相交的边，使得任何两条边都不相交，
率先解锁完所有相交线段的选手得分，五轮比赛累计得分高的选手获得这场比赛的胜利。
下载这个附件，解压后就可以玩这个游戏了：
操作说明：
用鼠标拖动小圆点，使得所有的边都不相交即可过关。
#####
我感觉存在固定的程序，可以解开任何一个平面图。
该程序读入一个包含$n$个顶点、$m$条边平面图，
经过一系列演算后输出$n$个顶点的坐标，
使得这$m$条边中任何两条边都不相交。
但不知道这一程序具体如何实现。
而中国选手杨英豪的解法是先搭建一个三角形，
然后按照某种顺序把其余顶点依次往这个三角形里填，
使得新填入的顶点的连边不和之前填入的顶点的连边相交。
杨英豪凭借这一解法在前四轮比赛中都取得了胜利，提前锁定了胜局：
http://baijiahao.baidu.com/s?id=1597038140321816692
这个解法可以用程序实现吗？ 这个游戏很多年前(大概8年前吧）我就玩过，是网上的一款flash小游戏，英文名也叫untangle（中文名好像叫星空什么）。游戏有很多关，从简单到难，最后我全部通关了，其背景音乐很好听。我记得我当时把这个flash通过缓存搞下来了，存在笔记本电脑上。回去找找再传上来给大家看看。
根据个人通关经验，发现自己在解更高关卡时大多根据直觉和前几关的零碎经验，并没有什么程序性的步骤（但有大致方向或原则）。然而这种直觉+经验的方式，可能就是最快的学习方式（当然不一定是效率最高的解法），即尽可能少的尝试次数来学到如何解决问题。这让我想到了如今火热的增强学习/迁移学习和元学习，如果能实现类似人这样的学习方式，那么智能就更进一步了。 找到一个在线版的：http://www.iqeq.com.cn/2016-1-21-1.html 判断平面图的算法是有多项式算法的 https://ac.els-cdn.com/0022000085900042/1-s2.0-0022000085900042-main.pdf?_tid=36ebc59a-8155-4968-a471-319f239826ef&acdnat=1523160064_8b61da0e4501ebe9d5be445c425df13d
页:
[1]