Untitled
unknown
plain_text
6 months ago
1.3 kB
7
Indexable
import queue def breadth_first_search_with_heuristics(graph, G1, G2): # Rečnici za čuvanje udaljenosti od G1 i G2 do svakog čvora distance_G1 = {node: float('inf') for node in graph} distance_G2 = {node: float('inf') for node in graph} # BFS za izračunavanje najkraćih udaljenosti od G1 def bfs(start, distance): q = queue.Queue() q.put(start) distance[start] = 0 while not q.empty(): node = q.get() for neighbor, weight in graph[node]: if distance[neighbor] > distance[node] + weight: distance[neighbor] = distance[node] + weight q.put(neighbor) # Pokrećemo BFS za G1 i G2 bfs(G1, distance_G1) bfs(G2, distance_G2) # Kreiramo heuristiku za svaki čvor kao minimalnu udaljenost do G1 ili G2 heuristika = {} for node in graph: heuristika[node] = min(distance_G1[node], distance_G2[node]) return heuristika # Primer grafa za testiranje graph = { 1: [(2, 4), (5, 7)], 2: [(1, 4), (3, 1), (5, 3)], 3: [(2, 1), (4, 3)], 4: [(3, 3), (5, 2)], 5: [(1, 7), (2, 3), (4, 2)] } G1, G2 = 1, 5 heuristika = breadth_first_search_with_heuristics(graph, G1, G2) print("Heuristika za svaki čvor:", heuristika)
Editor is loading...
Leave a Comment