点阵连线问题(NP)

shshsh_0510 · 发表于 2009-6-24 22:40:33

上面那个很容易扩展到所有奇数阶的
下面再给个8阶的

另外，NP问题不难，NPC问题的判定才困难。计数问题不叫NP,叫P#完全
这个问题的计数问题尽管困难，但未必是P#完全的。因为限制太大了，有可能可以较大幅度的剪枝

数学星空 · 发表于 2009-6-24 22:57:31

你画的图太大了无法看清楚哟,可以缩小些吗??

shshsh_0510 · 发表于 2009-6-24 23:46:54

22# 数学星空

只要看到关键的这3行就行了

mathe · 发表于 2009-6-25 07:48:01

shshsh_0510应该基本已经解决了2(n-1)的构造问题.
现在余下的问题就是2(n-1)是否最优解

winxos · 发表于 2009-6-25 08:19:27

24# mathe
大家看看能否找到其它形状的构造？

数学星空 · 发表于 2009-6-25 11:12:15

本帖最后由数学星空于 2009-6-25 11:18 编辑

为了使大家更好理解,更直观的分析问题,现将SHSHSH_0510的图再重新画了一遍,见下图

数学星空 · 发表于 2009-6-25 18:54:05

需要思考的几个问题

在满足以上题目条件前提下)
1.能串联N阶点阵的折数,它的最少线段数J(N)=2*(N-1)?
2.能串联N阶点阵的折线,它的计数问题?
3.能串联N阶点阵的折线,它的辅助点数取值范围?(除去N^2点外,线段的端点数)
4.能串联N阶点阵的折线,它的最小长度是多少?(设相邻两格点的最小距离为1)

数学星空 · 发表于 2009-6-26 08:13:12

5阶点阵图,见下图:
5阶点阵图.jpg

数学星空 · 发表于 2009-6-26 17:43:10

11阶点阵连线结果有了,见下图:
11阶点阵1.jpg

[localimg=180,113]3[/localimg]

数学星空 · 发表于 2009-6-26 17:44:27

请大家思考构造九阶,十阶的点阵连线结果...

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 点阵连线问题(NP)