Bagaimana Algoritma dan A-Star Dijkstra membandingkan?

154

Saya melihat apa yang telah dilakukan oleh orang-orang di Kompetisi AI Mario dan beberapa dari mereka telah membangun beberapa bot Mario yang cukup rapi menggunakan Algoritma Pathing A * (A-Star).

teks alternatif
( Video Mario A * Bot Beraksi )

Pertanyaan saya adalah, bagaimana A-Star dibandingkan dengan Dijkstra? Melihat mereka, mereka tampak serupa.

Mengapa seseorang menggunakan yang satu di atas yang lain? Terutama dalam konteks pathing dalam game?

KingNestor
sumber
47
xkcd.com/342
SLaks
@SLaks A * menggunakan lebih banyak memori daripada dijkstra? Bagaimana bisa jika * hanya path node yang menjanjikan saat dijkstra mencoba semuanya?
Poutrathor

Jawaban:

177

Dijkstra adalah kasus khusus untuk A * (ketika heuristik adalah nol).

pungutan
sumber
1
Di dijkstra, kami hanya mempertimbangkan jarak dari sumbernya kan? Dan titik minimum dipertimbangkan?
Kraken
4
Saya pikir A * adalah kasus khusus untuk Dijkstra di mana mereka menggunakan heuristik. Karena Dijkstra pertama kali ada afaik.
Madmenyo
46
@MennoGouw: Ya, algoritma Dijkstra dikembangkan lebih dulu; tetapi ini adalah kasus khusus dari algoritma A * yang lebih umum. Sama sekali tidak aneh (pada kenyataannya, mungkin norma) untuk kasus-kasus khusus yang ditemukan pertama kali, dan kemudian digeneralisasikan.
Pieter Geerkens
1
Jawaban bagus untuk siapa pun yang tahu heuristik;)
lindhe
1
A * dan penggunaan heuristik dibahas dengan baik dalam buku AI Norvig dan Russel
BoltzmannBrain
113

Dijkstra:

Ini memiliki satu fungsi biaya, yang merupakan nilai biaya riil dari sumber ke setiap node: f(x)=g(x).
Ia menemukan jalur terpendek dari sumber ke setiap simpul lain dengan hanya mempertimbangkan biaya riil.

Pencarian:

Ini memiliki dua fungsi biaya.

  1. g(x): sama dengan Dijkstra. Biaya nyata untuk mencapai simpul x.
  2. h(x): perkiraan biaya dari simpul xke simpul sasaran. Ini adalah fungsi heuristik. Fungsi heuristik ini seharusnya tidak melebih-lebihkan biayanya. Itu berarti, biaya riil untuk mencapai simpul tujuan dari simpul xharus lebih besar dari atau sama h(x). Ini disebut heuristik yang dapat diterima.

Total biaya setiap node dihitung oleh f(x)=g(x)+h(x)

Pencarian * hanya memperluas node jika tampaknya menjanjikan. Ini hanya berfokus untuk mencapai node tujuan dari node saat ini, bukan untuk mencapai setiap node lainnya. Ini optimal, jika fungsi heuristik diterima.

Jadi, jika fungsi heuristik Anda bagus untuk memperkirakan biaya di masa depan, maka Anda harus menjelajahi lebih sedikit node daripada Dijkstra.

Shahadat Hossain
sumber
20

Apa yang dikatakan poster sebelumnya, ditambah karena Dijkstra tidak memiliki heuristik dan pada setiap langkah memilih tepi dengan biaya terkecil, ia cenderung "menutupi" lebih banyak grafik Anda. Karena itu Dijkstra bisa lebih berguna daripada A *. Contoh yang baik adalah ketika Anda memiliki beberapa node target kandidat, tetapi Anda tidak tahu, yang mana yang paling dekat (dalam kasus A * Anda harus menjalankannya beberapa kali: satu kali untuk setiap kandidat node).

ttvd
sumber
17
Jika ada beberapa node tujuan potensial, seseorang dapat dengan mudah mengubah fungsi pengujian tujuan untuk memasukkan semuanya. Dengan cara ini, A * hanya perlu dijalankan sekali.
Brad Larsen
9

Algoritma Dijkstra tidak akan pernah digunakan untuk merintis jalan. Menggunakan A * adalah hal yang sulit jika Anda dapat menemukan heuristik yang layak (biasanya mudah untuk gim, terutama di dunia 2D). Bergantung pada ruang pencarian, Iterative Deepening A * kadang-kadang lebih disukai karena menggunakan lebih sedikit memori.

Katak Shaggy
sumber
5
Mengapa Dijkstra tidak pernah digunakan untuk merintis jalan? Bisakah Anda menguraikan?
KingNestor
2
Karena bahkan jika Anda dapat menemukan heuristik yang buruk, Anda akan melakukan lebih baik daripada Dijkstra. Terkadang bahkan jika itu tidak dapat diterima. Itu tergantung pada domain. Dijkstra juga tidak akan berfungsi dalam situasi dengan memori rendah, sedangkan IDA * akan.
Shaggy Frog
Saya menemukan slide di sini: webdocs.cs.ualberta.ca/ ~jonathan
PREVIOUS
7

Dijkstra adalah kasus khusus untuk A *.

Dijkstra menemukan biaya minimum dari titik awal ke titik lainnya. A * menemukan biaya minimum dari simpul awal ke simpul sasaran.

Algoritma Dijkstra tidak akan pernah digunakan untuk pencarian jalur. Menggunakan A * satu dapat datang dengan heuristik yang layak. Bergantung pada ruang pencarian, A * iteratif lebih disukai karena menggunakan lebih sedikit memori.

Kode untuk algoritma Dijkstra adalah:

// A C / C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph

#include <stdio.h>
#include <limits.h>

// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
 // Initialize min value
 int min = INT_MAX, min_index;

  for (int v = 0; v < V; v++)
   if (sptSet[v] == false && dist[v] <= min)
     min = dist[v], min_index = v;

   return min_index;
}

 int printSolution(int dist[], int n)
 {
  printf("Vertex   Distance from Source\n");
  for (int i = 0; i < V; i++)
     printf("%d \t\t %d\n", i, dist[i]);
  }

void dijkstra(int graph[V][V], int src)
{
 int dist[V];     // The output array.  dist[i] will hold the shortest
                  // distance from src to i

 bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
                 // path tree or shortest distance from src to i is finalized

 // Initialize all distances as INFINITE and stpSet[] as false
 for (int i = 0; i < V; i++)
    dist[i] = INT_MAX, sptSet[i] = false;

 // Distance of source vertex from itself is always 0
 dist[src] = 0;

 // Find shortest path for all vertices
 for (int count = 0; count < V-1; count++)
 {
   // Pick the minimum distance vertex from the set of vertices not
   // yet processed. u is always equal to src in first iteration.
   int u = minDistance(dist, sptSet);

   // Mark the picked vertex as processed
   sptSet[u] = true;

   // Update dist value of the adjacent vertices of the picked vertex.
   for (int v = 0; v < V; v++)

     // Update dist[v] only if is not in sptSet, there is an edge from 
     // u to v, and total weight of path from src to  v through u is 
     // smaller than current value of dist[v]
     if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                                   && dist[u]+graph[u][v] < dist[v])
        dist[v] = dist[u] + graph[u][v];
 }

 // print the constructed distance array
 printSolution(dist, V);
 }

// driver program to test above function
int main()
 {
 /* Let us create the example graph discussed above */
 int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                  {4, 0, 8, 0, 0, 0, 0, 11, 0},
                  {0, 8, 0, 7, 0, 4, 0, 0, 2},
                  {0, 0, 7, 0, 9, 14, 0, 0, 0},
                  {0, 0, 0, 9, 0, 10, 0, 0, 0},
                  {0, 0, 4, 14, 10, 0, 2, 0, 0},
                  {0, 0, 0, 0, 0, 2, 0, 1, 6},
                  {8, 11, 0, 0, 0, 0, 1, 0, 7},
                  {0, 0, 2, 0, 0, 0, 6, 7, 0}
                 };

dijkstra(graph, 0);

return 0;
}

Kode untuk algoritma A * adalah:

class Node:
def __init__(self,value,point):
    self.value = value
    self.point = point
    self.parent = None
    self.H = 0
    self.G = 0
def move_cost(self,other):
    return 0 if self.value == '.' else 1

def children(point,grid):
x,y = point.point
links = [grid[d[0]][d[1]] for d in [(x-1, y),(x,y - 1),(x,y + 1),(x+1,y)]]
return [link for link in links if link.value != '%']
def manhattan(point,point2):
return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[0])
def aStar(start, goal, grid):
#The open and closed sets
openset = set()
closedset = set()
#Current point is the starting point
current = start
#Add the starting point to the open set
openset.add(current)
#While the open set is not empty
while openset:
    #Find the item in the open set with the lowest G + H score
    current = min(openset, key=lambda o:o.G + o.H)
    #If it is the item we want, retrace the path and return it
    if current == goal:
        path = []
        while current.parent:
            path.append(current)
            current = current.parent
        path.append(current)
        return path[::-1]
    #Remove the item from the open set
    openset.remove(current)
    #Add it to the closed set
    closedset.add(current)
    #Loop through the node's children/siblings
    for node in children(current,grid):
        #If it is already in the closed set, skip it
        if node in closedset:
            continue
        #Otherwise if it is already in the open set
        if node in openset:
            #Check if we beat the G score 
            new_g = current.G + current.move_cost(node)
            if node.G > new_g:
                #If so, update the node to have a new parent
                node.G = new_g
                node.parent = current
        else:
            #If it isn't in the open set, calculate the G and H score for the node
            node.G = current.G + current.move_cost(node)
            node.H = manhattan(node, goal)
            #Set the parent to our current item
            node.parent = current
            #Add it to the set
            openset.add(node)
    #Throw an exception if there is no path
    raise ValueError('No Path Found')
def next_move(pacman,food,grid):
#Convert all the points to instances of Node
for x in xrange(len(grid)):
    for y in xrange(len(grid[x])):
        grid[x][y] = Node(grid[x][y],(x,y))
#Get the path
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
#Output the path
print len(path) - 1
for node in path:
    x, y = node.point
    print x, y
pacman_x, pacman_y = [ int(i) for i in raw_input().strip().split() ]
food_x, food_y = [ int(i) for i in raw_input().strip().split() ]
x,y = [ int(i) for i in raw_input().strip().split() ]

grid = []
for i in xrange(0, x):
grid.append(list(raw_input().strip()))

next_move((pacman_x, pacman_y),(food_x, food_y), grid)
John Baller
sumber
melewatkan tetangga yang sudah di set tertutup akan memberikan suboptimal. Mencoba di grafik ini (Ini adalah contoh video youtube, abaikan bahasanya) akan memberikan jawaban yang salah.
itsjwala
5

Dijkstra menemukan biaya minimum dari titik awal ke titik lainnya. A * menemukan biaya minimum dari simpul awal ke simpul sasaran.

Oleh karena itu, tampaknya Dijkstra akan kurang efisien ketika yang Anda butuhkan adalah jarak minimum dari satu node ke node lainnya.

Robert
sumber
2
Ini tidak benar. Standard Dijkstra digunakan untuk memberikan jalur terpendek antara dua titik.
Emil
3
Tolong jangan menyesatkan, Dijkstra's memberikan hasil dari s ke semua simpul lainnya. Dengan demikian kerjanya lebih lambat.
Ivan Voroshilin
Saya kedua @Emil komentar. Yang perlu Anda lakukan adalah berhenti ketika menghapus node tujuan dari antrian prioritas dan Anda memiliki jalur terpendek dari sumber ke tujuan. Sebenarnya ini adalah algoritma asli.
seteropere
Lebih tepatnya: jika target ditentukan, Dijkstra's menemukan jalur terpendek ke semua node yang terletak di jalur yang lebih pendek dari jalur ke target yang ditentukan. Tujuan heuristik dalam A * adalah untuk memangkas beberapa jalur ini. Efektivitas heuristik menentukan berapa banyak yang dipangkas.
Waylon Flinn
@seteropere, tetapi bagaimana jika simpul tujuan Anda adalah simpul terakhir yang dicari? Ini jelas kurang efisien, karena heuristik A * dan memilih node prioritas adalah yang membantu memastikan bahwa simpul tujuan yang dicari bukan simpul terakhir dalam daftar
Knight0fDragon
5

Anda dapat mempertimbangkan A * versi panduan Dijkstra. Artinya, alih-alih menjelajahi semua node, Anda akan menggunakan heuristik untuk memilih arah.

Untuk membuatnya lebih konkret, jika Anda menerapkan algoritma dengan antrian prioritas maka prioritas node yang Anda kunjungi akan menjadi fungsi dari biaya (biaya node sebelumnya + biaya untuk sampai ke sini) dan perkiraan heuristik dari sini ke tujuan. Sementara di Dijkstra, prioritas hanya dipengaruhi oleh biaya aktual untuk node. Dalam kedua kasus, kriteria berhenti mencapai tujuan.

gitfredy
sumber
2

Algoritma Dijkstra menemukan jalur terpendek dengan pasti. Di sisi lain A * tergantung pada heuristik. Untuk alasan ini A * lebih cepat daripada algoritma Dijkstra dan akan memberikan hasil yang baik jika Anda memiliki heuristik yang baik.

Hani
sumber
4
A * memberikan hasil yang sama dengan Dijkstra, tetapi lebih cepat ketika Anda menggunakan heuristik yang baik. Algoritma A * membebankan beberapa kondisi agar bekerja dengan benar seperti perkiraan jarak antara simpul saat ini dan simpul akhir harus lebih rendah dari jarak sebenarnya.
Alexandru
4
A * dijamin untuk memberikan jalan terpendek ketika heuristik dapat diterima (selalu diremehkan)
Robert
1

Jika Anda melihat kode psued untuk Astar:

foreach y in neighbor_nodes(x)
             if y in closedset
                 continue

Sedangkan, jika Anda melihat yang sama untuk Dijkstra :

for each neighbor v of u:         
             alt := dist[u] + dist_between(u, v) ;

Jadi, intinya adalah, Astar tidak akan mengevaluasi sebuah node lebih dari sekali,
karena ia percaya bahwa melihat suatu node saja sudah cukup, karena
heuristiknya.

OTOH, algoritma Dijkstra tidak malu mengoreksi dirinya sendiri, kalau
- kalau sebuah node muncul lagi.

Yang seharusnya membuat Astar lebih cepat dan lebih cocok untuk pencarian jalur.

simplfuzz
sumber
7
Ini tidak benar: A * dapat melihat node lebih dari sekali. Faktanya, Dijkstra adalah kasus khusus A * ...
Emil
2
Periksa yang ini untuk klarifikasi: stackoverflow.com/questions/21441662/…
spiralmoon
Semua algoritma pencarian memiliki "batas" dan "set yang dikunjungi". Algoritme tidak memperbaiki jalur ke sebuah simpul setelah berada di set yang dikunjungi: dengan desain, mereka memindahkan node dari perbatasan ke set yang dikunjungi dalam urutan prioritas. Jarak minimal yang diketahui ke node hanya dapat diperbarui saat berada di perbatasan. Dijkstra's adalah bentuk pencarian terbaik-pertama, dan sebuah simpul tidak akan pernah ditinjau kembali setelah ditempatkan di set "dikunjungi". A * membagikan properti ini, dan ia menggunakan estimator bantu untuk memilih node mana yang akan diprioritaskan. en.wikipedia.org/wiki/Dijkstra%27s_algorithm
pygosceles
0

Di A *, untuk setiap node Anda memeriksa koneksi keluar untuk mereka.
Untuk setiap simpul baru Anda menghitung biaya terendah sejauh ini (csf) tergantung pada bobot koneksi ke simpul ini dan biaya yang harus Anda capai untuk simpul sebelumnya.
Selain itu Anda memperkirakan biaya dari node baru ke node target dan menambahkannya ke csf. Anda sekarang memiliki perkiraan total biaya (dll). (etc = csf + perkiraan jarak ke target) Berikutnya Anda memilih dari node baru yang satu dengan yang terendah dll.
Lakukan hal yang sama seperti sebelumnya sampai salah satu node baru akan menjadi target.

Dijkstra bekerja hampir sama. Kecuali bahwa estimasi jarak ke target selalu 0, dan algoritma pertama berhenti ketika target tidak hanya salah satu node baru , tetapi juga satu dengan csf terendah.

A * biasanya lebih cepat daripada dijstra, meskipun ini tidak selalu menjadi masalah. Dalam gim video, Anda sering memilih pendekatan "cukup dekat untuk gim". Oleh karena itu jalur optimal "cukup dekat" dari A * biasanya cukup.

keinabel
sumber
-1

Algoritma Dijkstra jelas lengkap dan optimal sehingga Anda akan selalu menemukan jalur terpendek. Namun cenderung memakan waktu lebih lama karena digunakan terutama untuk mendeteksi beberapa node tujuan.

A* searchdi sisi lain masalah dengan nilai-nilai heuristik, yang dapat Anda tetapkan untuk mencapai tujuan Anda lebih dekat, seperti jarak manhattan ke arah gawang. Ini bisa menjadi optimal atau lengkap yang tergantung pada faktor heuristik. sudah pasti lebih cepat jika Anda memiliki simpul tujuan tunggal.

Stasis
sumber