А-звезда медленнее, чем Дейкстра - PullRequest
Новая
       36

А-звезда медленнее, чем Дейкстра

0 голосов
/ 05 мая 2018

У меня есть неприятная ошибка, которую я не могу решить в течение достаточно долгого времени. Я реализовал Maze Solving, используя A * (A-star) и Dijkstra в Python, и мой A * на самом деле медленнее, чем Dijkstra.

Эта часть одинакова для обоих: 

    open_list={}

    dist=dict([(v, float('inf')) for v in self.adj_list])
    dist[start]=0

    parents=dict([(v,None) for v in self.adj_list])

    marked={}
    marked[start]=True
    while open_list:
        (tmp,val)=min(open_list.items(), key=lambda x: x[1])
#take current minimum from open_list, add it to closed list and
#remove it from open_list

        del open_list[tmp]

        #if we found exit
        if tmp == stop:
            path=deque([])

            while parents[tmp]:
                path.appendleft(tmp)
                tmp=parents[tmp]

            path.appendleft(start)
            return list(path)

A *: 

 for v,w in self.adj_list[tmp]:
            if v not in marked:
                marked[v]=True

                dist[v]=dist[tmp]+w
                open_list[v]=dist[v]+self.h[v]

                parents[v]=tmp

            elif v in open_list:
                if dist[v] > dist[tmp]+w:#better path exists
                    dist[v]=dist[tmp]+w
                    parents[v]=tmp
                    open_list[v]=dist[v]#update value in open_list

Дейкстр: 

for v,w in self.adj_list[tmp]:
            if v not in marked:
                marked[v]=True

                dist[v]=dist[tmp]+w
                open_list[v]=dist[v]

                parents[v]=tmp

            elif v in open_list:
                if dist[v] > dist[tmp]+w:
                    dist[v]=dist[tmp]+w
                    parents[v]=tmp
                    open_list[v]=dist[v]

Как вы можете видеть, они одинаковы (за исключением эвристической части в A *), но по какой-то причине A * работает медленнее и попадает в if dist[v] > dist[tmp]+w:#better path exists этой ветви гораздо чаще. Эвристика хорошая, я проверял несколько раз

Есть идеи?

Если вы хотите попробовать, здесь - это Github repo

...