Algorithm Design Principle - Greedy Algorithm & Dynamic Programming

 

Metode/Algoritma Greedy merupakan algoritma yang membentuk soslusi langkah-langkah perlangkah. Pada setiap langkah akan diputusakan yang paling optimal. Keputusan tersebut tidak perlu memperhatikan keputusan selanjutnya yang akan diambil, dan keputusan tersebut tidak dapat diubah lagi pada langkah selanjutnya.

Prinsip algoritma greedy

Prinsip utama algoritma greedy adalah “take what you can get now” maksud dari prinsip tersebu adalah pada setiap langkah algoritma greedy kita ambil keputusan yang paling optimal untuk langkah tersebut tampa memperhatikan konsekuensi pada langkah selanjutnya. Kita namakan solusi tersebut dengan optimal local. Kemudian saat pengambilan nilai optimum local pada setiap langkah, diharapkan tercapai optimum global, yaitu tercapainya solusi optimum yang melibatkan keseluruhan langkah dari awal sampe akhir

DAG = {'A': {'C': 4, 'G': 9},

'G': {'E': 6},

'C': {'D': 6, 'H': 12},

'D': {'E': 7},

'H': {'F': 15},

'E': {'F': 8},

'F': {'B': 5}}

def shortest_path(graph, asal, tujuan):

result = []

result.append(asal)

while tujuan not in result:

current_node = result[-1]local_max = min(graph[current_node].values())

for node, weight in graph[current_node].items():

if weight == local_max:

result.append(node)