So implementieren Sie einen Greedy-Algorithmus mit Python

Wir wissen, dass das Prinzip des Greedy-Algorithmus darin besteht, bei der Lösung eines Problems immer die aktuell beste Wahl zu treffen. Mit anderen Worten, ohne die Berücksichtigung der insgesamt optimalen Lösung war das, was er machte, in gewissem Sinne nur eine lokal optimale Lösung. Der Greedy-Algorithmus kann nicht für alle Probleme die insgesamt optimale Lösung ermitteln, er kann jedoch für eine Vielzahl von Problemen die insgesamt optimale Lösung oder eine Näherungslösung zur insgesamt optimalen Lösung erzeugen.

Funktionen: Der Greedy-Algorithmus verwendet Top-Down- und iterative Methoden, um aufeinanderfolgende Greedy-Entscheidungen zu treffen. Bei jeder Greedy-Auswahl kann das gewünschte Problem in ein kleineres Teilproblem vereinfacht werden Erhalten Sie eine optimale Lösung für das Problem. Obwohl sichergestellt werden muss, dass bei jedem Schritt die lokal optimale Lösung erhalten werden kann, ist die resultierende globale Lösung manchmal nicht unbedingt optimal. Gehen Sie also nicht mit der Greedy-Methode zurück. Probleme, die durch gierige Algorithmen gelöst werden können, haben im Allgemeinen zwei wichtige Eigenschaften: gierige Auswahleigenschaften und optimale Unterstruktureigenschaften.

Beispiel: Geben Sie bei einer Reihe von Aktivitäten die Start- und Endzeit jeder Aktivität an und bitten Sie darum, die maximale Anzahl der Aktivitäten, an denen teilgenommen werden kann, oder die Start- und Endzeit der Aktivität zu berechnen

Idee des Greedy-Algorithmus:

Verwenden Sie zwei Arrays s und f, um die Start- und Endzeiten der Aktivitäten zu speichern und eine nicht abnehmende Aktivitätssequenz für die Aktivitäten durchzuführen Basierend auf der Endzeit der Aktivitäten erfolgt die entsprechende Anpassung, Blogger werden hier synchron durch Blasensortierung ausgetauscht, zum Beispiel: Aktivitäten (1, 4) ( 2, 3) (3, 5) dann erhalten wir

s = [2,1,3]
f = [3,4,5]

Bestimmen Sie durch Vergleich der Startzeit der nächsten Aktivität mit der Endzeit der vorherigen Aktivität, ob Wenn die Startzeit größer als die Endzeit ist, ist sie kompatibel. Andernfalls lautet der Code wie folgt: #Verwenden Sie die Blasensortierung, um die Endzeit zu sortieren und die entsprechende Startzeitliste abzurufen

def bubble_sort(s,f):
  for i in range(len(f)):
    for j in range(0,len(f)-i-1):
      if f[j] > f[j+1]:
        f[j], f[j+1] = f[j+1],f[j]
        s[j],s[j+1] = s[j+1],s[j]
  return s,f
 
def greedy(s,f,n):
  a = [True for x in range(n)]
  #初始选择第一个活动
  j = 0
  for i in range(1,n):
    #如果下一个活动的开始时间大于等于上个活动的结束时间
    if s[i] >= f[j]:
      a[i] = True
      j = i
    else:
      a[i] = False
  return a
 
n = int(input())
arr = input().split()
s = []
f = []
for ar in arr:
  ar = ar[1:-1]
  start = int(ar.split(',')[0])
  end = int(ar.split(',')[1])
  s.append(start)
  f.append(end)
 
s,f = bubble_sort(s,f)
A = greedy(s,f,n)
 
res = []
for k in range(len(A)):
  if A[k]:
    res.append('({},{})'.format(s[k],f[k]))
print(' '.join(res))

Ich glaube, dass Sie die Methode beherrschen, nachdem Sie diese und weitere Fälle gelesen haben. Wie aufregend, bitte achten Sie auf andere verwandte Artikel auf der chinesischen PHP-Website!

Verwandte Lektüre:

Detaillierte Codebeispiele, wie PHP die Stapeldatenstruktur und den Bracket-Matching-Algorithmus implementiert

Am beliebtesten Code in PHP Einfacher String-Matching-Algorithmus, PHP-Matching-Algorithmus_PHP-Tutorial

Das einfachste String-Matching-Algorithmus-Tutorial in PHP

Das obige ist der detaillierte Inhalt vonSo implementieren Sie einen Greedy-Algorithmus mit Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!