[Algorithm] Greedy method

Given two sequences of letters A and B, find if B is a subsequence of A in the
sense that one can delete some letters from A and obtain the sequence B.

Greedy领先的思想。(always stay ahead)

There is a line of 111 stalls, some of which need to be covered with boards.
You can use up to 11 boards, each of which may cover any number of
consecutive stalls. Cover all the necessary stalls, while covering as few total
stalls as possible

一块大板,不断去掉大空隙。直到大板被分为要求的11个。

本质:排序“间隙”,先 eliminate 最大的间隙(贪心的体现)

Ref: https://projectalgorithm.wordpress.com/2011/04/25/greedier-than-you/

A list of n files fi of lengths li which have to be stored on a tape.
Each file is equally likely to be needed. To retrieve a file, one must start from
the beginning of the tape and scan it until the tape is found and read.

Order the files on the tape so that the average (expected) retrieval time
is minimised.

如果p不再均匀,则比较P/L,如下。

用最少的钉子穿插所有的木条。

Greedy的对象的选择问题:

    • 穿插最多的优先 (greedy 失败)
    • 最早结束的优先 (greedy 成功)

Assume you are given n sorted arrays of different sizes. You are allowed
to merge any two arrays into a single new sorted array and proceed in
this manner until only one array is left. Design an algorithm that
achieves this task and uses minimal total number of moves of elements of
the arrays. Give an informal justification why your algorithm is optimal.

类似Merge sort过程的,huffman code原理的东东。

较小的块优先合并。

合并后的较大的块,如果还有后续的操作,那么前面合并得越大,将会成为后续移动操作中的累赘。

Along the long, straight road from Loololong to Goolagong houses are
scattered quite sparsely, sometimes with long gaps between two
consecutive houses. Telstra must provide mobile phone service to people
who live alongside the road, and the range of Telstras cell base station is
5km. Design an algorithm for placing the minimal number of base
stations alongside the road, that is sufficient to cover all houses.

一个思考:从左到右,从右到左,既然都是greedy,minimum是一样的,但stations的位置却不同。

You are given a connected graph with weighted edges. Find a spanning
tree such that the largest weight of all of its edges is as small as possible.

求加强连通图的最小生成树

为何最优?

    • Kruskal Algo: sort e by cost 以edge为主角,则适合"稀疏图"
    • Prim Algo: start from any vertex, add lightest edge one by one. 以vertex为主角,则适合"稠密图"

Ref: 最小生成树-Prim算法和Kruskal算法

Design an algorithm which produces a minimum spanning tre T 0 for the

new graph containing the additional vertex vn+1 and which runs in time

O(n log n).

New vertex与其他n个vertex的边做排序。

There are n radio towers for broadcasting tsunami warnings. You are

given the coordinates of each tower and its radius of range. When a

tower is activated, all towers within the radius of range of the tower will

also activate, and those can cause other towers to activate and so on.

You need to equip some of these towers with seismic sensors so that

when these sensors activate the towers where these sensors are located all

towers will eventually get activated and send a tsunami warning.

The goal is to design an algorithm which finds the fewest number of

towers you must equip with seismic sensors.

总有一个塔,在连锁反应中能激活最多的其他塔。给它安装报警器即可。

Find a maximum size subset of compatible activities.

求“一段时间内”能容纳的“最多活动数”。

最早结束时间的活动优先。

Transforming any optimal solution to the greedy solution with equal number of
activities

find that proving the greedy solution is also optimal.

证明

greedy exchange, 即证明greedy所得结论不会worse.

Extended:

“最多活动数” ==> "总的最长活动时间“,且”每个活动时间不等“,则,greedy失效,需dynamic programming.

Schedule all the jobs so that the lateness of the job with the largest
lateness is minimised.

最小化任务延迟

只关心deadlines.

证明:(交换论证)

关键步骤的证明是"减少一个逆序de调度导致的最大延迟不会更糟".

Partition the vertices of G into k disjoint subsets so that the minimal
distance between two points belonging to different sets of the partition is as
large as possible. Thus, we want a partition into k disjoint sets which are as
far apart as possible.

Sort the edges in an increasing order and start performing the usual
Kruskal’s algorithm for building a minimal spanning tree,

but stop when you obtain k trees, rather than a single spanning tree.

红线肯定大于任何一条蓝线。

时间复杂度:

n^2条边,O(n^2 log n).

采用“并查集”数据结构后,

we make at most 2n2 calls of the Find operation and

at most n calls of the Union operation.

Scheduling unit jobs with penalties and deadlines.

The problem of scheduling unit-time tasks with deadlines and penalties for a single processor has the following inputs:

 a set S = {1, 2, . . . , n} of n unit-time tasks;

 a set of n integer deadlines d1d2, . . . , dn, such that each di satisfies 1  di  n and task i is supposed to finish by time di; and

 a set of n nonnegative weights or penalties w1,w2, . . . , wn, such that a penalty wi is incurred if task i is not finished by time di and no penalty is incurred if a task finishes by its deadline.

We are asked to find a schedule for S that minimizes the total penalty incurred for missed deadlines.

拟阵理论(matroid)

Ref: http://www.it610.com/article/1920678.htm

实现任务的最优调度主要就是利用贪心算法中拟阵的思想。

如果S是一个带期限的单位时间任务的集合,且I是所有独立的任务集构成的集合,则对应的系统 M =(S,I)是一个拟阵。满足如下条件:

    1. S是一个非空有穷集合;
    2. l⊆2^S且?∈l (I为S的非空子集族)
    3. l满足交换性质 (Augmentation):若A∈l,B∈l且|A|<|B|,则∃x∈B−A,使得A∪{x}∈l (这条性质给了我们已知集合B,构造集合A的方法)
    4. l满足遗传性质 (Downward closure):若B∈l,A⊆B,则A∈l. Or, B是S的独立子集,这样B的任意子集也都是S的独立子集。(暗示了我们已知集合B,找出其子集的性质的办法)

利用拟阵解决任务调度问题的算法原理主要就是将最小化迟任务的惩罚之和问题转化为最大化早任务的惩罚之和的问题,也就是说在任务调度的时候优先选择当前任务序列中惩罚最大的任务。

这里,假设集合A存放任务的一个调度。如果存在关于A中任务的一个调度,使得没有一个任务是迟的,称任务集合A是独立的。

Prove:

先证明其是拟阵,可采用最大化早任务的惩罚和的贪心算法。

Extended:

O(n)次独立性检查的每一次都用O(n)时间。如何优化?

并查集。

时间: 04-21

[Algorithm] Greedy method的相关文章

[Algorithm][Greedy]Dijsktra Algorithm

面试折在了dijsktra algorithm上,我一个暴风哭泣-- 本来是想复习一下Dijsktra算法,又看到了Prim's algorithm 等系列,今天就着这个机会都好好复习一下. ---------------------------正文分割线------------------------------------------ Dijsktra Algorithm 给出一个图以及一个起点,找到从起点到其他所有点的最短路径. Dijsktra 与 Prim 最小生成树算法类似, 也生成

Method for finding shortest path to destination in traffic network using Dijkstra algorithm or Floyd-warshall algorithm

A method is presented for finding a shortest path from a starting place to a destination place in a traffic network including one or more turn restrictions, one or more U-turns and one or more P-turns using a Dijkstra algorithm. The method as sets a

Method of packet transmission from node and content owner in content-centric networking

A method of transmitting a content reply packet from a content owner in content-centric networking (CCN) includes determining a caching capability value threshold (CCVth) for determining a candidate node for caching a content based on a policy of the

Multiplication algorithm

A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.

bnu 28890 &amp;zoj 3689——Digging——————【要求物品次序的01背包】

Digging Time Limit: 2000ms Memory Limit: 65536KB This problem will be judged on ZJU. Original ID: 368964-bit integer IO format: %lld      Java class name: Main Prev Submit Status Statistics Discuss Next Type: None None Graph Theory 2-SAT Articulation

BNUOJ33566 Cycling Roads(并查集+判断两线段相交)

Cycling Roads Time Limit: 1000ms Memory Limit: 65536KB This problem will be judged on Ural. Original ID: 1966 64-bit integer IO format: %lld      Java class name: (Any) Prev Submit Status Statistics Discuss Next Font Size:  +   - Type:   None Graph T

BNUOJ33568 Glass Pyramid(DFS)

Glass Pyramid Time Limit: 1000ms Memory Limit: 65536KB This problem will be judged on Ural. Original ID: 1968 64-bit integer IO format: %lld      Java class name: (Any) Prev Submit Status Statistics Discuss Next Font Size: +   - Type:   None  Graph T

BNUOJ34980方(芳)格(哥)取数(好坑)

方(芳)格(哥)取数 Time Limit: 3000ms Memory Limit: 65536KB 64-bit integer IO format: %lld      Java class name: Main Prev Submit Status Statistics Discuss Next Font Size:  +   - Type:   None Graph Theory      2-SAT     Articulation/Bridge/Biconnected Compon

BNU 4260 ——Trick or Treat——————【三分求抛物线顶点】

ial Judge Prev Submit Status Statistics Discuss Next Type: None None   Graph Theory       2-SAT       Articulation/Bridge/Biconnected Component       Cycles/Topological Sorting/Strongly Connected Component       Shortest Path           Bellman Ford