AI 와 생각해보는 알고리즘 그리고 현대모비스 자율주행?

https://velog.io/@iamipro/posts

iamipro (임명수) / 작성글 - velog

코딩 블로그는 따로 운영하고 있다.

여기는 IT블로그를 운영중인데

생각해보니 요즘 핫한 AI에 관한 것이다.

AI 인프라인 엔비디아가 이제 주춤하고,

AI 소프트웨어인 마이크로소프트, 구글, 메타 그리고 클라우드 아마존이 호황이란다.

 

인공지능, 알고리즘 공부해본거 생각해보면 회귀, 분류 빅데이터를 이용하여 정답과 거리를 줄여나가는 그레이디언트 부스팅, 최단거리 탐색 알고리즘 다익스트라, 그리고 내비게이션과 연결된 A*알고리즘 이런 것들이다.

 

그레이디언트 부스팅은 머신러닝과 상관있으니 차치하고,

다익스트라 최단거리 알고리즘을 자바와 파이썬으로 한번보자

 

파이썬 역시 priority_queue가 나온다.

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# 그래프 예제
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

start_node = 'A'
print(dijkstra(graph, start_node))

 

import java.util.*;

class Node implements Comparable<Node> {
    private final String name;
    private final int distance;

    public Node(String name, int distance) {
        this.name = name;
        this.distance = distance;
    }

    public String getName() {
        return name;
    }

    public int getDistance() {
        return distance;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.distance, other.distance);
    }
}

public class Dijkstra {

    public static Map<String, Integer> dijkstra(Map<String, Map<String, Integer>> graph, String start) {
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>();
        Map<String, Integer> distances = new HashMap<>();
        Set<String> visited = new HashSet<>();

        for (String node : graph.keySet()) {
            distances.put(node, Integer.MAX_VALUE);
        }
        distances.put(start, 0);
        priorityQueue.add(new Node(start, 0));

        while (!priorityQueue.isEmpty()) {
            Node currentNode = priorityQueue.poll();
            String currentName = currentNode.getName();

            if (visited.contains(currentName)) {
                continue;
            }
            visited.add(currentName);

            Map<String, Integer> neighbors = graph.get(currentName);
            for (Map.Entry<String, Integer> neighbor : neighbors.entrySet()) {
                String neighborName = neighbor.getKey();
                int weight = neighbor.getValue();
                int newDist = distances.get(currentName) + weight;

                if (newDist < distances.get(neighborName)) {
                    distances.put(neighborName, newDist);
                    priorityQueue.add(new Node(neighborName, newDist));
                }
            }
        }

        return distances;
    }

    public static void main(String args) {
        Map<String, Map<String, Integer>> graph = new HashMap<>();
        graph.put("A", Map.of("B", 1, "C", 4));
        graph.put("B", Map.of("A", 1, "C", 2, "D", 5));
        graph.put("C", Map.of("A", 4, "B", 2, "D", 1));
        graph.put("D", Map.of("B", 5, "C", 1));

        String startNode = "A";
        Map<String, Integer> distances = dijkstra(graph, startNode);

        for (Map.Entry<String, Integer> entry : distances.entrySet()) {
            System.out.println("Distance from " + startNode + " to " + entry.getKey() + " is " + entry.getValue());
        }
    }
}

 

최단거리 탐색으로 그래프탐색알고리즘인 A*알고리즘은 내비게이션에 많이 사용된다. 다익스트라와 유사하지만 , 휴리스틱 함수를 사용하여 탐색속도를 향상시킨다.

 

import java.util.*;

class Node implements Comparable<Node> {
    private final int x, y;
    private final int g, h;

    public Node(int x, int y, int g, int h) {
        this.x = x;
        this.y = y;
        this.g = g;
        this.h = h;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public int getG() {
        return g;
    }

    public int getH() {
        return h;
    }

    public int getF() {
        return g + h;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.getF(), other.getF());
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == || getClass() != obj.getClass()) return false;
        Node node = (Node) obj;
        return x == node.x && y == node.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

public class AStarAlgorithm {
    private static final int[][] DIRECTIONS = {
        {0, 1}, {1, 0}, {0, -1}, {-1, 0}
    };

    public static List<Node> aStar(int[][] grid, Node start, Node goal) {
        PriorityQueue<Node> openList = new PriorityQueue<>();
        Set<Node> closedList = new HashSet<>();
        Map<Node, Node> cameFrom = new HashMap<>();
        Map<Node, Integer> gScore = new HashMap<>();
        gScore.put(start, 0);
        openList.add(start);

        while (!openList.isEmpty()) {
            Node current = openList.poll();

            if (current.equals(goal)) {
                return reconstructPath(cameFrom, current);
            }

            closedList.add(current);

            for (int direction : DIRECTIONS) {
                int newX = current.getX() + direction[0];
                int newY = current.getY() + direction[1];

                if (newX < 0 || newY < 0 || newX >= grid.length || newY >= grid[0].length || grid[newX][newY] == 1) {
                    continue;
                }

                Node neighbor = new Node(newX, newY, current.getG() + 1, heuristic(newX, newY, goal.getX(), goal.getY()));

                if (closedList.contains(neighbor)) {
                    continue;
                }

                int tentativeGScore = gScore.get(current) + 1;

                if (!openList.contains(neighbor) || tentativeGScore < gScore.getOrDefault(neighbor, Integer.MAX_VALUE)) {
                    cameFrom.put(neighbor, current);
                    gScore.put(neighbor, tentativeGScore);
                    if (!openList.contains(neighbor)) {
                        openList.add(neighbor);
                    }
                }
            }
        }

        return Collections.emptyList(); // 경로를 찾지 못한 경우
    }

    private static int heuristic(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2); // 맨해튼 거리
    }

    private static List<Node> reconstructPath(Map<Node, Node> cameFrom, Node current) {
        List<Node> path = new ArrayList<>();
        while (current !=) {
            path.add(current);
            current = cameFrom.get(current);
        }
        Collections.reverse(path);
        return path;
    }

    public static void main(String args) {
        int[][] grid = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0}
        };

        Node start = new Node(0, 0, 0, heuristic(0, 0, 4, 4));
        Node goal = new Node(4, 4, 0, 0);

        List<Node> path = aStar(grid, start, goal);

        if (!path.isEmpty()) {
            System.out.println("Path found:");
            for (Node node : path) {
                System.out.println("(" + node.getX() + ", " + node.getY() + ")");
            }
        } else {
            System.out.println("No path found.");
        }
    }
}

 

A*은 휴리스틱이 잘 설계되는게 중요한데, 그럴수록 다익스트라보다 효율적이다.

현대모비스에서는 자율주행이 쟁점이니 이런거 활용하는게 나올라나?