[Einführung in den Algorithmus] Finden Sie den kürzesten Weg [Python3]

Thema

Suchen Sie auf einer Karte, die Geländekosten als Information enthält, eine Route, die den Startpunkt und den Zielpunkt zu den niedrigsten Kosten verbindet. (In SRPG-Spielen werden beispielsweise Geländekosten berücksichtigt, wenn Sie in Flachland, Häuser, Wälder und Berge ziehen.)

Algorithmus

1. Bereiten Sie ein Array vor, das den Koordinaten und Geländekosten entspricht (cost_map)
2. Ermitteln Sie die Kosten für den Wechsel vom Zielpunkt zu jedem Punkt und erstellen Sie ein Array (rout_cost).
3. Folgen Sie basierend auf den Bewegungskosten (rout_cost) jedes Punkts dem Punkt mit den niedrigsten Kosten vom Startpunkt aus

Hinweis) Ergänzung (Technik, die beim Schreiben eines Programms verwendet wird) Verwenden Sie eine rekursive Funktion.

Trainieren

1. Betrachten Sie beispielsweise die kürzeste Route vom Start (x3, y0) bis zum Ziel (x1, y6) auf einer Karte mit den folgenden Geländekosten.

Bereiten Sie ein Array cost_map mit Geländekosten als Element und ein Array rout_cost mit einem unendlichen Wert als Element vor.

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. Berechnen Sie die Bewegungskosten für jeden Punkt ab dem Zielpunkt und aktualisieren Sie die oben vorbereiteten rout_cost basierend auf dem Berechnungsergebnis.

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]])

Die abgeschlossenen rout_cost lauten wie folgt. Beachten Sie, dass der Zielpunkt (x6, y1) Null ist.

3. Finden Sie schließlich den kürzesten Weg vom Start bis zum Ziel.

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])

Der kürzeste Weg ist

result.py

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

Wird sein.

Verweise

Masakazu Yanai "Code Puzzle für Programmierer" Technical Review (2014) Eine ausführliche Erklärung finden Sie in der Literatur. Es ist in Javascript geschrieben.