《算法设计手册》第二版：专业算法设计指南

需积分: 9 178 浏览量更新于2024-07-23 收藏 2.94MB PDF 举报

《算法设计手册》第二版是Steven S. Skiena撰写的一本经典著作，专为学生和计算机专业人员提供全面的组合算法技术指南。本书以实用性和深度见长，旨在帮助读者理解和设计高效、优雅的算法，是算法设计领域的权威参考书。该书分为两大部分：技术和资源。在"技术"部分，作者深入浅出地介绍了各种核心算法设计原则和方法，包括搜索、排序、图论、动态规划、贪心算法、回溯法等，并通过丰富的例子和习题来帮助读者掌握这些技术。读者可以在这里学习如何分析问题，选择合适的数据结构，以及如何设计和优化算法以解决复杂问题。 "资源"部分则涵盖了工具和库的使用，让读者了解如何利用现代编程语言和库来实现算法，以及最新的研究进展和技术趋势。此外，书中还提供了大量的代码示例和调试技巧，便于读者实践和应用所学知识。本书的重要特点是其系统性与实用性并重，不仅适合初学者作为入门教材，也适合有经验的专业人员作为查漏补缺的参考书籍。通过阅读《算法设计手册》，读者将能够提升算法设计能力，理解算法在实际问题中的应用，以及如何在实际开发环境中将理论转化为实践。对于那些希望通过深入研究和实践来提升算法设计技能的读者来说，这本书是不可或缺的资源。它不仅提供了一个坚实的基础，而且随着技术的发展，不断更新的内容使其始终保持相关性和前沿性。无论是准备算法竞赛，还是在日常工作中面对复杂问题，这本书都是一个强大的盟友。

Introduction to Algorithm Design

What is an algorithm? An algorithm is a procedure to accomplish a speciﬁc task.

An algorithm is the idea behind any reasonable computer program.

To be interesting, an algorithm must solve a general, well-speciﬁed problem.An

algorithmic problem is speciﬁed by describing the complete set of instances it must

work on and of its output after running on one of these instances. This distinction,

between a problem and an instance of a problem, is fundamental. For example, the

algorithmic problem known as sorting is deﬁned as follows:

Problem: Sorting

Input: A sequence of n keys a

,...,a

Output: The permutation (reordering) of the input sequence such that a



≤ a



≤

···≤a



n−1

≤ a



An instance of sorting might be an array of names, like {Mike, Bob, Sally, Jill,

Jan}, or a list of numbers like {154, 245, 568, 324, 654, 324}. Determining that

you are dealing with a general problem is your ﬁrst step towards solving it.

An algorithm is a procedure that takes any of the possible input instances

and transforms it to the desired output. There are many diﬀerent algorithms for

solving the problem of sorting. For example, insertion sort is a method for sorting

that starts with a single element (thus forming a trivially sorted list) and then

incrementally inserts the remaining elements so that the list stays sorted. This

algorithm, implemented in C, is described below:

S.S. Skiena, The Algorithm Design Manual, 2nd ed., DOI: 10.1007/978-1-84800-070-4 1,

 Springer-Verlag London Limited 2008

4 1. INTRODUCTION TO ALGORITHM DESIGN

I N S E R T I O N S O R TI N S E R T I O N S O R T

I N S E R T I O N S O R T

E I N S R T I O N S O R TE I N S R T I O N S O R T

E I N R S T I O N S O R T

E I N R S T I O N S O R TE I N R S T I O N S O R T

E I I N R S T O N S O R T

E I I N O R S T N S O R TE I I N O R S T N S O R T

E I I N N O R S T S O R TE I I N N O R S T S O R T

E I I N N O R S S T O R TE I I N N O R S S T O R T

E I I

R R

T T

E I I N N O O R S S T R T

E I I N N O O R R S S T T

Figure 1.1: Animation of insertion sort in action (time ﬂows down)

insertion_sort(item s[], int n)

{

int i,j; /* counters */

for (i=1; i<n; i++) {

j=i;

while ((j>0) && (s[j] < s[j-1])) {

swap(&s[j],&s[j-1]);

j = j-1;

}

An animation of the logical ﬂow of this algorithm on a particular instance (the

letters in the word “INSERTIONSORT”) is given in Figure 1.1

Note the generality of this algorithm. It works just as well on names as it does

on numbers, given the appropriate comparison operation (<) to test which of the

two keys should appear ﬁrst in sorted order. It can be readily veriﬁed that this

algorithm correctly orders every possible input instance according to our deﬁnition

of the sorting problem.

There are three desirable properties for a good algorithm. We seek algorithms

that are correct and eﬃcient, while being easy to implement. These goals may not

be simultaneously achievable. In industrial settings, any program that seems to

give good enough answers without slowing the application down is often acceptable,

regardless of whether a better algorithm exists. The issue of ﬁnding the best possible

answer or achieving maximum eﬃciency usually arises in industry only after serious

performance or legal troubles.

In this chapter, we will focus on the issues of algorithm correctness, and defer a

discussion of eﬃciency concerns to Chapter 2. It is seldom obvious whether a given

6 1. INTRODUCTION TO ALGORITHM DESIGN

Several algorithms might come to mind to solve this problem. Perhaps the most

popular idea is the nearest-neighbor heuristic. Starting from some point p

, we walk

ﬁrst to its nearest neighbor p

.Fromp

, we walk to its nearest unvisited neighbor,

thus excluding only p

as a candidate. We now repeat this process until we run

out of unvisited points, after which we return to p

to close oﬀ the tour. Written

in pseudo-code, the nearest-neighbor heuristic looks like this:

NearestNeighbor(P )

Pick and visit an initial point p

from P

p = p

i =0

While there are still unvisited points

i = i +1

Select p

to be the closest unvisited point to p

i−1

Visit p

Return to p

from p

n−1

This algorithm has a lot to recommend it. It is simple to understand and imple-

ment. It makes sense to visit nearby points before we visit faraway points to reduce

the total travel time. The algorithm works perfectly on the example in Figure 1.2.

The nearest-neighbor rule is reasonably eﬃcient, for it looks at each pair of points

) at most twice: once when adding p

to the tour, the other when adding p

Against all these positives there is only one problem. This algorithm is completely

wrong.

Wrong? How can it be wrong? The algorithm always ﬁnds a tour, but it doesn’t

necessarily ﬁnd the shortest possible tour. It doesn’t necessarily even come close.

Consider the set of points in Figure 1.3, all of which lie spaced along a line. The

numbers describe the distance that each point lies to the left or right of the point

labeled ‘0’. When we start from the point ‘0’ and repeatedly walk to the nearest

unvisited neighbor, we might keep jumping left-right-left-right over ‘0’ as the algo-

rithm oﬀers no advice on how to break ties. A much better (indeed optimal) tour

for these points starts from the leftmost point and visits each point as we walk

right before returning at the rightmost point.

Try now to imagine your boss’s delight as she watches a demo of your robot

arm hopscotching left-right-left-right during the assembly of such a simple board.

“But wait,” you might be saying. “The problem was in starting at point ‘0’.

Instead, why don’t we start the nearest-neighbor rule using the leftmost point

as the initial point p

? By doing this, we will ﬁnd the optimal solution on this

instance.”

That is 100% true, at least until we rotate our example 90 degrees. Now all

points are equally leftmost. If the point ‘0’ were moved just slightly to the left, it

would be picked as the starting point. Now the robot arm will hopscotch up-down-

up-down instead of left-right-left-right, but the travel time will be just as bad as

before. No matter what you do to pick the ﬁrst point, the nearest-neighbor rule is

doomed to work incorrectly on certain point sets.

剩余739页未读，继续阅读

yangkehai1234

粉丝: 1
资源: 27

《算法设计手册》第二版：专业算法设计指南

The Algorithm Design Manual(2nd Ed.)_Source Code

The Algorithm Design Manual second edition

The Algorithm Design Manual (2rd Edition)

最短路径dijkstra算法参考文献

有关贪心算法的参考文献

2023年计算机科学与技术考研书籍推荐

kleinberg——algorithm design课后题答案

Extend the application above to be able to measure the efficiency of the implemented sorting algorithm in term of number of comparisons performed by the algorithm. The application should display the total number of comparisons performed by the algorithm for a given collection of items. [10 marks]

Derive the stochastic gradient descent algorithm

最新资源