Python で貪欲アルゴリズムを実装する方法

貪欲アルゴリズムの原則は、問題を解決するときに常にその時点で最善の選択を行うことであることを私たちは知っています。つまり、彼が作ったのは全体最適解を考慮せず、ある意味局所最適解に過ぎなかったのである。貪欲アルゴリズムは、すべての問題に対して全体最適解を取得することはできませんが、広範囲の問題に対して全体最適解、または全体最適解の近似解を生成することができます。

特徴: 貪欲アルゴリズムはトップダウンのアプローチを採用し、反復手法を使用して貪欲な選択を連続的に行います。貪欲な選択が行われるたびに、目的の問題がより小さなサブ問題に単純化されます。問題は解決できる 問題の最適解を得るには、各ステップで局所的な最適解が得られるようにする必要がありますが、結果として得られる全体的な解が必ずしも最適であるとは限らないため、貪欲な方法で後戻りしないでください。貪欲アルゴリズムによって解決できる問題には、通常、貪欲選択プロパティと最適下部構造プロパティという 2 つの重要なプロパティがあります。

質問のようなもの: 一連のアクティビティを指定して、各アクティビティの開始時刻と終了時刻を伝え、参加できるアクティビティの最大数またはアクティビティの開始時刻と終了時刻を計算するよう求めます

貪欲なアルゴリズムのアイデア:

2 つの array を使用します s と f はそれぞれアクティビティの開始時間と終了時間を保存し、同じアクティビティの開始時間のリストに従って非減少アクティビティ シーケンスを実行します。ここでブロガーはバブルソート同期交換を使用します。 例: アクティビティ (1, 4) (2, 3) (3, 5) 次に、アクティビティの開始時間を比較することで

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

を取得します。次のアクティビティと前のアクティビティの終了時刻が決定されます。これら 2 つのアクティビティには互換性がありますか? 開始時刻が終了時刻より大きい場合、それらは互換性があります。それ以外の場合、コードは次のとおりです。 #バブル ソートを使用してください。終了時刻を並べ替えて、対応する開始時刻のリストを取得します

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

これらの事例を読んだ後は、この方法を習得したと思います。さらに興味深い情報については、PHP 中国語 Web サイトの他の関連記事に注目してください。

関連資料:

PHP がスタック データ構造とブラケット マッチング アルゴリズムを実装する方法の詳細なコード例

PHP の最も単純な文字列マッチング アルゴリズム、PHP マッチング アルゴリズム_PHP チュートリアル

最も単純な文字列マッチング アルゴリズムのチュートリアルphp で

以上がPython で貪欲アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。