PSC Per.2

Tugas Kelompok Pengantar Sistem Cerdas:
1. Bentuk kelompok dengan jumlah maksimal 5 orang.

2. Siapkan bahan data Jarak spot buat minggu depan, masing- masing kelompok, sudah punya data
Jarak/rute dari masing- masing Spot diarea STMIK Palangkaraya, dengan titik start Kantor STMIK
Palangkaraya.
3. Buat peta Jarak td dari masing- masing spot ke titik start kantor. Minggu depan data tersebut sudah ada
dan tersedia (disiapkan) tiap kelompok.
4. Implementasikan data jarak kedalam algoritma Breadth First Search(BFS), dan Depth Frist
Search(DFS), Greedy, dan a*.
Jawaban:
1. Nama Kelompok :
1) Hari Fitri
2) Muhammad Rafli
3) Rhema Selvia Putri
4) Angella Karismanti
5) Esiska
2.
Algoritma Breadth First Search(BFS)
peta = { 'A': set (['B', 'F']),
'B': set (['A', 'C', 'F']),
'C': set (['B', 'D', 'E']),
'D': set (['C', 'E']),
'E': set (['C', 'D', 'F']),
'F': set (['A', 'B', 'E']),}
def bfs_lintasan_terpendek(peta, mulai, tujuan):

explored = []
queue = [[mulai]]
if mulai == tujuan :
return "Awal adalah Tujuan"
while queue :
jalur = queue.pop(0)
node = jalur[-1]
if node not in explored :

neighbours = peta[node]
for neighbours in neighbours :

jalur_baru = list(jalur)
jalur_baru.append(neighbours)
queue.append(jalur_baru)
if neighbours == tujuan:
return jalur_baru
explored.append(node)
return "Moho maaf node yang kalian pilih tidak ada"

mulai = input("Masukkan awal : ")
tujuan = input("Masukkan akhir : ")
print(bfs_lintasan_terpendek(peta, mulai, tujuan))
Output BFS:
Peta Jalur BFS:
Algoritma Depth Frist Search(DFS).

peta = { 'A': set (['B', 'F']),
'B': set (['A', 'C', 'F']),
'C': set (['B', 'D', 'E']),
'D': set (['C', 'E']),
'E': set (['C', 'D', 'F']),
'F': set (['A', 'B', 'E']),}
def dfs(peta, mulai, tujuan):

stack = [[mulai]]
visited = set()
while stack:
jalur = stack.pop()
node = jalur[-1]
if node not in visited:

neighbours = peta[node]
for neighbours in neighbours:

new_jalur = list(jalur)
new_jalur.append(neighbours)
stack.append(new_jalur)
if neighbours == tujuan:
return new_jalur
visited.add(node)
return None
mulai = 'A'
tujuan = 'D'
jalur = dfs(peta, mulai, tujuan)
if jalur:
print(f"Jalur terpendek dari {mulai} ke {tujuan} adalah:", "->".join(jalur))
else:
print(f"Tidak ada jalur dari {mulai} ke {tujuan}")
Output DFS:
Peta Jalur DFS:
Algoritma Greedy
import sys
class TSPGreedy:
def __init__(self, graph):
self.graph = graph
self.num_nodes = len(graph)
def tsp(self):
visited = [False] * self.num_nodes
# Mulai dari simpul 0
current_node = 0
visited[current_node] = True
path = [current_node]
total_cost = 0
# Pilih simpul berikutnya secara greedy hingga semua simpul dikunjungi

for _ in range(self.num_nodes - 1):
next_node = self.get_next_node(current_node, visited)
path.append(next_node)
total_cost += self.graph[current_node][next_node]
visited[next_node] = True
current_node = next_node
# Kembali ke simpul awal

path.append(path[0])
total_cost += self.graph[current_node][path[0]]
return path, total_cost
def get_next_node(self, current_node, visited):

min_cost = sys.maxsize
next_node = None
for i in range(self.num_nodes):
if not visited[i] and self.graph[current_node][i] < min_cost:
min_cost = self.graph[current_node][i]
next_node = i
return next_node
# Contoh penggunaan
if __name__ == "__main__":
graph = [
[0, 141, 181, 272],
[141, 0, 343, 363],
[181, 363, 0, 343],
[272, 343, 343, 0]
]
tsp_solver = TSPGreedy(graph)
path, total_cost = tsp_solver.tsp()
print("Rute terpendek:", path)
print("Jarak terpendek:", total_cost)
Output Greedy:
Algoritma a*
import heapq
class AStar:
def __init__(self, graph, heuristic):
self.graph = graph
self.num_nodes = len(graph)
self.heuristic = heuristic
def astar(self, start, goal):

frontier = [(0, start)]
came_from = {}
cost_so_far = {start: 0}
while frontier:
_, current_node = heapq.heappop(frontier)
if current_node == goal:
break
for next_node in self.graph[current_node]:

new_cost = cost_so_far[current_node] + self.graph[current_node][next_node]
if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:

cost_so_far[next_node] = new_cost
priority = new_cost + self.heuristic(next_node, goal)
heapq.heappush(frontier, (priority, next_node))
came_from[next_node] = current_node
return self.reconstruct_path(came_from, start, goal)
def reconstruct_path(self, came_from, start, goal):

current_node = goal
path = []
while current_node != start:

path.append(current_node)
current_node = came_from[current_node]
path.append(start)
path.reverse()
return path
# Contoh penggunaan
if __name__ == "__main__":
# Contoh graph
graph = {
'A': {'B': 40, 'C': 131, 'D': 202},
'B': {'A': 40, 'C': 91, 'D': 162, 'E': 182},
'C': {'A': 131, 'B': 91, 'D': 71, 'E': 91},
'D': {'A': 202, 'B': 162, 'C': 71, 'E': 20},
'E': {'B': 182, 'C': 91, 'D': 20}
}
# Fungsi heuristik (jarak Euclidean)

def heuristic(node, goal):
return abs(ord(node) - ord(goal))
# Inisialisasi algoritma A*
astar = AStar(graph, heuristic)
# Pencarian jalur terpendek dari 'A' ke 'E'

start = 'A'
goal = 'E'
shortest_path = astar.astar(start, goal)
print("Jalur terpendek dari", start, "ke", goal, ":", shortest_path)
Output a*:
Algoritma Hill Climbing

import random
def hill_climbing(problem, max_iterations):

current_state = problem.initial_state()
for _ in range(max_iterations):
neighbors = problem.neighbors(current_state)
if not neighbors:
break
next_state = max(neighbors, key=lambda state: problem.value(state))

if problem.value(next_state) <= problem.value(current_state):
break
current_state = next_state
return current_state
# Contoh penggunaan
class Problem:
def initial_state(self):
return random.randint(0, 100)
def value(self, state):

return -abs(state - 50) # Fungsi nilai, mencari nilai paling dekat dengan 50
def neighbors(self, state):

return [state + 1, state - 1]
if __name__ == "__main__":
problem = Problem()
solution = hill_climbing(problem, 10000)
print("Solusi terbaik:", solution)
Output Hill Climbing :

PSC Per.2

Uploaded by

Copyright:

Available Formats

PSC Per.2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

PSC Per.2

Uploaded by

Copyright:

Available Formats

Tugas Kelompok Pengantar Sistem Cerdas:

1. Bentuk kelompok dengan jumlah maksimal 5 orang.

def bfs_lintasan_terpendek(peta, mulai, tujuan):

if node not in explored :

for neighbours in neighbours :

return "Moho maaf node yang kalian pilih tidak ada"

print(bfs_lintasan_terpendek(peta, mulai, tujuan))

Peta Jalur BFS:

Algoritma Depth Frist Search(DFS).

def dfs(peta, mulai, tujuan):

if node not in visited:

for neighbours in neighbours:

Peta Jalur DFS:

# Pilih simpul berikutnya secara greedy hingga semua simpul dikunjungi

# Kembali ke simpul awal

return path, total_cost

def get_next_node(self, current_node, visited):

def astar(self, start, goal):

for next_node in self.graph[current_node]:

if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:

return self.reconstruct_path(came_from, start, goal)

def reconstruct_path(self, came_from, start, goal):

while current_node != start:

# Fungsi heuristik (jarak Euclidean)

# Pencarian jalur terpendek dari 'A' ke 'E'

Algoritma Hill Climbing

def hill_climbing(problem, max_iterations):

next_state = max(neighbors, key=lambda state: problem.value(state))

def value(self, state):

def neighbors(self, state):

Output Hill Climbing :

You might also like