一个移动路线的问题

jx215 · 发表于 2014-1-11 22:41:40

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

本帖最后由 jx215 于 2014-1-11 22:45 编辑

在5×6矩形框内，取对角线上A，B两点
问：一，从A移动到B有多少条不重复的路线？（每条路线经过的节点不能重复）
二，若将图中的红点去掉，则表示“此路不通”，需要绕道而行。现在要使得从A到B的路线少于原先的二分之一，则至少要去掉几个红点？为什么？

图一：未去掉红点

图二：已去掉部分红点

wayne · 发表于 2014-1-11 23:07:41

第一问，可以曲折蜿蜒，往回走吗？往回走也可以保证不重复点

jx215 · 发表于 2014-1-11 23:11:33

wayne 发表于 2014-1-11 23:07
第一问，可以曲折蜿蜒，往回走吗？往回走也可以保证不重复点

当然可以，只要走过的点不重复。

Lwins_G · 发表于 2014-1-12 00:07:20

在计算机科学里面，这样规模的问题可以用动态规划来解决。但时间复杂度关于`\min (n,m)`为指数级。@KeyTo9_Fans 对这个问题应该较为了解。

mathe · 发表于 2014-1-12 07:39:55

第一问fans算过的吧。第二问非常简单，去一个点足够了

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

[原创] 一个移动路线的问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。