writerq1

A star algorithm은 길찾기 알고리즘으로 유다시티 수업 마지막 프로젝트로도 나왔다.

생각보다 재밌는 알고리즘 이었다.

그리디 알고리즘으로도 길찾기 문제는 해결할 수 있는데, 사실상 효율적이지 않다는 문제가 있다.

start node 중심에서 원형으로 모든 가능성에 대해서 길찾기를 하게 됨으로

방향성을 가지고 길찾기를 할 수 있도록, 알고리즘에 약간의 수정을 해야 한다.

function = g + h

g = cost of the path

h = estimated distance to the goal

위의 function의 값이 최소화가 되는 방향으로 알고리즘을 짜는 문제다. 

아래는 내가 프로젝트로 냈었던 문제다. 피타고라스정리를 이용해서 거리를 계산해가고 있으며

그리디 알고리즘에 h 요소를 집어넣어 문제를 해결할 수 있었다.

def shortest_path(M,start,goal):
    explored = []
    frontiers = {}

    for neighbour in M.roads[start]:
        route = [start, neighbour]
        distance_from_start = math.sqrt((M.intersections[start][0] - M.intersections[neighbour][0])**2 + (M.intersections[start][1] - M.intersections[neighbour][1])**2)
        distance_to_goal = math.sqrt((M.intersections[goal][0] - M.intersections[neighbour][0])**2 + (M.intersections[goal][1] - M.intersections[neighbour][1])**2)
        total_distance = distance_from_start + distance_to_goal
        frontiers[neighbour] = Intersection(route, distance_from_start, distance_to_goal, total_distance)

    explored.append(start)

    while frontiers:
        smallest_frontier = sorted(frontiers.items(), key=lambda x: x[1].total_distance)[0]
        smallest_fron_key = smallest_frontier[0]
        explored.append(smallest_fron_key)
        if smallest_fron_key == goal:
            print("shortest path called")
            return smallest_frontier[1].route

        for neighbour in M.roads[smallest_fron_key]:
            if neighbour not in explored:
                route = smallest_frontier[1].route.append(neighbour)
                distance_from_start = smallest_frontier[1].distance_from_start + math.sqrt(
                    (M.intersections[smallest_fron_key][0] - M.intersections[neighbour][0])**2 + (M.intersections[smallest_fron_key][1] - M.intersections[neighbour][1])**2
                    )
                distance_to_goal = math.sqrt((M.intersections[goal][0] - M.intersections[neighbour][0])**2 + (M.intersections[goal][1] - M.intersections[neighbour][1])**2)
                total_distance = distance_from_start + distance_to_goal
                if frontiers.get(neighbour) != None and total_distance > frontiers[neighbour].total_distance:
                    continue
                frontiers[neighbour] = Intersection(route, distance_from_start, distance_to_goal, total_distance)

    if not frontiers:
        return -1

knapsack Problem

item 마다 weight 과 value가 있고, 정해진 weight limitation 하에 최적의 value를 구하는 문제.

모든 경우의 수를 다 따지려면 2의 n제곱 만큼의 time complexity가 필요하다.

dynamic programming은 문제를 나누어서 접근하는 방법으로 divide and conquere과도 비슷하다.

보통의 경우 lookup table을 두는데,

subproblem에 대한 solution들을 저장해 둔다.

추가 되는 경우의 수마다 최적값을 업데이트 해나가는데,,

내 생각에 이는 greedy 알고리즘과도 비슷하게 느껴졌다.

문제의 핵심은 problem을 subproblem으로 break down 할 수 있느냐는 부분.

def knapsack_max_value(knapsack_max_weight, items):
    
    # Initialize a lookup table to store the maximum value ($) 
    lookup_table = [0] * (knapsack_max_weight + 1)


    # Iterate down the given list
    for item in items:
        
        # The "capcacity" represents amount of remaining capacity (kg) of knapsack at a given moment. 
        for capacity in reversed(range(knapsack_max_weight + 1)):
            
            if item.weight <= capacity:
                lookup_table[capacity] = max(lookup_table[capacity], lookup_table[capacity - item.weight] + item.value)

    return lookup_table[-1]

What is graph

node(or vertex)사이의 관계를 나타낼 수 있는 자료구조.

tree도 graph의 한 종류라고 할 수 있다.

node 사이에는 연결선 (edge)가 존재한다.

graph는 root이 따로 없고, circle형태도 가능하다.

edge역시 data값을 지닐 수 있다. (보통 strength of connection, 예를 들어 거리)

**A star 알고리즘에서처럼 길찾기 알고리즘을 구현할 때 유용한 자료구조.

Directions and cycles

edge는 direction을 지닐 수 있고 아닐 수도 있다. (한방향만으로만 연결된 node)

cycle은 infinite loop의 가능성을 준다.

Connectivity

모든 노드가 edge로 연결되어 있어야 하는 것이 아니기 때문에,

연결이 끊긴 node가 있을 수 있다. disconnected graph.

연결이 끊긴 node끼리 그래프를 만들수도 있다.

최소한으로 몇개의 edge를 끊으면 disconnected graph가 되는지 개수를 세어서,

connectivity의 strength를 체크해볼 수 있다.

Graph representation

Object oriented language 를 사용하는 경우라면 node(vertex)나 edge를 object 형식으로 만들수 있다.

list 형식으로도 관리할 수 있는데

예를 들면 edge list, [[1,3],[2,4],[3,6] .... ]

노드의 아이디넘버를 통해 엣지를 리스트화 하는 방법.

adjacency list

[[1], [0,2,3], [1,3] ...]

리스트의 인덱스가 node 역할을 해서 인접한 노드를 list로 정리하는 방법.

adjacency matrix

3d 형태로 list안에 list를 넣는 방식.

Searching의 경우 tree와 비슷하게 stack와 queue를 활용할 수 있다.

DFS

def dfs_search(root_node, search_value):
    visited = set()                         # Sets are faster for lookups
    stack = [root_node]                     # Start with a given root node
    
    while len(stack) > 0:                   # Repeat until the stack is empty
            
        current_node = stack.pop()          # Pop out a node added recently 
        visited.add(current_node)           # Mark it as visited

        if current_node.value == search_value:
            return current_node

        # Check all the neighbours
        for child in current_node.children:

            # If a node hasn't been visited before, and not available in the stack already.
            if (child not in visited) and (child not in stack):         
                stack.append(child)

BFS

def bfs_search(root_node, search_value):
    visited = set()                           # Sets are faster while lookup. Lists are faster to iterate.
    queue = [root_node]
    
    while len(queue) > 0:
        current_node = queue.pop(0)
        visited.add(current_node)

        if current_node.value == search_value:
            return current_node

        for child in current_node.children:
            if child not in visited:          # Lookup
                queue.append(child)

매 step 마다 최적의 해를 구하면 최종적인 방식도 최적이 되는 재밌는 알고리즘.

매 스텝마다 최적의 해를 구한다는 의미로 greedy라는 표현을 쓴 것 같은데, 곰곰히 들여다볼수록 재미있는 부분이 많다.

코드를 확인해 보면, 결국 매step의 선택이 가장 최선의 선택임을 알 수 있다.

import sys

'''Find the shortest path from the source node to every other node in the given graph'''
def dijkstra(graph, source):
    
    result = {}
    result[source] = 0                 
    
    for node in graph.nodes:
        if (node != source):
            result[node] = sys.maxsize
            
    unvisited = set(graph.nodes)  
    
    path = {}

    '''THE GREEDY APPROACH'''
    # As long as unvisited is non-empty
    while unvisited: 
        min_node = None    
        
        # 1. Find the unvisited node having smallest known distance from the source node.
        for node in unvisited:
            if node in result:
                
                if min_node is None:       
                    min_node = node
                elif result[node] < result[min_node]:
                    min_node = node

        if min_node is None:
            break
            
        # known distance of min_node
        current_distance = result[min_node]
        
        # 2. For the current node, find all the unvisited neighbours. 
        # For this, you have calculate the distance of each unvisited neighbour.
        for neighbour in graph.neighbours[min_node]:
            if neighbour in unvisited:
                distance = current_distance + graph.distances[(min_node, neighbour)]
            
                # 3. If the calculated distance of the unvisited neighbour is less than the already known distance in result dictionary, update the shortest distance in the result dictionary.
                if ((neighbour not in result) or (distance < result[neighbour])):
                    result[neighbour] = distance

                    # 4. If there is an update in the result dictionary, you need to update the path dictionary as well for the same key.
                    path[neighbour] = min_node
        
        # 5. Remove the current node from the unvisited set.
        unvisited.remove(min_node)

    return result