算法/贪心算法
< 算法
在回溯算法中，我们看到了找到决策点并对该决策点的所有选项进行递归的算法。贪心算法可以看作是一种回溯算法，在每个决策点，"最佳"选项已经确定，因此可以选择而不必对任何备选选项进行递归。
"贪心"这个名字来源于算法根据单个标准做出决策，而不是进行全局分析，而全局分析会考虑决策对后续步骤的影响。正如我们将看到的，在贪心算法的情况下，这种回溯分析将是不必要的，因此它在意义上并非贪婪，即只为了短期利益而造成伤害。
与回溯算法不同，并非每个问题都能使用贪心算法解决。并非每个问题都"可以"使用贪心算法解决。将找到优化问题的解视为一个爬山问题，贪心算法只能用于在每个点上，选择最陡峭的路径都会通向峰顶的情况。
贪心算法往往非常高效，而且可以相对直接地实现。在许多情况下，其复杂度为 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();
}
}
}
