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算过的吧。第二问非常简单，去一个点足够了
页: [1]
查看完整版本: 一个移动路线的问题