b*******m
发帖数: 5492 | 1 平面内给定任意n个点，试从任一点出发，构造一条最短路径，使其成为封闭n边形。
另：这个多边形是凸还是凹？给出证明 |
l**z
发帖数: 63 | 2 凹凸应该是不定的，跟给的点分布有关
【在 b*******m 的大作中提到】
: 平面内给定任意n个点，试从任一点出发，构造一条最短路径，使其成为封闭n边形。
: 另：这个多边形是凸还是凹？给出证明
|
z********8
发帖数: 671 | 3 凸
反证法。假如是凹，凹的两边将比两个点的连线长，就不是最短路径。
【在 b*******m 的大作中提到】
: 平面内给定任意n个点，试从任一点出发，构造一条最短路径，使其成为封闭n边形。
: 另：这个多边形是凸还是凹？给出证明
|
l**z
发帖数: 63 | 4 跟travelling salesman problem差不多。NP-hard problem.
【在 b*******m 的大作中提到】
: 平面内给定任意n个点，试从任一点出发，构造一条最短路径，使其成为封闭n边形。
: 另：这个多边形是凸还是凹？给出证明
|
b*****g
发帖数: 919 | 5 .
.
. .
这样的怎么凸？
【在 z********8 的大作中提到】
: 凸
: 反证法。假如是凹，凹的两边将比两个点的连线长，就不是最短路径。
|
f*****h
发帖数: 1327 | 6 123连起来，一个钝角三角形
题目没有说必须包括所有点
【在 b*****g 的大作中提到】
: .
: .
: . .
: 这样的怎么凸？
|
l**z
发帖数: 63 | 7 再考虑多一点
题目其实出的不严格，因为任意n点并不一定能练成n边行
比如所有点都在一条直线上的情况。
如果题意是所有点都连在一起，那就跟TSP一模一样。
如果题意是允许有些点不相连，但被n-m边行包围在中间，就是个凸边形
【在 l**z 的大作中提到】
: 跟travelling salesman problem差不多。NP-hard problem.
|
b*****g
发帖数: 919 | 8 n个点 n边形
【在 f*****h 的大作中提到】
: 123连起来，一个钝角三角形
: 题目没有说必须包括所有点
|
w**t
发帖数: 94 | 9 nod这个题目不严谨
【在 b*****g 的大作中提到】
: n个点 n边形
|
