解锁所有相交的线段

KeyTo9_Fans

在最强大脑第五季的国际赛最终战中日对决的最后一场比赛中，

参赛选手要为一个平面图移动顶点，解开所有相交的边，使得任何两条边都不相交，

率先解锁完所有相交线段的选手得分，五轮比赛累计得分高的选手获得这场比赛的胜利。

下载这个附件，解压后就可以玩这个游戏了：

Untangle.zip (87.03 KB, 下载次数: 6)

2018-4-7 23:41 上传

点击文件名下载附件

操作说明：

用鼠标拖动小圆点，使得所有的边都不相交即可过关。

#####

我感觉存在固定的程序，可以解开任何一个平面图。

该程序读入一个包含$n$个顶点、$m$条边平面图，

经过一系列演算后输出$n$个顶点的坐标，

使得这$m$条边中任何两条边都不相交。

但不知道这一程序具体如何实现。

而中国选手杨英豪的解法是先搭建一个三角形，

然后按照某种顺序把其余顶点依次往这个三角形里填，

使得新填入的顶点的连边不和之前填入的顶点的连边相交。

杨英豪凭借这一解法在前四轮比赛中都取得了胜利，提前锁定了胜局：

http://baijiahao.baidu.com/s?id=1597038140321816692

这个解法可以用程序实现吗？

kastin

这个游戏很多年前(大概8年前吧）我就玩过，是网上的一款flash小游戏，英文名也叫untangle（中文名好像叫星空什么）。游戏有很多关，从简单到难，最后我全部通关了，其背景音乐很好听。我记得我当时把这个flash通过缓存搞下来了，存在笔记本电脑上。回去找找再传上来给大家看看。

根据个人通关经验，发现自己在解更高关卡时大多根据直觉和前几关的零碎经验，并没有什么程序性的步骤（但有大致方向或原则）。然而这种直觉+经验的方式，可能就是最快的学习方式（当然不一定是效率最高的解法），即尽可能少的尝试次数来学到如何解决问题。这让我想到了如今火热的增强学习/迁移学习和元学习，如果能实现类似人这样的学习方式，那么智能就更进一步了。

kastin

找到一个在线版的：http://www.iqeq.com.cn/2016-1-21-1.html

mathe

判断平面图的算法是有多项式算法的

mathe

https://ac.els-cdn.com/002200008 ... be9d5be445c425df13d