w***g
发帖数: 5958 | 1 【 以下文字转载自 Mathematics 讨论区 】
发信人: wdong (cybra), 信区: Mathematics
标 题: 请教一个智力题
发信站: BBS 未名空间站 (Sat Apr 25 08:30:55 2015, 美东)
众所周知：包围单位面积的曲线，圆的面积最小。
一个推广的问题：一张面积无穷大的纸，没有边界，需要剪下来面
积相等的n片，每片面积为1,但形状不限。怎么剪使得剪刀走过的长度最小？
n=1的话显然就是圆形最优。如果n=16，怎么剪最好？
已经确定用16个6边形蜂窝装剪比棋盘更好。但蜂窝边界有棱角，显然也不是最优的。 | w***g
发帖数: 5958 | 2 既然贴到这个版来了，就按这个版的规矩来。
因为16片之间共享边的话可以使剪刀的路径减小，所以16片肯定是连在一起的一大片。
稍微跳跃一下，假设这一大片的边界是一个圆。这样就可以用编程的手段来解决这个问
题了。
给定一个参数R，可以算出一个半径为R的（近似的）圆。这个圆内有很多像素。以每个
像素为一个节点，产生一个图。如果两个像素是相邻的（4相邻或者8相邻，作为参数吧
），就在两个对应的节点间连一条边。上面的问题就可以变成一个图着色的问题：
怎样把所有的节点按相同的比例涂上16种颜色(因为无法整除，所以有的颜色的节点会
比别的颜色的节点少1个），使得两个顶点颜色不一样的边的个数最少。
这个问题显然是NP难的。但对于实际问题来说，近似解应该就可以了。
有同学愿意来写这个练习题吗？如果有多于一个同学愿意做练习题的，我可以写程序产生
表述为图着色的input，然后得到output后产生visualization。我们可以比比：
- 谁的算法画出来的图更漂亮，
- 那种语言算得快，
.....
感兴趣的同学请回复。
【在 w***g 的大作中提到】
: 【 以下文字转载自 Mathematics 讨论区 】
: 发信人: wdong (cybra), 信区: Mathematics
: 标 题: 请教一个智力题
: 发信站: BBS 未名空间站 (Sat Apr 25 08:30:55 2015, 美东)
: 众所周知：包围单位面积的曲线，圆的面积最小。
: 一个推广的问题：一张面积无穷大的纸，没有边界，需要剪下来面
: 积相等的n片，每片面积为1,但形状不限。怎么剪使得剪刀走过的长度最小？
: n=1的话显然就是圆形最优。如果n=16，怎么剪最好？
: 已经确定用16个6边形蜂窝装剪比棋盘更好。但蜂窝边界有棱角，显然也不是最优的。
| W***o
发帖数: 6519 | 3 请教大牛： 为什么觉得graph coloring (2 or 3-coloring?) 是这个方向？ 以下面的
图为
例子，我看不出来你怎么能切除16片等面积的形状出来。
为什么不可以用圆形hamiltonian cycle/Traveling sales person (假设剪刀就是一个
sales man），上面有16个vertices, 每个vertex 距离相等？
是不是也可以转成linear programming？ min (L * n * m), where L is the length/
cost needed per shape cutting, n = 16, m1, m2, ... m16 ?
【在 w***g 的大作中提到】
: 既然贴到这个版来了，就按这个版的规矩来。
: 因为16片之间共享边的话可以使剪刀的路径减小，所以16片肯定是连在一起的一大片。
: 稍微跳跃一下，假设这一大片的边界是一个圆。这样就可以用编程的手段来解决这个问
: 题了。
: 给定一个参数R，可以算出一个半径为R的（近似的）圆。这个圆内有很多像素。以每个
: 像素为一个节点，产生一个图。如果两个像素是相邻的（4相邻或者8相邻，作为参数吧
: ），就在两个对应的节点间连一条边。上面的问题就可以变成一个图着色的问题：
: 怎样把所有的节点按相同的比例涂上16种颜色(因为无法整除，所以有的颜色的节点会
: 比别的颜色的节点少1个），使得两个顶点颜色不一样的边的个数最少。
: 这个问题显然是NP难的。但对于实际问题来说，近似解应该就可以了。
| w***g
发帖数: 5958 | 4 大牛不敢当。
是圆形对应的像素连成的图。确定R画出来的圆里面的像素不一定正好是16n，有可能除
不尽。那样的话不同颜色的像素最多差一个。
你的hamilton cycle+16个vertices思路有点混乱。剪刀走16步，步与步之间会交叉，
切出来的未必是16片。距离相等这个idea倒似乎可以。先均匀放入16个不同颜色的点，
其余的点没有颜色，然后让颜色以相同的速度扩散，不同的颜色碰到的地方就是边。出
来的是一个voronoi图。如果16个点位置放的好的话，就可以保证16块大小一样。
话说，如果精度无穷，能否证明最优切法一定对应一个voronoi图？我看着似乎可以。
length/
【在 W***o 的大作中提到】
: 请教大牛： 为什么觉得graph coloring (2 or 3-coloring?) 是这个方向？ 以下面的
: 图为
: 例子，我看不出来你怎么能切除16片等面积的形状出来。
: 为什么不可以用圆形hamiltonian cycle/Traveling sales person (假设剪刀就是一个
: sales man），上面有16个vertices, 每个vertex 距离相等？
: 是不是也可以转成linear programming？ min (L * n * m), where L is the length/
: cost needed per shape cutting, n = 16, m1, m2, ... m16 ?
| s*i
发帖数: 5025 | 5 直觉是经典的 surface energy 问题。求最小表面能。
一个是圆
两个肯定是连接的两个半圆（大半，小半，还得解出来）
[发表自未名空间手机版 - m.mitbbs.com] | w***g
发帖数: 5958 | 6 你这个太牛了。我解了下n=2的情况，确实是两个接起来的大半个圆。
中间的线段对应的圆的内角弧度是2.1的样子。
看来我的直觉还很差。
假设总面积为1, 内角弧度的一半为x，则所有边长度和为
f(x) = (4 * (pi -x) + 2 * sin(x))/sqrt(2*(pi-x)+sin(2*x))
在gnuplot里画一下就看出来了。x=1.05的样子达到最小值。
【在 s*i 的大作中提到】
: 直觉是经典的 surface energy 问题。求最小表面能。
: 一个是圆
: 两个肯定是连接的两个半圆（大半，小半，还得解出来）
: [发表自未名空间手机版 - m.mitbbs.com]
|
|
