Python-Divide-and-Conquer-Methode zum Ermitteln des lokalen Spitzenwerts des zweidimensionalen array_python

Im Folgenden werde ich einen Artikel über die Python-Divide-and-Conquer-Methode zum Ermitteln des lokalen Spitzenwerts eines zweidimensionalen Arrays veröffentlichen. Sie hat einen guten Referenzwert und ich hoffe, dass sie für alle hilfreich ist. Werfen wir gemeinsam einen Blick darauf

Die Bedeutung der Frage besteht grob darin, einen lokalen Peak in einem zweidimensionalen n*m-Array zu finden. Der Spitzenwert muss größer sein als die vier benachbarten Elemente (außerhalb der Array-Grenze wird dies als negative Unendlichkeit angesehen. Wenn wir beispielsweise schließlich den Spitzenwert A[j][i] finden, dann ist A[j][i). ] > A[j+1][i] && A[j][i] > A[j][i] > && A[j][i] > A[j][i-1]. Gibt die Koordinaten und den Wert dieses Peaks zurück.

Der einfachste und direkteste Weg besteht natürlich darin, alle Array-Elemente zu durchlaufen, um festzustellen, ob es sich um Spitzenwerte handelt.

Und dann ein wenig optimieren Mehr, um den Maximalwert jeder Zeile (Spalte) zu ermitteln, und dann den Spitzenwert der Maximalwertspalte mithilfe der Dichotomiemethode zu ermitteln (die spezifische Methode kann in einem eindimensionalen Array gefunden werden, um den Spitzenwert zu ermitteln). Die Komplexität dieses Algorithmus beträgt O(logn)

Es handelt sich um einen Algorithmus mit einer Komplexität von O(n). Die Algorithmusidee ist in die folgenden Schritte unterteilt:

1. Finden Sie das Wort „田“. Vergleichen Sie unter Einbeziehung der vier Außenkanten und der beiden horizontalen und vertikalen Kanten in der Mitte (der grüne Teil im Bild) deren Größen und ermitteln Sie die Position des Maximalwerts. (7 im Bild)

2. Nachdem Sie den Maximalwert im Wort Tian ermittelt haben, bestimmen Sie, ob dies der Fall ist Wenn dies der Fall ist, geben Sie die Koordinate zurück. Wenn nicht, notieren Sie die maximale Koordinate unter den vier gefundenen benachbarten Punkten. Reduzieren Sie den Bereich durch den Quadranten, in dem sich die Koordinate befindet, und vergleichen Sie das nächste Feldzeichen weiter

3. Wann Wenn der Bereich auf 3 * 3 reduziert wird, wird der lokale Peak definitiv gefunden (oder er wurde möglicherweise schon einmal gefunden)

Warum es in dem von uns gewählten Bereich einen Peak geben muss? Sie können es sich so vorstellen: Zuerst haben wir einen Kreis. Es ist bekannt, dass es mindestens ein Element in einem Kreis gibt, das größer ist als alle Elemente in diesem Kreis. Gibt es also einen Maximalwert in diesem Kreis? ?

Es mag etwas kompliziert sein, aber wenn Sie genauer darüber nachdenken, sollten Sie es verstehen können. Sie können es auch mit einem mathematischen Beweis durch Widerspruch beweisen.

Nachdem wir den Algorithmus verstanden haben, besteht der nächste Schritt darin, den Code zu implementieren. Die Sprache, die ich hier verwende, ist Python (ich bin neu in Python, also verzeihen Sie mir bitte einige Verwendungen, die möglicherweise nicht prägnant genug sind). Beginnen wir mit dem Code:

import numpy as np
def max_sit(*n):     #返回最大元素的位置
 temp = 0
 sit = 0
 for i in range(len(n)):
  if(n[i]>temp):
   temp = n[i]
   sit = i
 return sit
def dp(s1,s2,e1,e2):
 m1 = int((e1-s1)/2)+s1   #row
 m2 = int((e2-s1)/2)+s2   #col
 nub = e1-s1
 temp = 0
 sit_row = 0
 sit_col = 0
 for i in range(nub):
  t = max_sit(list[s1][s2+i],     #第一排
     list[m1][s2+i],     #中间排
     list[e1][s2+i],     #最后排
     list[s1+i][s2],     #第一列
     list[s1+i][m2],     #中间列
     list[s1+i][e2],     #最后列
     temp)
  if(t==6):
   pass
  elif(t==0):
   temp = list[s1][s2+i]
   sit_row = s1
   sit_col = s2+i
  elif(t==1):
   temp = list[m1][s2+i]
   sit_row = m1
   sit_col = s2+i
  elif(t==2):
   temp = list[e1][s2+i]
   sit_row = e1
   sit_col = s2+i
  elif(t==3):
   temp = list[s1+i][s2]
   sit_row = s1+i
   sit_row = s2
  elif(t==4):
   temp = list[s1+i][m2]
   sit_row = s1+i
   sit_col = m2
  elif(t==5):
   temp = list[s1+i][e2]
   sit_row = s1+i
   sit_col = m2
 t = max_sit(list[sit_row][sit_col],   #中
    list[sit_row-1][sit_col],  #上
    list[sit_row+1][sit_col],  #下
    list[sit_row][sit_col-1],  #左
    list[sit_row][sit_col+1])  #右
 if(t==0):
  return [sit_row-1,sit_col-1]
 elif(t==1):
  sit_row-=1
 elif(t==2):
  sit_row+=1
 elif(t==3):
  sit_col-=1
 elif(t==4):
  sit_col+=1
 if(sit_row<m1):
  e1 = m1
 else:
  s1 = m1
 if(sit_col<m2):
  e2 = m2
 else:
  s2 = m2
 return dp(s1,s2,e1,e2)
f = open("demo.txt","r")
list = f.read()
list = list.split("\n")       #对行进行切片
list = ["0 "*len(list)]+list+["0 "*len(list)] #加上下的围墙
for i in range(len(list)):      #对列进行切片
 list[i] = list[i].split()
 list[i] = ["0"]+list[i]+["0"]    #加左右的围墙
list = np.array(list).astype(np.int32)
row_n = len(list)
col_n = len(list[0])
ans_sit = dp(0,0,row_n-1,col_n-1)
print("找到峰值点位于：",ans_sit)
print("该峰值点大小为：",list[ans_sit[0]+1,ans_sit[1]+1])
f.close()

Zunächst wird meine Eingabe in eine TXT-Textdatei geschrieben und per String in ein zweidimensionales Array umgewandelt Informationen zum spezifischen Konvertierungsprozess finden Sie in meinem letzten Blog - Python Konvertieren Sie die Zeichenfolge in ein zweidimensionales Array . (Es ist zu beachten, dass der Satz list.pop() nicht hinzugefügt werden muss, wenn die geteilte Liste in der Windows-Umgebung kein leeres Ende hat.) Einige Änderungen bestehen darin, dass ich eine „0“-Wand um das zweidimensionale Array hinzugefügt habe. Durch das Hinzufügen einer Wand entfällt die Notwendigkeit, Grenzaspekte bei der Beurteilung von Spitzenwerten zu berücksichtigen.

max_sit(*n)-Funktion wird verwendet, um die Position des Maximalwerts unter mehreren Werten zu ermitteln und seine Position zurückzugeben. Die in Python integrierte Max-Funktion kann nur den Maximalwert zurückgeben, daher müssen Sie dies trotzdem tun Schreiben Sie es selbst, *n bedeutet Parameter unbestimmter Länge, da ich diese Funktion beim Vergleich von Feldern und zehn (Beurteilung von Spitzenwerten)

def max_sit(*n):     #返回最大元素的位置
 temp = 0
 sit = 0
 for i in range(len(n)):
  if(n[i]>temp):
   temp = n[i]
   sit = i
 return sit

dp verwenden muss (s1, s2, e1, e2) Die vier Parameter in der Funktion können als startx, starty, endx, endy angesehen werden. Das heißt, wir suchen nach den Koordinatenwerten der oberen linken Ecke und der unteren rechten Ecke des Bereichs.

m1 und m2 sind die Mittelwerte von row bzw. col, also der Mitte des Wortes Tian.

def dp(s1,s2,e1,e2): 
 m1 = int((e1-s1)/2)+s1   #row 
 m2 = int((e2-s1)/2)+s2   #col

Vergleichen Sie die Werte in 3 Zeilen und 3 Spalten, um den Maximalwert zu ermitteln sei ein Quadrat. Wenn es ein Rechteck ist, muss es angepasst werden

 for i in range(nub):
  t = max_sit(list[s1][s2+i],     #第一排
     list[m1][s2+i],     #中间排
     list[e1][s2+i],     #最后排
     list[s1+i][s2],     #第一列
     list[s1+i][m2],     #中间列
     list[s1+i][e2],     #最后列
     temp)
  if(t==6):
   pass
  elif(t==0):
   temp = list[s1][s2+i]
   sit_row = s1
   sit_col = s2+i
  elif(t==1):
   temp = list[m1][s2+i]
   sit_row = m1
   sit_col = s2+i
  elif(t==2):
   temp = list[e1][s2+i]
   sit_row = e1
   sit_col = s2+i
  elif(t==3):
   temp = list[s1+i][s2]
   sit_row = s1+i
   sit_row = s2
  elif(t==4):
   temp = list[s1+i][m2]
   sit_row = s1+i
   sit_row = m2
  elif(t==5):
   temp = list[s1+i][e2]
   sit_row = s1+i
   sit_row = m2

Bestimmen Sie, ob der Maximalwert im Wort Tian ein Spitzenwert ist. und kann den angrenzenden Maximalwert nicht finden

t = max_sit(list[sit_row][sit_col],   #中 
    list[sit_row-1][sit_col],  #上 
    list[sit_row+1][sit_col],  #下 
    list[sit_row][sit_col-1],  #左 
    list[sit_row][sit_col+1])  #右 
 if(t==0): 
  return [sit_row-1,sit_col-1] 
 elif(t==1): 
  sit_row-=1 
 elif(t==2): 
  sit_row+=1 
 elif(t==3): 
  sit_col-=1 
 elif(t==4): 
  sit_col+=1

Den Bereich eingrenzen und rekursiv lösen

 if(sit_row<m1): 
  e1 = m1 
 else: 
  s1 = m1 
 if(sit_col<m2): 
  e2 = m2 
 else: 
  s2 = m2 
 
 return dp(s1,s2,e1,e2)

Okay, die Codeanalyse ist hier im Grunde abgeschlossen. Wenn etwas unklar ist, hinterlassen Sie bitte unten eine Nachricht.

Zusätzlich zu diesem Algorithmus habe ich auch einen Greedy-Algorithmus geschrieben, um dieses Problem zu lösen. Leider ist die Algorithmuskomplexität im schlimmsten Fall immer noch O(n^2), QAQ.

Die allgemeine Idee besteht darin, den größten Punkt unter den vier benachbarten Punkten ausgehend von der mittleren Position zu finden und dann den angrenzenden größten Punkt zu finden. Wenn Sie interessiert sind, werden Sie auf jeden Fall einen Spitzenpunkt finden. Sie können einen Blick darauf werfen. , der obige Code:

#!/usr/bin/python3
def dp(n):
 temp = (str[n],str[n-9],str[n-1],str[n+1],str[n+9])  #中 上 左 右 下
 sit = temp.index(max(temp))
 if(sit==0):
  return str[n]
 elif(sit==1):
  return dp(n-9)
 elif(sit==2):
  return dp(n-1)
 elif(sit==3):
  return dp(n+1)
 else:
  return dp(n+9)
f = open("/home/nancy/桌面/demo.txt","r")
list = f.read()
list = list.replace(" ","").split()  #转换为列表
row = len(list)
col = len(list[0])
str="0"*(col+3)
for x in list:      #加围墙 二维变一维
 str+=x+"00"
str+="0"*(col+1)
mid = int(len(str)/2)
print(str,mid)
p = dp(mid)
print (p)
f.close()

Verwandte Empfehlungen:

Python-Array-Suchalgorithmus halbieren Binär Sucheinfügung

Python-Array-Verarbeitungscode für Anfänger

Python-Array-Filter-Implementierungsmethode

Das obige ist der detaillierte Inhalt vonPython-Divide-and-Conquer-Methode zum Ermitteln des lokalen Spitzenwerts des zweidimensionalen array_python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!