折腾来折腾去

pikipity的blog

Algorithms: Design and Analysis Part 1 -- Programming Questions (Week3)

这里主要记录下来在 “Algorithms: Design and Analysis Part 1” 的Programming Questions 中的算法、实现和作业中的困难。我是用的是 Python。Week 2 Programming Question 在这里Week 3 Programming Question 的题目可以到这里查看作业用到的数据可以到这里下载

第三周,作业要求使用 “randomized contraction algorithm” 来解决 “min cut” 问题。当我们将图上所有的点划分为两大类的时候,如果一个边的两个端点分别属于两个大类,这一个边被我们称为 “cut"。"min cut” 问题就是找到一种分类方法,使得 “cut” 的数量最少。这里这份文档,将如何使用 “Karger’s Min Cut Algorithm” (也就是题目要求使用的方法)解释的非常清楚,但是是英文的,我就挑其中的重点翻译一下。

这个 “Karger’s Min Cut Algorithm” 非常简单,基本分为以下步骤:

  1. 随机选择一个边;
  2. 将选定的边的两个端点合并;
  3. 重复步骤1、2,直到只剩两个点,此两点之间的边就是 cut;
  4. 重复步骤1、2、3,直到找到 min cut。

以下图为例,如果要找到其 min cut,需要进行以下步骤:

Example of min cut

  1. 随机选择一个边,例如 b-f,将 b 和 f 合并,得到下图。注意:当两个点合并之后,只有这两个点之间的边消失,其他边依然存在,比如 a-bf 和 e-bf 都是两个边。

    Step 1

  2. 再随机选择一个边,例如 g-h ,将 g 和 h 合并,得到下图。

    Step 2

  3. 再随机选择一个边,例如 d-g,合并 d 和 g,由于 g 已经与 h 合并,所以得到下图。

    Step 3

  4. 再随机选择一个边,例如 a-e,合并 a 和 e,得到下图。

    Step 4

  5. 随机选择一个边,例如 a-b,合并 a 和 b,得到下图。

    Step 5

  6. 随机选择一个边,例如 c-d,合并 c-d,得到下图。

    Step 6

以上是一个循环,cut 数量为2。由于每次都是随机选择边,所以无法保证一次就得到最少的 cut 数量,所以要将以上的步骤循环多次,随着次数的增多,就可以找到 min cut 了。

这个算法很简单,难点是如何实现。我的程序中,每一次合并点都需要更新整幅图,比较耗费资源,如果有更好的实现方法,欢迎讨论。每一次循环的基本思路如下:

1
2
3
4
5
6
7
Repeat until there are only two points:
  choose first point "a"
  choose second point "b" from connections of "a"
  change all "b" to "a" in current graph
  move connections of "b" to "a"
  remove self-connection
  remove "b" point

Python 代码如下,我代码中,总共循环了50次,:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# -*- coding: utf-8 -*-
import random
import copy

def Choose_first_point(Points):
    # Choose one point from Points
    L=len(Points)
    index=random.choice(range(0,L))
    point=Points[index]
    return index, point
    
def Choose_second_point(first_index,first_point,Graph,Points):
    # Choose second point from Graph based on first_point
    second_index,second_point=Choose_first_point(Graph[first_index])
    second_index=Points.index(second_point)
    return second_index,second_point
    
def Cal_Min_Cut(Points,Graph):
    if len(Graph)==2:
        return len(Graph[0])
    # Choose silde
    Index=[0,0]
    Silde=[0,0]
    Index[0],Silde[0]=Choose_first_point(Points)
    Index[1],Silde[1]=Choose_second_point(Index[0],Silde[0],Graph,Points)
    # Change all second index to first index
    for i in Graph[Index[1]]:
        index_i=Points.index(i)
        while 1:
            try: 
                index=Graph[index_i].index(Silde[1])
            except ValueError:
                break
            else:
                Graph[index_i][index]=Silde[0]
    # Combine second point to first point
    Points.pop(Points.index(Silde[1]))
    Graph[Index[0]]=Graph[Index[0]]+Graph[Index[1]]
    # Remove self-silde
    i=0
    while 1:
        try: 
            k=Graph[Index[0]][i]
        except IndexError:
            break
        else:
            if k==Silde[0]:
                Graph[Index[0]].pop(i)
            else:
                i+=1
    Graph.pop(Index[1])
    # Continue
    return Cal_Min_Cut(Points,Graph)                                 
    



# Read File
file="KargerMinCut.txt"
f=open(file)
InGraph=[]
InPoints=[]
while 1:
    line=f.readline()
    if not line:
        break
    else:
        line=map(int,line.split())
        InPoints.append(line.pop(0))
        InGraph.append(line)

# Find min cut number
N=50
Num=''
while N>=0:
    Points=copy.deepcopy(InPoints)
    Graph=copy.deepcopy(InGraph)
    print ""
    temp=Cal_Min_Cut(Points,Graph)
    if temp<Num:
        Num=temp
    print "iteration "+str(N)
    print "current cut: "+str(temp)
    print "min cut: "+str(Num)
    N-=1

答案是17



Comments