[Introduction à l'algorithme] Trouvez l'itinéraire le plus court [Python3]

thème

Trouvez un itinéraire qui relie le point de départ et le point de but au coût le plus bas sur une carte qui a le coût du terrain comme information. (Par exemple, dans les jeux SRPG, les coûts du terrain sont pris en compte lors du déplacement vers les plaines, les maisons, les forêts et les montagnes.)

algorithme

1. Préparez un tableau correspondant aux coordonnées et au coût du terrain (cost_map)
2. Trouvez le coût du déplacement du point de but vers chaque point et créez un tableau (rout_cost)
3. En fonction du coût de déplacement (rout_cost) de chaque point, suivez le point avec le coût le plus bas à partir du point de départ

Note) Supplément (Technique utilisée lors de l'écriture d'un programme) Utilisez une fonction récursive.

Entraine toi

1. Par exemple, considérez l'itinéraire le plus court entre le début (x3, y0) et l'objectif (x1, y6) sur une carte avec le coût de terrain suivant.

Préparez un tableau cost_map qui a le coût du terrain comme élément et un tableau rout_cost qui a une valeur infinie comme élément.

alg_01.py

s = [3,0]; g = [1,6]  ## start and goal position
cost_map = [[4,3,1,1,1,2,3],\
            [3,2,1,2,1,1,1],\
            [2,1,3,3,2,3,2],\
            [2,3,5,3,2,4,3]]
m = len(cost_map)
n = len(cost_map[0])
rout_cost = [[float("inf") for j in range(n)] for i in range(m)]

2. Calculez le coût du mouvement vers chaque point à partir du point de but, et mettez à jour le coût_outu préparé ci-dessus en fonction du résultat du calcul.

alg_02.py

def calc_rout_cost(x,y,cost_tmp):
    cost_tmp += cost_map[x][y]
    if cost_tmp < rout_cost[x][y]:
        rout_cost[x][y] = cost_tmp
        if y < n-1:
            calc_rout_cost(x,y+1,cost_tmp)
        if y > 0:
            calc_rout_cost(x,y-1,cost_tmp)
        if x < m-1:
            calc_rout_cost(x+1,y,cost_tmp)
        if x > 0:
            calc_rout_cost(x-1,y,cost_tmp)
calc_rout_cost(g[0],g[1],-cost_map[g[0]][g[1]])

Le rout_cost terminé est le suivant. Notez que le point de but (x6, y1) sera zéro.

3. Enfin, trouvez le chemin le plus court du départ au but.

alg_03.py

def search_rout(x,y):
    tmp = rout_cost[x][y]
    tmp_x, tmp_y = x, y
    if x > 0 and rout_cost[x-1][y] < tmp :
        tmp_x, tmp_y = x-1, y
        tmp = rout_cost[tmp_x][tmp_y]
    if x < m-1 and rout_cost[x+1][y] < tmp :
        tmp_x, tmp_y = x+1, y
        tmp = rout_cost[tmp_x][tmp_y]
    if y > 0 and rout_cost[x][y-1] < tmp :
        tmp_x, tmp_y = x, y-1
        tmp = rout_cost[tmp_x][tmp_y]
    if y < n-1 and rout_cost[x][y+1] < tmp :
        tmp_x, tmp_y = x, y+1
        tmp = rout_cost[tmp_x][tmp_y]
    if rout_cost[x][y] == 0: return;
    rout_list.append([tmp_x,tmp_y])
    search_rout(tmp_x,tmp_y)

rout_list = []
rout_list.append(s)
search_rout(s[0],s[1])

Le trajet le plus court est

result.py

print(rout_list)
## [[3, 0], [2, 0], [2, 1], [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6]]

Sera.

Les références

Revue technique de Masakazu Yanai "Code Puzzle for Programmers" (2014) Veuillez vous référer à la documentation pour une explication détaillée. Il est écrit en Javascript.