演算法/貪心演算法
< 演算法
在回溯演算法中，我們看到了找到決策點並對該決策點的所有選項進行遞迴的演算法。貪心演算法可以看作是一種回溯演算法，在每個決策點，"最佳"選項已經確定，因此可以選擇而不必對任何備選選項進行遞迴。
"貪心"這個名字來源於演算法根據單個標準做出決策，而不是進行全域性分析，而全域性分析會考慮決策對後續步驟的影響。正如我們將看到的，在貪心演算法的情況下，這種回溯分析將是不必要的，因此它在意義上並非貪婪，即只為了短期利益而造成傷害。
與回溯演算法不同，並非每個問題都能使用貪心演算法解決。並非每個問題都"可以"使用貪心演算法解決。將找到最佳化問題的解視為一個爬山問題，貪心演算法只能用於在每個點上，選擇最陡峭的路徑都會通向峰頂的情況。
貪心演算法往往非常高效，而且可以相對直接地實現。在許多情況下，其複雜度為 O(n)，因為在每個點上都只有一個選擇。然而，大多數嘗試建立正確貪心演算法的嘗試都失敗了，除非首先證明了演算法的正確性。當貪心策略無法在所有輸入上產生最佳結果時，我們將其稱為啟發式方法，而不是演算法。當速度比精確結果更重要時（例如，當"足夠好"的結果就足夠時），啟發式方法很有用。
我們將要研究的第一個可以用貪心演算法解決的問題是事件安排問題。我們給定一組事件，每個事件都有開始時間和結束時間，我們需要產生一個這些事件的子集，使得這些事件互不交叉（即，時間不重疊），並且我們儘可能安排最多的事件。
以下是該問題的正式表述
- 輸入：events：一組區間 ，其中 是開始時間， 是結束時間。
- 解：Events 的子集 S。
- 約束：事件不能交叉（開始時間是排他的）。也就是說，對於所有區間 ，其中 ，則有 。
- 目標：最大化已安排事件的數量，即最大化集合 S 的大小。
我們首先從該問題的回溯解開始
// event-schedule -- schedule as many non-conflicting events as possible
function event-schedule(events array of s[1..n], j[1..n]): set
if n == 0: return fi
if n == 1: return {events[1]} fi
let event := events[1]
let S1 := union(event-schedule(events - set of conflicting events), event)
let S2 := event-schedule(events - {event})
if S1.size() >= S2.size():
return S1
else
return S2
fi
end
上面的演算法將忠實地找到最大的一組非衝突事件。它忽略瞭如何計算集合
- events - 一組衝突事件
的細節，但它需要 的時間。因為該演算法對自身進行了兩次遞迴呼叫，每次呼叫的引數大小均為 ，並且由於刪除衝突需要線性時間，因此該演算法所需時間的遞迴公式為
即 .
但是，假設我們不只選擇陣列中的第一個元素，而是使用其他標準。目的是隻選擇"正確"的元素，這樣我們就無需進行兩次遞迴呼叫。首先，讓我們考慮先選擇最短事件的貪心策略，直到我們無法再新增任何事件而不會產生衝突。這裡的想法是，最短的事件比其他事件更可能少發生衝突。
在某些情況下，先選擇最短事件會產生最佳結果。然而，下面是一種該策略不是最優的情況
在上面，最佳的解決方案是選擇事件 A 和 C，而不是隻選擇 B。也許我們應該選擇與其他事件衝突最少的事件，而不是最短的事件。這個策略看起來更直接，但它在這個場景中失敗了
在上面，我們可以透過選擇 A、B、C、D 和 E 來最大化事件數量。然而，與其他事件衝突最少的事件是 6、2 和 7、3。但是選擇 6、2 中的一個和 7、3 中的一個意味著我們無法選擇 B、C 和 D，而這包括三個事件，而不是兩個。
在存在依賴約束但允許併發的構建中，可以使用關鍵路徑確定來找到最短的可行時間，這等同於有向無環圖問題中的最長路徑。透過使用鬆弛和廣度優先搜尋，可以透過對權重（時間約束）取反來找到最長路徑，然後找到解決方案，最後恢復正權重。（鬆弛是指為每個要訪問的相鄰節點確定具有最小累積權重的父節點）
迪傑斯特拉最短路徑演算法
[edit | edit source]透過兩個（高階的虛擬碼）轉換，可以從效率較低的回溯演算法中推匯出迪傑斯特拉演算法。這裡的技巧是證明這些轉換保持正確性，但這也是對迪傑斯特拉演算法的全部洞察。[TODO：重要的是要注意這樣一個悖論：要解決這個問題，最好解決一個更一般化的版本。也就是說，從 s 到所有節點的最短路徑，而不僅僅是到 t。值得用一個單獨的彩色框來突出顯示這一點。]
為了瞭解迪傑斯特拉最短路徑演算法的工作原理，讓我們來看一個例子
有一個起點和終點，它們之間有兩條路徑；一條路徑的第一跳的成本為 30，最後一跳到目標節點的成本為 10，總成本為 40。另一條路徑的第一跳的成本為 10，第二跳的成本為 10，最後一跳的成本為 40，總成本為 60。
起點被賦予距離 0，以便它可以位於最短距離佇列的前面，所有其他節點都被賦予無窮大或一個很大的數字，例如 32767。
這使得起點成為佇列中的第一個當前節點。
在每次迭代中，當前節點都是最短路徑佇列中的第一個節點。它檢視與當前節點相鄰的所有節點；
以起點為例，在第一條路徑中，它將找到一個距離為 30 的節點，在第二條路徑中，它將找到一個距離為 10 的相鄰節點。當前節點的距離（在開始時為零）被加到相鄰節點的距離上，並且每個節點從起點開始的距離被更新，因此這些節點在第一條路徑中的距離將為 30+0=30，在第二條路徑中的距離將為 10+0=10。
重要的是，每個節點的先前指標屬性也被更新，因此每個節點將指向當前節點，對於這兩個節點來說，當前節點就是起點。
每個節點的優先順序在優先順序佇列中使用新的距離進行更新。
這樣就結束了一次迭代。當前節點在檢查其相鄰節點之前已從佇列中刪除。
在接下來的迭代中，佇列的前面將是距離為 10 的第二條路徑上的節點，它只有一個距離為 10 的相鄰節點，並且該相鄰節點的距離將從 32767 更新為 10（當前節點距離）+ 10（從當前節點的距離）= 20。
在接下來的迭代中，將檢查成本為 20 的第二條路徑上的節點，它有一個距離為 40 到目標節點的相鄰跳躍，並且目標節點的距離從 32767 更新為 20 + 40 = 60。目標節點的優先順序被更新。
在接下來的迭代中，最短路徑節點將是成本為 30 的第一條路徑上的節點，目標節點還沒有從佇列中刪除。它也與目標節點相鄰，總距離成本為 30 + 10 = 40。
由於 40 小於 60（目標節點先前計算的距離），因此目標節點距離被更新為 40，目標節點的先前指標被更新為第一條路徑上的節點。
在最後一次迭代中，最短路徑節點是目標節點，迴圈退出。
從目標節點開始檢視先前指標，可以將最短路徑反向構建為指向起點的一個列表。
鑑於上述示例，節點和演算法需要什麼樣的資料結構？
# author, copyright under GFDL
class Node :
def __init__(self, label, distance = 32767 ):
# a bug in constructor, uses a shared map initializer
#, adjacency_distance_map = {} ):
self.label = label
self.adjacent = {} # this is an adjacency map, with keys nodes, and values the adjacent distance
self.distance = distance # this is the updated distance from the start node, used as the node's priority
# default distance is 32767
self.shortest_previous = None #this the last shortest distance adjacent node
# the logic is that the last adjacent distance added is recorded, for any distances of the same node added
def add_adjacent(self, local_distance, node):
self.adjacent[node]=local_distance
print "adjacency to ", self.label, " of ", self.adjacent[node], " to ", \
node.label
def get_adjacent(self) :
return self.adjacent.iteritems()
def update_shortest( self, node):
new_distance = node.adjacent[self] + node.distance
#DEBUG
print "for node ", node.label, " updating ", self.label, \
" with distance ", node.distance, \
" and adjacent distance ", node.adjacent[self]
updated = False
# node's adjacency map gives the adjacent distance for this node
# the new distance for the path to this (self)node is the adjacent distance plus the other node's distance
if new_distance < self.distance :
# if it is the shortest distance then record the distance, and make the previous node that node
self.distance = new_distance
self.shortest_previous= node
updated = True
return updated
MAX_IN_PQ = 100000
class PQ:
def __init__(self, sign = -1 ):
self.q = [None ] * MAX_IN_PQ # make the array preallocated
self.sign = sign # a negative sign is a minimum priority queue
self.end = 1 # this is the next slot of the array (self.q) to be used,
self.map = {}
def insert( self, priority, data):
self.q[self.end] = (priority, data)
# sift up after insert
p = self.end
self.end = self.end + 1
self.sift_up(p)
def sift_up(self, p):
# p is the current node's position
# q[p][0] is the priority, q[p][1] is the item or node
# while the parent exists ( p >= 1), and parent's priority is less than the current node's priority
while p / 2 != 0 and self.q[p/2][0]*self.sign < self.q[p][0]*self.sign:
# swap the parent and the current node, and make the current node's position the parent's position
tmp = self.q[p]
self.q[p] = self.q[p/2]
self.q[p/2] = tmp
self.map[self.q[p][1]] = p
p = p/2
# this map's the node to the position in the priority queue
self.map[self.q[p][1]] = p
return p
def remove_top(self):
if self.end == 1 :
return (-1, None)
(priority, node) = self.q[1]
# put the end of the heap at the top of the heap, and sift it down to adjust the heap
# after the heap's top has been removed. this takes log2(N) time, where N iis the size of the heap.
self.q[1] = self.q[self.end-1]
self.end = self.end - 1
self.sift_down(1)
return (priority, node)
def sift_down(self, p):
while 1:
l = p * 2
# if the left child's position is more than the size of the heap,
# then left and right children don't exist
if ( l > self.end) :
break
r= l + 1
# the selected child node should have the greatest priority
t = l
if r < self.end and self.q[r][0]*self.sign > self.q[l][0]*self.sign :
t = r
print "checking for sift down of ", self.q[p][1].label, self.q[p][0], " vs child ", self.q[t][1].label, self.q[t][0]
# if the selected child with the greatest priority has a higher priority than the current node
if self.q[t] [0] * self. sign > self.q [p] [0] * self.sign :
# swap the current node with that child, and update the mapping of the child node to its new position
tmp = self. q [ t ]
self. q [ t ] = self.q [ p ]
self. q [ p ] = tmp
self.map [ tmp [1 ] ] = p
p = t
else: break # end the swap if the greatest priority child has a lesser priority than the current node
# after the sift down, update the new position of the current node.
self.map [ self.q[p][1] ] = p
return p
def update_priority(self, priority, data ) :
p = self. map[ data ]
print "priority prior update", p, "for priority", priority, " previous priority", self.q[p][0]
if p is None :
return -1
self.q[p] = (priority, self.q[p][1])
p = self.sift_up(p)
p = self.sift_down(p)
print "updated ", self.q[p][1].label, p, "priority now ", self.q[p][0]
return p
class NoPathToTargetNode ( BaseException):
pass
def test_1() :
st = Node('start', 0)
p1a = Node('p1a')
p1b = Node('p1b')
p2a = Node('p2a')
p2b = Node('p2b')
p2c = Node('p2c')
p2d = Node('p2d')
targ = Node('target')
st.add_adjacent ( 30, p1a)
#st.add_adjacent ( 10, p2a)
st.add_adjacent ( 20, p2a)
#p1a.add_adjacent(10, targ)
p1a.add_adjacent(40, targ)
p1a.add_adjacent(10, p1b)
p1b.add_adjacent(10, targ)
# testing alternative
#p1b.add_adjacent(20, targ)
p2a.add_adjacent(10, p2b)
p2b.add_adjacent(5,p2c)
p2c.add_adjacent(5,p2d)
#p2d.add_adjacent(5,targ)
#chooses the alternate path
p2d.add_adjacent(15,targ)
pq = PQ()
# st.distance is 0, but the other's have default starting distance 32767
pq.insert( st.distance, st)
pq.insert( p1a.distance, p1a)
pq.insert( p2a.distance, p2a)
pq.insert( p2b.distance, p2b)
pq.insert(targ.distance, targ)
pq.insert( p2c.distance, p2c)
pq.insert( p2d.distance, p2d)
pq.insert(p1b.distance, p1b)
node = None
while node != targ :
(pr, node ) = pq.remove_top()
#debug
print "node ", node.label, " removed from top "
if node is None:
print "target node not in queue"
raise
elif pr == 32767:
print "max distance encountered so no further nodes updated. No path to target node."
raise NoPathToTargetNode
# update the distance to the start node using this node's distance to all of the nodes adjacent to it, and update its priority if
# a shorter distance was found for an adjacent node ( .update_shortest(..) returns true ).
# this is the greedy part of the dijsktra's algorithm, always greedy for the shortest distance using the priority queue.
for adj_node, dist in node.get_adjacent():
#debug
print "updating adjacency from ", node.label, " to ", adj_node.label
if adj_node.update_shortest( node ):
pq.update_priority( adj_node.distance, adj_node)
print "node and targ ", node, targ, node <> targ
print "length of path", targ.distance
print " shortest path"
#create a reverse list from the target node, through the shortes path nodes to the start node
node = targ
path = []
while node <> None :
path.append(node)
node = node. shortest_previous
for node in reversed(path): # new iterator version of list.reverse()
print node.label
if __name__ == "__main__":
test_1()
最小生成樹
[edit | edit source]貪婪地尋找最小權重邊；這可以透過將邊按升序權重排序到列表中來實現。兩種著名的演算法是普里姆演算法和克魯斯卡爾演算法。克魯斯卡爾演算法選擇下一個最小權重邊，前提是不會在生成的更新圖中形成迴圈。普里姆演算法選擇最小權重邊，前提是隻有與樹連線的一條邊。對於這兩種演算法，大部分工作將用於驗證所檢查的邊是否符合主要條件。在克魯斯卡爾演算法中，必須對候選邊進行搜尋和標記技術。這將導致對所有已選擇的連線邊進行搜尋，如果遇到標記邊，則表示已形成迴圈。在普里姆演算法中，將把候選邊與當前選擇的邊的列表進行比較，該列表可以在符號表中按頂點編號進行鍵控，如果兩個端點都找到，則拒絕候選邊。
加權圖中的最大流
[edit | edit source]在流量圖中，邊具有正向容量、方向以及該方向上的流量量（小於或等於正向容量）。剩餘容量是容量減去該方向上的流量，以及反方向上的流量。
福特-富克森方法中的最大流需要一個步驟來搜尋從源點到匯點的可行路徑，該路徑在每一步都具有非零剩餘容量。然後，最小剩餘容量決定了這條路徑的最大流量。可以使用 BFS 進行多次搜尋迭代（埃德蒙茲-卡普演算法），直到在最後一個節點離開佇列或堆疊時，匯點沒有被標記。最後一次迭代中所有標記的節點被稱為最小割。
以下是使用 BFS 實現福特-富克森方法的兩個 Java 示例。第一個使用對映將頂點對映到輸入邊，而第二個避免使用 Collections 型別的 Map 和 List，而是透過計算指向頂點的邊的數量，然後為每個邊陣列（按頂點編號索引）分配空間，並使用一個基本列表節點類來實現 BFS 的佇列。
對於這兩個程式，輸入是“頂點_1，頂點_2，容量”形式的行，輸出是“頂點_1，頂點_2，容量，流量”形式的行，它們描述了初始和最終的流量圖。
// copyright GFDL and CC-BY-SA
package test.ff;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class Main {
public static void main(String[] args) throws IOException {
System.err.print("Hello World\n");
final String filename = args[0];
BufferedReader br = new BufferedReader( new FileReader(filename));
String line;
ArrayList<String[]> lines = new ArrayList<>();
while ((line= br.readLine()) != null) {
String[] toks = line.split("\\s+");
if (toks.length == 3)
lines.add(toks);
for (String tok : toks) {
System.out.print(tok);
System.out.print("-");
}
System.out.println("");
}
int [][]edges = new int[lines.size()][4];
// edges, 0 is from-vertex, 1 is to-vertex, 2 is capacity, 3 is flow
for (int i = 0; i < edges.length; ++i)
for (int j =0; j < 3; ++j)
edges[i][j] = Integer.parseInt(lines.get(i)[j]);
Map<Integer, List<int[]>> edgeMap = new HashMap<>();
// add both ends into edge map for each edge
int last = -1;
for (int i = 0; i < edges.length; ++i)
for (int j = 0; j < 2; ++j) {
edgeMap.put(edges[i][j],
edgeMap.getOrDefault(edges[i][j],
new LinkedList<int[]>()) );
edgeMap.get(edges[i][j]).add(edges[i]);
// find the highest numbered vertex, which will be the sink.
if ( edges[i][j] > last )
last = edges[i][j];
}
while(true) {
boolean[] visited = new boolean[edgeMap.size()];
int[] previous = new int[edgeMap.size()];
int[][] edgeTo = new int[edgeMap.size()][];
LinkedList<Integer> q = new LinkedList<>();
q.addLast(0);
int v = 0;
while (!q.isEmpty()) {
v = q.removeFirst();
visited[v] = true;
if (v == last)
break;
int prevQsize = q.size();
for ( int[] edge: edgeMap.get(v)) {
if (v == edge[0] &&
!visited[edge[1]] &&
edge[2]-edge[3] > 0)
q.addLast(edge[1]);
else if( v == edge[1] &&
!visited[edge[0]] &&
edge[3] > 0 )
q.addLast(edge[0]);
else
continue;
edgeTo[q.getLast()] = edge;
}
for (int i = prevQsize; i < q.size(); ++i) {
previous[q.get(i)] = v;
}
}
if ( v == last) {
int a = v;
int b = v;
int smallest = Integer.MAX_VALUE;
while (a != 0) {
// get the path by following previous,
// also find the smallest forward capacity
a = previous[b];
int[] edge = edgeTo[b];
if ( a == edge[0] && edge[2]-edge[3] < smallest)
smallest = edge[2]-edge[3];
else if (a == edge[1] && edge[3] < smallest )
smallest = edge[3];
b = a;
}
// fill the capacity along the path to the smallest
b = last; a = last;
while ( a != 0) {
a = previous[b];
int[] edge = edgeTo[b];
if ( a == edge[0] )
edge[3] = edge[3] + smallest;
else
edge[3] = edge[3] - smallest;
b = a;
}
} else {
// v != last, so no path found
// max flow reached
break;
}
}
for ( int[] edge: edges) {
for ( int j = 0; j < 4; ++j)
System.out.printf("%d-",edge[j]);
System.out.println();
}
}
}
// copyright GFDL and CC-BY-SA
package test.ff2;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
public class MainFFArray {
static class Node {
public Node(int i) {
v = i;
}
int v;
Node next;
}
public static void main(String[] args) throws IOException {
System.err.print("Hello World\n");
final String filename = args[0];
BufferedReader br = new BufferedReader(new FileReader(filename));
String line;
ArrayList<String[]> lines = new ArrayList<>();
while ((line = br.readLine()) != null) {
String[] toks = line.split("\\s+");
if (toks.length == 3)
lines.add(toks);
for (String tok : toks) {
System.out.print(tok);
System.out.print("-");
}
System.out.println("");
}
int[][] edges = new int[lines.size()][4];
for (int i = 0; i < edges.length; ++i)
for (int j = 0; j < 3; ++j)
edges[i][j] = Integer.parseInt(lines.get(i)[j]);
int last = 0;
for (int[] edge : edges) {
for (int j = 0; j < 2; ++j)
if (edge[j] > last)
last = edge[j];
}
int[] ne = new int[last + 1];
for (int[] edge : edges)
for (int j = 0; j < 2; ++j)
++ne[edge[j]];
int[][][] edgeFrom = new int[last + 1][][];
for (int i = 0; i < last + 1; ++i)
edgeFrom[i] = new int[ne[i]][];
int[] ie = new int[last + 1];
for (int[] edge : edges)
for (int j = 0; j < 2; ++j)
edgeFrom[edge[j]][ie[edge[j]]++] = edge;
while (true) {
Node head = new Node(0);
Node tail = head;
int[] previous = new int[last + 1];
for (int i = 0; i < last + 1; ++i)
previous[i] = -1;
int[][] pathEdge = new int[last + 1][];
while (head != null ) {
int v = head.v;
if (v==last)break;
int[][] edgesFrom = edgeFrom[v];
for (int[] edge : edgesFrom) {
int nv = -1;
if (edge[0] == v && previous[edge[1]] == -1 && edge[2] - edge[3] > 0)
nv = edge[1];
else if (edge[1] == v && previous[edge[0]] == -1 && edge[3] > 0)
nv = edge[0];
else
continue;
Node node = new Node(nv);
previous[nv]=v;
pathEdge[nv]=edge;
tail.next = node;
tail = tail.next;
}
head = head.next;
}
if (head == null)
break;
int v = last;
int minCapacity = Integer.MAX_VALUE;
while (v != 0) {
int fv = previous[v];
int[] edge = pathEdge[v];
if (edge[0] == fv && minCapacity > edge[2] - edge[3])
minCapacity = edge[2] - edge[3];
else if (edge[1] == fv && minCapacity > edge[3])
minCapacity = edge[3];
v = fv;
}
v = last;
while (v != 0) {
int fv = previous[v];
int[] edge = pathEdge[v];
if (edge[0] == fv)
edge[3] += minCapacity;
else if (edge[1] == fv)
edge[3] -= minCapacity;
v = fv;
}
}
for (int[] edge : edges) {
for (int j = 0; j < 4; ++j)
System.out.printf("%d-", edge[j]);
System.out.println();
}
}
}
