Trong bài này mình sẽ nói chi tiết hơn về ví dụ tìm khoảng cách ngắn nhất từ một điểm đến một đoạn thẳng. Tôi sẽ đi từng bước một cho đến khi nhận được kết quả như trong hình 1
Cách tính khoảng cách giữa hai điểm
Tôi bắt đầu hướng dẫn này bằng một câu hỏi, làm cách nào để tìm khoảng cách giữa hai điểm? . Khoảng cách Euclide được sử dụng phổ biến nhất để tính toán đường thẳng giữa hai điểm trên hệ tọa độ Descartes. Khoảng cách Euclide có thể được tính bằng phương trình bên dưới. \[d=\sqrt{[x_1-x_2]^2+[y_1-y_2]^2} \]
Trong triển khai Tìm kiếm Phần Vàng, việc tính toán khoảng cách sẽ được thực hiện trong mỗi lần lặp cho từng điểm bên trong $x_1$ và $x_2$. Đó là lý do tại sao trong hình 1, chúng ta có thể thấy hai đường màu đỏ từ một điểm xác định màu xanh bên ngoài đường thẳng đến mỗi điểm bên trong. Quá trình lặp sẽ tiếp tục và dừng khi đạt đến giá trị lỗi ngưỡng. Giá trị ngưỡng thực sự nhỏ như 0. 05 để đảm bảo sự khác biệt giữa hai khoảng cách thực sự nhỏ ở độ chính xác dài hoặc thậm chí giống nhau ở độ chính xác ngắn hơn
Triển khai Giải pháp bằng Python
Bây giờ hãy làm điều đó trong Python. Đầu tiên chúng ta cần nhập một số thư viện cần thiết, chẳng hạn như. numpy, matplotlib, thời gian và IPython
#IMPORTING REQUIRED LIBRARIES %matplotlib inline import numpy as np import matplotlib.pyplot as plt from IPython.display import clear_output import time
Vì chúng ta đang làm việc với một dòng, chúng ta cần xác định hàm của dòng. Một chức năng cho một dòng có thể được thể hiện như. $f[x]=mx+b$. Trong đó $x$ là biến đầu vào, $m$ là hệ số góc và $b$ là hằng số
Độ dốc có thể được tính theo phương trình sau. \[m=\frac{y_2-y_1}{x_2-x_1} \] Sau đó, $b$ có thể được tìm thấy bằng cách thay giá trị của $y_1$ và $x_1$ hoặc $y_1$ và $x_1$ thành $f[
Dưới đây là hàm tính hệ số góc $m$ và $b$ với 4 biến đầu vào $x_1$,$y_1$ và $x_2$,$y_2$ là tọa độ đầu và cuối của một đoạn thẳng
def line_func[x1,x2,y1,y2]: m=[y2-y1]/[x2-x1] b=y1-[m*x1] return m,b
Sau khi nhận được $m$ và $b$, sau đó chúng tôi sử dụng nó để tính toán $f[x]$ hoặc $y$. Đối với điều này, chúng tôi tạo ra một chức năng để tính toán nó
def func_fx[m,b,x]: fx=m*x+b return fx
Tiếp theo, chúng ta tạo một hàm để tính khoảng cách giữa hai điểm bằng phương trình trên
def distance[x1,y1,x2,y2]: d=np.sqrt[[x1-x2]**2+[y1-y2]**2] return d
Để chọn đúng điểm tối ưu ta phải biết vị trí của các điểm trong với nhau. Đối với điều này, chúng tôi tạo một chức năng được gọi là check_pos. Nếu $x_1$ lớn hơn $x_2$, điều đó có nghĩa là $x_1$ ở bên phải của $x_2$. Vì điều đó, chúng tôi đưa ra nhãn 'đúng'
def check_pos[x1,x2]: if x2fx1 and label=='right': xl=x2 xu=xu new_x=update_interior[xl,xu] x1=new_x[0] x2=new_x[1] xopt=x1 else: xl=xl xu=x1 new_x=update_interior[xl,xu] x1=new_x[0] x2=new_x[1] xopt=x2 return xl,xu,xopt,fx1,fx2
Cuối cùng, chúng tôi tạo chức năng tìm kiếm vàng với bốn biến đầu vào cụ thể là. ranh giới trên[$x_u$], ranh giới dưới[$x_l$], chế độ [là 'tối thiểu' vì chúng tôi chỉ tìm kiếm giá trị nhỏ nhất] và ngưỡng lỗi[$et$]. Trong hàm còn có lệnh vẽ đồ thị tại dòng 28-34 cho ra đồ thị như hình 1. Phần còn lại của chức năng này là in ra một số kết quả như số lần lặp, giá trị lỗi, khoảng cách và khoảng cách trung bình
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
def golden_search[xl,xu,mode,et]: it=0 e=1 while e>=et: new_x=update_interior[xl,xu] x1=new_x[0] x2=new_x[1] fx1=func_fx[m,b,x1] fx2=func_fx[m,b,x2] label=check_pos[x1,x2] #SELECTING AND UPDATING BOUNDARY-INTERIOR POINTS if mode=='max': new_boundary=find_max[xl,xu,x1,x2,label] elif mode=='min': new_boundary=find_min[xl,xu,x1,x2,label] else: print['Please define min/max mode'] break #exit if mode not min or max xl=new_boundary[0] xu=new_boundary[1] xopt=new_boundary[2] distance_1=new_boundary[3] distance_2=new_boundary[4] mean_distance=[distance_1+distance_2]/2 #PLOTTING clear_output[wait=True] plt.plot[[x_point,x1],[y_point,fx1],'r'] plt.plot[[x_point,x2],[y_point,fx2],'r'] plt.plot[x,y] plt.plot[x_point,y_point,'bo'] plt.axis['equal'] plt.show[] it+=1 print ['Iteration: ',it] r=[np.sqrt[5]-1]/2 #GOLDEN RATIO e=[[1-r]*[abs[[xu-xl]/xopt]]]*100 #Error print['Error:',e] print ['distance 1=',distance_1] print ['distance 2=',distance_2] print['mean distance=',round[mean_distance,3]] time.sleep[1]
Chúng tôi đã tạo tất cả các chức năng cần thiết cho ứng dụng này. Bây giờ hãy chạy nó với đoạn mã sau