Why longest path problem doesn't have optimal substructure?
We all know that the shortest path problem has optimal substructure. The reasoning is like below:
Supppose we have a path p from node u to v, another node t lies on path p: u->t->v ("->" means a path).
We claim that u->t is also a shortest path from u to t, and t->v is a shortest path from t to v.
Proof: if there is another path from u to t that is shorter than u->t, we can simply replace u->t with this shorter path in the solution of u->v, resulting in a shorter path than u->v, contradicting the fact that u->v is a shortest path from u to v.
But why can't we apply similar reasoning to the longest path problem? It's because in the longest path problem there are some constraints imposed on the solution. Suppose u->v is a longest path from u->v, node t lies on it.
So it's like u->t->v. If there is a longer path from u to t than u->t, if we cut off u->t from u->v and paste in the longer path, this new solution may fail some of the restrictions, for example, it may contains a cycle, which is invalid.
最新文章
- java中的对象，类。与 方法的重载。
- 如何使用.NET开发全版本支持的Outlook插件产品（一）——准备工作
- 为什么说Babel将推动JavaScript的发展
- TortoiseGit 添加ssh key
- Xcode模拟器和真机生成的日志查看(转载)
- Centos环境下部署游戏服务器－SSH
- web版扫雷小游戏（一）
- poj 2492A Bug's Life
- 开启Apache mod_rewrite模块（解决404 Not Found）
- php基础之三 数组
- Windows 下 pip和easy_install 的安装与使用
- Oracle数据库中直方图对执行计划的影响
- 五分钟学习React(四)：什么是JSX
- 谈谈.NET架构师面试及如何设计面试题
- 4月23日 MySQL学习-DDL
- web机试
- overflow标签
- lucene查询索引之Query子类查询——（七）
- hashlib和hmac
- Angular 4.0 环境搭建