graph theory - How's A* able to abandon a non efficient path following a better one? -

-

consider a* algorithm.

in google possible find pseudo-code:

function a*(start,goal)      closedset := empty set                 // set of nodes evaluated.           openset := set containing initial node // set of tentative nodes evaluated.      came_from := empty map                 // map of navigated nodes.      g_score[start] := 0                        // distance start along optimal path.      h_score[start] := heuristic_estimate_of_distance(start, goal)      f_score[start] := h_score[start]           // estimated total distance start goal through y.      while openset not empty          x := node in openset having lowest f_score[] value          if x = goal              return reconstruct_path(came_from, came_from[goal])          remove x openset          add x closedset          foreach y in neighbor_nodes(x)              if y in closedset                  continue              tentative_g_score := g_score[x] + dist_between(x,y)               if y not in openset                  add y openset                  tentative_is_better := true              elseif tentative_g_score < g_score[y]                  tentative_is_better := true              else                  tentative_is_better := false              if tentative_is_better = true                  came_from[y] := x                   g_score[y] := tentative_g_score                  h_score[y] := heuristic_estimate_of_distance(y, goal)                  f_score[y] := g_score[y] + h_score[y]                  update(closedset,y)                    update(openset,y)         return failure   function reconstruct_path(came_from, current_node)      if came_from[current_node] set          p = reconstruct_path(came_from, came_from[current_node])          return (p + current_node)      else          return current_node

well there 1 thing not understand: consider have situation in picture:

enter image description here

how a* able change a->b->c a->d... ??? mean, a* starts node , navigates through nodes. @ point node have more 1 neighbour, well, a* able follow path generated neighbour, @ point able switch... , come on steps starting previou node , taking different road if abandoned path did't cross one...

in code, what's condition enables envirinment?

a* generalization of dijkstra's algorithm, again generalization of breadth-first search (bfs). looks might confused "path switching" because think of search operation resembling depth-first search (dfs). dfs follows path end, backtracks little bit , tries other paths, backtracks further, , on. corresponds how perform search operation in real life (i.e., if had find way out of labyrinth). bfs, on other hand, maintains queue of nodes intends visit. in each iteration, picks node front of queue, examines neighbours , adds unvisited neighbours of queue. proceeds next node @ front of queue. not possible in real life, require ability teleport between different nodes. :-) dijkstra , a* based on same idea, use priority queue instead, in select "unfinished" node closest start node. algorithms built around idea of always switching paths: investigate node presently seems offer best path.


Comments

Post a Comment

Popular posts from this blog

Javascript line number mapping -

-
magically formatted comments change reported line number of javascript errors in browsers; this: //@line n "f" n line number , f file name. unfortunately, //@line appears ungoogleable. know there documentation on feature, , browsers support it? (i found references here , here .) from can find available in mozilla based browsers. it using js_setoptions command can turn these options on or off depending on values passed. https://developer.mozilla.org/en/js_setoptions
Read more

c# - Is it possible to remove an existing registration from Autofac container builder? -

-
something along lines: builder.registertype<mytype>().as<itype>(); builder.registertype<mytype2>().as<itype>(); builder.deregistertype<mytype>().as<itype>() var container = builder.build(); var types = container.resolve<ienumerable<itype>>(); assert.istrue(types.count == 1); assert.istrue(types[0].gettype == typeof(mytype2)); scenario: go through bunch of assemblies , go register types want make sure have 1 implementation of given type. need before create container. track on own nice if autofac me bit. this cannot done directly using containerbuilder , unless start on new one. mind you, having first built container should able construct new container filtering away unwanted types , reusing registrations first container. this: ... var container = builder.build(); builder = new containerbuilder(); var components = container.componentregistry.registrations .where(cr => cr.activator.limittype != typ...
Read more

php - Mysql PK and FK char(36) vs int(10) -

-
i have read mysql can handle indexes , searches better if tables keys integers rather char(36) uuid's. is worth converting int(10)? note: use 1 server , have have plans use multiple databases concurrently therefore removing 1 of big reasons using uuid. our tables innodb if makes difference. thanks in advance. usually rdbms can handle integer keys pk more efficient, other datatypes. reason how build index column, yes: long dont require string (or other typed) keys, should use integers. however: char(36) , int(10) far away being equal, because int(10) much smaller, char(36). dont know, if require many different keys, should keep in mind. update, complete last paragraph: int(10) 32-bit, char(36) 36 - ^byte^ (= 288-bit). not mean, int consumes less space, means, char(36) has 4 times more different keys.
Read more