没有合适的资源?快使用搜索试试~ 我知道了~
算法设计技巧与分析课件(英文版):ch13 Backtracking.ppt
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 115 浏览量
2022-06-28
10:42:51
上传
评论
收藏 2.59MB PPT 举报
温馨提示
试读
64页
算法设计技巧与分析课件(英文版):ch13 Backtracking.ppt
资源推荐
资源详情
资源评论
Algorithms Design Techniques and Analysis
Chapter 13
Backtracking
—An Efficient Searching Algorithm
Algorithms Design Techniques and Analysis
What we have known after previous
learning…
•
A subclass of intractable problems have been studied,
commonly referred to as the class of NP-complete
problems.
•
The Class P
•
The Class NP
•
NP-Complete Problems
•
The Class co-NP
•
The Class NPI
Algorithms Design Techniques and Analysis
Coping with hardness
•
Three useful methodologies:
•
One, Suitable for those problems that exhibit good
average time complexity, but for which the worst case
polynomial time solution is exclusive. This methodology
is based on a methodic examination of the implicit state
space induced by the problem instance under study. In
the process of exploring the state space of the
instance, some pruning takes place.
•
Two, based on the probabilistic notion of accuracy.
•
Three, useful for incremental solutions where one is
willing to compromise on the quality of solution in
return for faster (polynomial time) solutions.
Algorithms Design Techniques and Analysis
Contents of current chapter
•
Backtracking.
•
The 3-coloring problem
•
The 8-queens problem
•
The general backtracking method
•
Sub of sub set problem
•
Hamilton cycle problem
•
Branch and bound
•
TSP problem
Algorithms Design Techniques and Analysis
13.1 Introduction
•
In many real world problems, as in most of the problems
NP-hard problems, a solution can be obtained by
exhaustively searching through a large but finite number of
possibilities .
•
Moreover, for virtually all these problems, there does not
exist an algorithm that uses a method other than exhaustive
search .
How to develop systematic techniques of searching?
And how to cut down the search space to possibly a much smaller
space?
剩余63页未读,继续阅读
资源评论
智慧安全方案
- 粉丝: 3642
- 资源: 59万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功