CODEWITHSUNDEEP
pythonpython-3.xartificial-intelligence
Raheel
Raheel

Reputation: 17

Convert BFS to UCS in python (breadth-first search to uniform cost search)

I am Trying to Covert BFS Program in python to UCS (breadth-first search to uniform cost search) but I have trouble making logic for that I have tried to Sort the Graph but not able to apply UCS completely using my logic

If anyone can help and also guide a little bit how the flow will work and how to tackle this problem

import collections
graph = {
    'A': [('B', 5), ('C', 7)],
    'B': [('A', 5), ('D', 8), ('E', 1)],
    'E': [('B', 1), ('D', 2)],
    'D': [('B', 8), ('E', 2), ('F', 7), ('C', 2), ('I', 5)],
    'F': [('D', 7)],
    'I': [('D', 5), ('G', 14)],
    'G': [('I', 14), ('C', 13)],
    'C': [('A', 7), ('D', 2), ('G', 13)]}


def path_cost(path):
    total_cost = 0
    for (node, cost) in path:
        total_cost += cost
    return total_cost, path[-1][0]

def UCS(graph , startingnode ,goal):
    #cost = 0

    queue = [[(startingnode, 0)]]
    visited = []
    while queue:
        for v in graph.values():
            v.sort(key=lambda x: x[1])
        print(graph.values())

        node = queue[-1][0]
        if node in visited:
            continue
        visited.append(node)
        if node == goal:
            return path
        else:
            adjacent_nodes = graph.get(node , [])
            for (node2 , cost) in adjacent_nodes:
                new_path = path.copy()
                new_path.append([node2 , cost])
                queue.append(new_path)


UCS(graph , 'A' , 'G')

Upvotes: 0

Views: 1009

Answers (1)

Nabcellent
Nabcellent

Reputation: 26

graph = {
    'A': [('B', 5), ('C', 7)],
    'B': [('A', 5), ('D', 8), ('E', 1)],
    'E': [('B', 1), ('D', 2)],
    'D': [('B', 8), ('E', 2), ('F', 7), ('C', 2), ('I', 5)],
    'F': [('D', 7)],
    'I': [('D', 5), ('G', 14)],
    'G': [('I', 14), ('C', 13)],
    'C': [('A', 7), ('D', 2), ('G', 13)]}


def path_cost(path):
    total_cost = 0
    for (node, cost) in path:
        total_cost += cost
    return total_cost, path[-1][0]


def ucs(graph, start, goal):
    queue = [[(start, 0)]]
    visited = []

    while queue:
        queue.sort(key=path_cost)
        path = queue.pop(0)
        node = path[-1][0]

        if node in visited:
            continue

        visited.append(node)

        if node == goal:
            print(path)
            return path
        else:
            adjacent_nodes = graph.get(node, [])
            for (node2, cost) in adjacent_nodes:
                new_path = path.copy()
                new_path.append([node2, cost])
                queue.append(new_path)


ucs(graph, 'A', 'G')

Upvotes: 1

Related Questions