كيف تقوم خوارزمية Dijkstra ومقارنة نجمة؟

Question

كنت أبحث في ما الرجال في مسابقة ماريو منظمة العفو الدولية لقد تم القيام به وبعضهم ببناء بعض روبوتات ماريو جميلة تستخدم خوارزمية المسار A * (نجمة).

(فيديو ماريو أ * بوت في العمل)

سؤالي هو، كيف تقارن نجمة مع dijkstra؟ النظر إليها، تبدو متشابهة.

لماذا يستخدم شخص ما واحدة على الآخر؟ خاصة في سياق المسار في الألعاب؟

Answer 1

Dijkstra هي حالة خاصة ل * (عندما تكون الاستدلال صفر).

Answer 2

dijkstra:

لديها وظيفة واحدة تكلفة، وهي قيمة تكلفة حقيقية من المصدر إلى كل عقدة: f(x)=g(x).
يجد أقصر طريق من المصدر إلى كل عقدة أخرى من خلال النظر في التكلفة الحقيقية فقط.

بحث:

لديها وظيفة التكلفة.

1. g(x): نفس dijkstra. التكلفة الحقيقية للوصول إلى عقدة x.
2. h(x): التكلفة التقريبية من العقدة x إلى عقدة الهدف. إنها وظيفة إرشادية. هذه الوظيفة الغربية لا ينبغي أن تبالغ أبدا في تقدير التكلفة. هذا يعني، تكلفة حقيقية للوصول إلى عقدة الهدف من العقدة x يجب أن يكون أكبر من أو يساوي h(x). وبعد ويطلق عليه الإغراء القبول.

يتم حساب التكلفة الإجمالية لكل عقدة بواسطة f(x)=g(x)+h(x)

A * Search فقط قم بتوسيع عقدة إذا بدا واعدا. يركز فقط على الوصول إلى عقدة الهدف من العقدة الحالية، وليس للوصول إلى كل عقد أخرى. إنه الأمثل، إذا كانت الوظيفة الإغراء مقبولة.

لذلك إذا كانت دالة إلغاء السرية جيدة لتقريب التكلفة المستقبلية، فهل ستحتاج إلى استكشاف العقد أقل بكثير من Dijkstra.

Answer 3

ما قاله الملصق السابق، بالإضافة إلى ذلك لأن Dijkstra ليس لديه مزعجة وفي كل خطوة تلتقط الحواف بأصغر تكلفة يميل إلى "تغطية" أكثر من الرسم البياني الخاص بك. بسبب هذا dijkstra يمكن أن يكون أكثر فائدة من *. مثال جيد هو عندما يكون لديك العديد من العقد المستهدفة المرشحة، لكنك لا تعرف، أيهما أقرب (في حالة * سيتعين عليك تشغيله عدة مرات: مرة واحدة لكل عقدة مرشحة).

Answer 4

لن يتم استخدام خوارزمية Dijkstra في Pathfinding. باستخدام A * غير عذر إذا كنت تستطيع التوصل إلى مخالفة كريمة (عادة ما تكون سهلة للألعاب، خاصة في العالمين الثاني). اعتمادا على مساحة البحث، فإن تعميق تكراري A * هو الأفضل أحيانا لأنه يستخدم ذاكرة أقل.

Answer 5

dijkstra هي حالة خاصة ل *.

يجد Dijkstra الحد الأدنى من التكاليف من عقدة البدء إلى جميع الآخرين. يجد A * الحد الأدنى من التكلفة من عقدة البدء إلى عقدة الهدف.

لن يتم استخدام خوارزمية Dijkstra في العثور على المسار. باستخدام A * يمكن للمرء أن يأتي مع مزراقة لائقة. اعتمادا على مساحة البحث، يكون تكراري A * هو الأفضل لأنه يستخدم ذاكرة أقل.

رمز خوارزمية Dijkstra هو:

// 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;
}

رمز خوارزمية * هو:

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)

Answer 6

يمكنك التفكير في * نسخة موجهة من Dijkstra. بمعنى، بدلا من استكشاف جميع العقد، ستستخدم محورا لاختيار اتجاه.

لوضعها بشكل أكثر ملاءمة، إذا كنت تنفذ الخوارزميات مع قائمة انتظار أولوية، فإن أولوية العقدة التي تزورها ستكون وظيفة من التكلفة (تكلفة العقد السابقة + تكلفة الوصول إلى هنا) وتقدير إرشادي من هنا إلى الهدف. بينما في Dijkstra، فإن الأولوية تتأثر فقط بالتكلفة الفعلية للعقد. في كلتا الحالتين، يصل معيار التوقف إلى الهدف.

Answer 7

يجد Dijkstra الحد الأدنى من التكاليف من عقدة البدء إلى جميع الآخرين. يجد A * الحد الأدنى من التكلفة من عقدة البدء إلى عقدة الهدف.

لذلك يبدو أن Dijkstra سيكون أقل كفاءة عندما تكون كل ما تحتاجه هو الحد الأدنى للمسافة من عقدة إلى أخرى.

Answer 8

إذا نظرت إلى psuedocode. ل Astar:

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

في حين، إذا نظرت إلى نفسه dijkstra. :

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

لذلك، فإن النقطة هي، لن تقوم أستار بتقييم العقدة أكثر من مرة،
لأنه يعتقد أن النظر في عقدة ذات مرة كافية، مستحقة
إلى الاستدلال لها.

Otoh، خوارزمية Dijkstra ليست خجولة من تصحيح نفسها، في حالة
عقدة ينبثق مرة أخرى.

أيّ ينبغي اجعل أستار أسرع وأكثر ملاءمة لاستدلاع المسار.

Answer 9

خوارزمية Dijkstra يجد أقصر مسار بالتأكيد. من ناحية أخرى، يعتمد على الإغراء. لهذا السبب، يكون ذلك أسرع من خوارزمية Dijkstra وسيعطي نتائج جيدة إذا كان لديك مزراقة جيدة.

Answer 10

تعد خوارزمية Dijkstra كاملة بالتأكيد وستجد دائما أقصر طريق. ومع ذلك، فإنه يميل إلى الاستمرار لفترة أطول لأنه يستخدم بشكل أساسي للكشف عن عقد هدف متعددة.

A* search من ناحية أخرى، المسائل ذات القيم السريعة، والتي يمكنك تحديدها للوصول إلى هدفك أقرب، مثل مسافة مانهاتن نحو الهدف. يمكن أن تكون إما مثالية أو كاملة مما يعتمد على العوامل المثيرة. بالتأكيد أسرع إذا كان لديك عقدة هدف واحد.

Answer 11

في *، لكل عقدة، يمكنك التحقق من الاتصالات الصادرة الخاصة بهم.
بالنسبة لكل عقدة جديدة، تقوم بحساب أقل تكلفة حتى الآن (CSF) اعتمادا على أوزان الاتصالات إلى هذه العقدة والتكاليف التي كان عليك الوصول إلى العقدة السابقة.
بالإضافة إلى ذلك، تقدر التكلفة من العقدة الجديدة إلى العقدة المستهدفة وإضافة هذا إلى CSF. لديك الآن التكلفة الإجمالية المقدرة (إلخ). (إلخ = CSF + المسافة المقدرة إلى الهدف) التالي تختار من العقد الجديدة التي تحتوي على أدنى مستوى إلخ.
تفعل الشيء نفسه كما كان من قبل حتى واحد من العقد الجديدة سيكون الهدف.

dijkstra يعمل تقريبا نفس الشيء. إلا أن المسافة المقدرة للاستهداف هي دائما 0، وخلع الخوارزمية أولا عندما يكون الهدف ليس واحدا فقط من العقد الجديدة, ، ولكن أيضا واحد مع أدنى CSF.

A * عادة ما يكون أسرع من dijstra، على الرغم من أن هذا لن يكون هو الحال دائما. في ألعاب الفيديو، تفضل غالبا "قريب بما فيه الكفاية للحصول على لعبة". لذلك "إغلاق ما يكفي" المسار الأمثل من ما يكفي عادة.