【算法设计与分析】最近点对问题蛮力法破解及可视化绘图显示

本文针对本课程内容上机实验一进行预习，通过python的matplotlib库提供一个可能的可视化显示代码运算的方式。

由于之前便已经发觉到了Python画图的优势，故尝试通过Python来进行算法的给出以及可视化展示。（很明显是因为Python画图方便才使用的，算法还是建议用C/C++来进行实现）

蛮力法的代码实现很简单，遍历数对，找到最近的点。

难点在于多线程的学习以及可视化的操作，由于对Python的多线程不熟悉，多少也走了一些弯路。其中关键部分是通过线程间通讯传递所要可视化展示的点和连线。
代码流程如下：

下面是代码，含有被我注释起来的单独的绘图多线程函数，可供使用：

###############################
# Created by DDD for AlgorithmTest
###############################
import time
import matplotlib.pyplot as plt
import random
import threading
from multiprocessing import Queue


class ClosestPoints(threading.Thread):  # 选择最近点算法，蛮力法
    def __init__(self, arg1, arg2, arg3):
        super().__init__()
        self.arg1 = arg1
        self.arg2 = arg2
        self.arg3 = arg3

    def run(self):
        global closetp1, closetp2, closetd  # 全局变量，用于主函数打印结果
        closetp1, closetyp2, closetd = -1, -1, -1
        index1, index2, d, minDist = -1, -1, 0, 1000
        for i in range(0, self.arg3):
            for j in range(i + 1, self.arg3):
                q.put((self.arg1[i], self.arg1[j], self.arg2[i], self.arg2[j], False))
                d = (self.arg1[i] - self.arg1[j]) ** 2 + (self.arg2[i] - self.arg2[j]) ** 2
                if d < minDist:
                    minDist = d
                    index1, index2 = i, j
                time.sleep(1)
        q.put((self.arg1[index1], self.arg1[index2], self.arg2[index1], self.arg2[index2], True))
        closetp1, closetp2 = index1, index2
        closetd = minDist


# 此处下面为多进程下实现的绘图可视化，由于多进程使用plot时会产生报错，因而移到了主函数中
"""
class Draw(threading.Thread):
    def __init__(self, argx, argy):
        super().__init__()
        self.argx = argx
        self.argy = argy
        plt.show()

    def run(self):
        while True:
            x1, x2, y1, y2, flag = q.get()
            plt.clf()
            pointx = [x1, x2]
            pointy = [y1, y2]
            plt.scatter(self.argx, self.argy, color='red', marker='o', s=50)
            if not flag:
                plt.plot(pointx, pointy, color='blue')
                plt.draw()  # 刷新图形
                plt.pause(1)  # 暂停一段时间，让图形有时间显示出来
            else:
                plt.plot(pointx, pointy, color='yellow')
                plt.draw()  # 刷新图形
                plt.pause(1)  # 暂停一段时间，让图形有时间显示出来
                time.sleep(2)
                break
"""

# 下面是随机生成点的语句
num = 30             # 生成num个点
pointsNumMax = 10   # num个点取值在0~pointsNumMax之间

x = [random.uniform(0, pointsNumMax) for _ in range(num)]       # 这句是生成浮点型的x轴坐标
# x = [random.randint(0, pointsNum) for _ in range(num)]           # 这句是生成整形的x轴坐标
y = [random.uniform(0, pointsNumMax) for _ in range(num)]
# y = [random.randint(0, pointsNum) for _ in range(num)]
point = list(zip(x, y))                                         # 这句将两个坐标包装成一个点
print(point)
# 下面是多进程的设置
q = Queue()     # 用于进程间通讯
t1 = ClosestPoints(x, y, num)

t1.start()

plt.show()
while True:
    x1, x2, y1, y2, flag = q.get()
    plt.clf()       # 清除画布
    pointx = [x1, x2]
    pointy = [y1, y2]
    plt.scatter(x, y, color='red', marker='o', s=50)
    if not flag:
        plt.plot(pointx, pointy, color='blue')
        plt.draw()  # 刷新图形
        plt.pause(1)  # 暂停一段时间，让图形有时间显示出来
    else:           # 连接最近的点，并展示两秒
        plt.plot(pointx, pointy, color='yellow')
        plt.draw()  # 刷新图形
        plt.pause(1)  # 暂停一段时间，让图形有时间显示出来
        time.sleep(2)
        break

t1.join()       # 监听进程t1是否结束
print("已执行完毕")
print("最近的两个点是{}（{}，{}）和{}（{}，{}）".format(closetp1, point[closetp1][0], point[closetp1][1], closetp2,
                                                  point[closetp2][0], point[closetp2][1]))
print("最近距离是{}".format(closetd))
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

文尽于此，本文使用Markdown编辑。