A* 알고리즘 MATLAB 구현

1. MATLAB 코드 구현

% Excel 파일에서 맵 읽기
map = xlsread('your_map_file.xlsx'); 

% 시작점과 종료점 설정
startPoint = [1, 1]; 
endPoint = [size(map, 1), size(map, 2)]; 

% A* 알고리즘 핵심 코드
openSet = [startPoint]; 
cameFrom = containers.Map(); 
gScore = containers.Map(); 
gScore(startPoint) = 0; 
fScore = containers.Map(); 
fScore(startPoint) = heuristic(startPoint, endPoint); 

while ~isempty(openSet)
    [~, currentIndex] = min([fScore.values{:}]); 
    current = openSet(currentIndex); 
    if isequal(current, endPoint)
        path = reconstructPath(cameFrom, current); 
        break;
    end
    openSet(currentIndex) = []; 
    neighbors = getNeighbors(current, map); 
    for i = 1:size(neighbors, 1)
        neighbor = neighbors(i, :); 
        tentativeGScore = gScore(current) + 1; 
        if ~gScore.isKey(neighbor) || tentativeGScore < gScore(neighbor)
            cameFrom(neighbor) = current; 
            gScore(neighbor) = tentativeGScore; 
            fScore(neighbor) = tentativeGScore + heuristic(neighbor, endPoint); 
            if ~ismember(neighbor, openSet, 'rows')
                openSet = [openSet; neighbor]; 
            end
        end
    end
end

function h = heuristic(a, b)
    h = abs(a(1) - b(1)) + abs(a(2) - b(2)); 
end

function neighbors = getNeighbors(node, map)
    x = node(1); 
    y = node(2); 
    neighbors = []; 
    if x > 1 && map(x - 1, y) ~= 1
        neighbors = [neighbors; x - 1, y]; 
    end
    if x < size(map, 1) && map(x + 1, y) ~= 1
        neighbors = [neighbors; x + 1, y]; 
    end
    if y > 1 && map(x, y - 1) ~= 1
        neighbors = [neighbors; x, y - 1]; 
    end
    if y < size(map, 2) && map(x, y + 1) ~= 1
        neighbors = [neighbors; x, y + 1]; 
    end
end

function path = reconstructPath(cameFrom, current)
    totalPath = {current}; 
    while cameFrom.isKey(current)
        current = cameFrom(current); 
        totalPath = [current; totalPath{:}]; 
    end
    path = totalPath; 
end

2. C 언어 코드 구현

#include 
#include 
#include 

#define ROWS 10
#define COLS 10

typedef struct {
    int x;
    int y;
    int gScore;
    int fScore;
    int cameFromX;
    int cameFromY;
} NodeInfo;

typedef struct {
    NodeInfo data[ROWS * COLS];
    int size;
} OpenSet;

void initOpenSet(OpenSet *openSet) {
    openSet->size = 0;
}

void addToOpenSet(OpenSet *openSet, NodeInfo node) {
    openSet->data[openSet->size++] = node;
}

int isOpenSetEmpty(OpenSet *openSet) {
    return openSet->size == 0;
}

NodeInfo getLowestFScoreNode(OpenSet *openSet) {
    int minIndex = 0;
    for (int i = 1; i < openSet->size; i++) {
        if (openSet->data[i].fScore < openSet->data[minIndex].fScore) {
            minIndex = i;
        }
    }
    NodeInfo node = openSet->data[minIndex];
    openSet->data[minIndex] = openSet->data[openSet->size - 1];
    openSet->size--;
    return node;
}

int isValid(int x, int y) {
    return x >= 0 && x < ROWS && y >= 0 && y < COLS;
}

int heuristic(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

void aStar(int map[ROWS][COLS], int startX, int startY, int goalX, int goalY) {
    int gScore[ROWS][COLS];
    int fScore[ROWS][COLS];
    int cameFromX[ROWS][COLS];
    int cameFromY[ROWS][COLS];
    int visited[ROWS][COLS];

    memset(gScore, -1, sizeof(gScore));
    memset(fScore, -1, sizeof(fScore));
    memset(cameFromX, -1, sizeof(cameFromX));
    memset(cameFromY, -1, sizeof(cameFromY));
    memset(visited, 0, sizeof(visited));

    OpenSet openSet;
    initOpenSet(&openSet);

    NodeInfo startPoint;
    startPoint.x = startX;
    startPoint.y = startY;
    startPoint.gScore = 0;
    startPoint.fScore = heuristic(startX, startY, goalX, goalY);
    startPoint.cameFromX = -1;
    startPoint.cameFromY = -1;

    addToOpenSet(&openSet, startPoint);
    gScore[startX][startY] = 0;
    fScore[startX][startY] = startPoint.fScore;

    while (!isOpenSetEmpty(&openSet)) {
        NodeInfo current = getLowestFScoreNode(&openSet);
        if (current.x == goalX && current.y == goalY) {
            printf("경로 찾기 성공: \n");
            while (current.x != -1 && current.y != -1) {
                printf("(%d, %d) ", current.x, current.y);
                int tempX = current.cameFromX;
                int tempY = current.cameFromY;
                current.x = tempX;
                current.y = tempY;
            }
            printf("\n");
            return;
        }
        visited[current.x][current.y] = 1;

        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        for (int i = 0; i < 4; i++) {
            int newX = current.x + dx[i];
            int newY = current.y + dy[i];
            if (isValid(newX, newY) && map[newX][newY] != 1) {
                int tentativeGScore = gScore[current.x][current.y] + 1;
                if (gScore[newX][newY] == -1 || tentativeGScore < gScore[newX][newY]) {
                    cameFromX[newX][newY] = current.x;
                    cameFromY[newX][newY] = current.y;
                    gScore[newX][newY] = tentativeGScore;
                    fScore[newX][newY] = tentativeGScore + heuristic(newX, newY, goalX, goalY);
                    if (!visited[newX][newY]) {
                        NodeInfo neighbor;
                        neighbor.x = newX;
                        neighbor.y = newY;
                        neighbor.gScore = tentativeGScore;
                        neighbor.fScore = fScore[newX][newY];
                        neighbor.cameFromX = current.x;
                        neighbor.cameFromY = current.y;
                        addToOpenSet(&openSet, neighbor);
                    }
                }
            }
        }
    }
    printf("경로가 없음.\n");
}

Dijkstra 알고리즘 MATLAB 구현

1. MATLAB 코드 구현

% 인접 행렬
adjMatrix = [0 1 0 1 0;
             1 0 1 0 0;
             0 1 0 1 1;
             1 0 1 0 1;
             0 0 1 1 0]; 

numNodes = size(adjMatrix, 1); 
startNode = 1; 

distance = inf(numNodes, 1); 
distance(startNode) = 0; 
visited = false(numNodes, 1); 

while any(~visited)
    [~, currentNode] = min(distance(~visited)); 
    currentNode = find(~visited, 1, 'first'); 
    visited(currentNode) = true; 
    neighbors = find(adjMatrix(currentNode, :)); 
    for i = 1:numel(neighbors)
        neighbor = neighbors(i); 
        newDistance = distance(currentNode) + 1; 
        if newDistance < distance(neighbor)
            distance(neighbor) = newDistance; 
        end
    end
end