找回密码
 欢迎注册
楼主: 数学星空

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

[复制链接]
发表于 2009-6-24 22:40:33 | 显示全部楼层
上面那个很容易扩展到所有奇数阶的 下面再给个8阶的 另外,NP问题不难,NPC问题的判定才困难。计数问题不叫NP,叫P#完全 这个问题的计数问题尽管困难,但未必是P#完全的。因为限制太大了,有可能可以较大幅度的剪枝
1.jpg

评分

参与人数 2威望 +5 鲜花 +2 收起 理由
winxos + 2 + 2 好强大
mathe + 3 非常不错

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-24 22:57:31 | 显示全部楼层
你画的图太大了无法看清楚哟,可以缩小些吗??
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-24 23:46:54 | 显示全部楼层
22# 数学星空 只要看到关键的这3行就行了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-25 07:48:01 | 显示全部楼层
shshsh_0510应该基本已经解决了2(n-1)的构造问题. 现在余下的问题就是2(n-1)是否最优解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-6-25 08:19:27 | 显示全部楼层
24# mathe 大家看看能否找到其它形状的构造?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-25 11:12:15 | 显示全部楼层
本帖最后由 数学星空 于 2009-6-25 11:18 编辑 为了使大家更好理解,更直观的分析问题,现将SHSHSH_0510的图再重新画了一遍,见下图 2.jpg 4.jpg
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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 11阶点阵2.jpg [localimg=180,113]3[/localimg]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-6-26 17:44:27 | 显示全部楼层
请大家思考构造九阶,十阶的点阵连线结果...
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-23 00:25 , Processed in 0.072654 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表