Greedy algorithm

Definition

An algorithm that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems.

2

อัลกอริทึมเชิงละโมบ

• เป็นวงวนที่ใช้เกณฑ์จากสภาพของปัญหา ณ ขณะนั้น เพื่อขยายผลเฉลย ในขณะเดียวกันปัญหาก็มีขนาดเล็กลง
• ขยายผลเฉลยและลดขนาดของปัญหาไปเรื่อยๆ จนได้ผลเฉลยที่สมบูรณ์
• โดยการขยายผลเฉลยจากสภาพปัจจุบัน (ไม่ได้มองอนาคต)
• อันมีลักษระของความละโมบอยู่จึงเรียกว่า อัลกอริทึมเชิงละโมบ

3

ปัญหาต้นไม้ทวิภาค

4

ต้นไม้มีต้นทุนที่ = 2.43 ซึ่งไม่ใช่ต่ำสุด

Characteristic of Greedy algorithm

• In many problems, we wish to not only find a solution, but to find the best or optimal solution.
• A simple technique that works for some optimization problems is called the greedy technique.
• As the name suggests, we solve a problem by being greedy—that is, choosing the best, most immediate solution (i.e. a local solution).
• However, for some problems, this technique is not guaranteed to produce the best globally optimal solution.

5

ปัญหาถุงเป้ (Knapsack)

• 0/1 Knapsack เลือกชิ้นใดก็ต้องเลือกทั้งอัน

​

​

1. เลือกของตามมูลค่า ของแพงมาก่อน ละโมบมูลค่า
2. เลือกของที่น้ำหนักน้อยที่สุด ต้องการจำนวนชิ้นมากที่สุด
3. เลือกของที่มีมูลค่าต่อน้ำหนักมากที่สุด (เฉือนได้ และเฉือนไม่ได้)
1. bounded knapsack problem (BKP) เลือกชิ้นเดียวกันหลายอันได้ภายใต้จำนวนที่กำหนด
2. unbounded knapsack problem (UKP) เลือกชิ้นเดียวกันหลายอันได้

6

https://en.wikipedia.org/wiki/Knapsack_problem

Knapsack Example: weight ไม่เกิน 10

1)

2)

3)

7

Greedy changing-making algorithm

procedure change(c1, c2, … cr: ค่าของเหรียญ, c1 > c2 > … > cr : int){

for(i = 1 to r)

while (n >= ci) {

add a coin with value ci to the change

n = n - ci

}

}

​

8

Example! where c1 = 20, c2 = 15, c3 = 7, c4 = 1 and we want to give 22 “cents” in change.

• What will this algorithm produce?
• Is it optimal?

Example!, let c1 = 25, c2 = 10, c3 = 5, c4 = 1.

http://cse.unl.edu/~choueiry/S06-235/files/Algorithms.pdf

วิธีสั้นสุดแบบแหล่งต้นทางเดียว (shortest path)

• Dijkstra's algorithm solves the single-source shortest path problem.
• Bellman–Ford algorithm solves the single-source problem if edge weights may be negative.
• A* search algorithm solves for single pair shortest path using heuristics to try to speed up the search.
• Floyd–Warshall algorithm solves all pairs shortest paths.
• Johnson's algorithm solves all pairs shortest paths, and may be faster than Floyd–Warshall on sparse graphs.
• Viterbi algorithm solves the shortest stochastic path problem with an additional probabilistic weight on each node.

​

9

ต้นไม้แบบทอดข้ามเล็กสุด (Minimum spanning tree)

• A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total weighting for its edges.
• A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree. A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of minimum spanning trees for its connected components.

​

10

Kruskal algorithm

https://www.youtube.com/watch?v=5XkK88VEILk

11

Prim’s algorithm

https://www.youtube.com/watch?v=kuNfKbyOnDs

https://www.youtube.com/watch?v=Pn874kEc3IA

12

Huffman code

https://www.youtube.com/watch?v=dM6us854Jk0

​

13

Floyd Warshall Algorithm: All-pairs Shortest-paths

https://www.youtube.com/watch?v=KQ9zlKZ5Rzc�

14