Comment implémenter un algorithme glouton en utilisant Python

On sait que le principe de l'algorithme glouton est de toujours faire le meilleur choix du moment lors de la résolution d'un problème. En d’autres termes, sans considérer la solution optimale globale, ce qu’il a fait n’était qu’une solution optimale locale dans un certain sens. L’algorithme glouton ne peut pas obtenir la solution optimale globale pour tous les problèmes, mais il peut produire la solution optimale globale ou une solution approximative de la solution optimale globale pour un large éventail de problèmes.

Caractéristiques : L'algorithme glouton utilise des méthodes descendantes et itératives pour faire des choix gloutons successifs. Chaque fois qu'un choix glouton est fait, le problème souhaité est simplifié en un sous-problème plus petit. À chaque étape, une sélection gloutonne peut être effectuée. obtenir une solution optimale au problème. Bien qu'il soit nécessaire de s'assurer que la solution optimale locale peut être obtenue à chaque étape, la solution globale résultante n'est parfois pas nécessairement optimale, il ne faut donc pas revenir en arrière avec la méthode gloutonne. Les problèmes qui peuvent être résolus par des algorithmes gloutons ont généralement deux propriétés importantes : les propriétés de sélection gloutonnes et les propriétés de sous-structure optimales.

Par exemple : étant donné un ensemble d'activités, indiquez l'heure de début et l'heure de fin de chaque activité, et demandez de calculer le nombre maximum d'activités auxquelles on peut participer ou l'heure de début et de fin de l'activité

Idée d'algorithme gourmand :

Utilisez deux tableaux s et f pour stocker respectivement les heures de début et de fin des activités, et effectuez une séquence d'activité non décroissante pour les activités en fonction de l'heure de fin des activités. La même chose est faite pour la liste des heures de début des activités. Ajustement correspondant, les blogueurs sont ici échangés de manière synchrone via le tri à bulles, par exemple : activités (1, 4) (. 2, 3) (3, 5) alors on obtient

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

En comparant l'heure de début de l'activité suivante avec l'heure de fin de l'activité précédente, déterminer si les deux activités sont compatibles. Si l'heure de début est supérieure à l'heure de fin, alors Compatible, sinon incompatible, le code est le suivant #Utilisez le tri à bulles pour trier les heures de fin, et obtenez la liste des heures de début correspondantes

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))

Je pense que vous maîtrisez la méthode après avoir lu ces cas, et plus encore. Comme c'est excitant, veuillez prêter attention aux autres articles connexes sur le site Web chinois de php !

Lecture connexe :

Exemple de code détaillé de la façon dont PHP implémente la structure de données de pile et l'algorithme de correspondance entre crochets

Le plus populaire code en PHP Algorithme de correspondance de chaînes simple, algorithme de correspondance php_Tutoriel PHP

Le tutoriel d'algorithme de correspondance de chaînes le plus simple en php

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!