2
$\begingroup$

There are some algorithm or solving a simple maze on the web; but what I am trying to solve is a bit more complicated. Here is an example:

####################
#S #D #           #
#  # ##  ##  ###D###
#     #   #   #    #
## #  #   #     ## #
#     ### #####    #
# #   #  D#  #   ###
# ### ### ## # #####
#   #     #       E#
####################

S represents the StartPoint; E represents the EndPoint. D(s) are the collecting point. I want to find the all the paths from S to E which go through D. Then I want to distinguish the shortest path.

Here is an example of A* algorithm, How can I assure that paths go through D points.

def aStar(self, graph, current, end):
    openList = []
    closedList = []
    path = []

    def retracePath(c):
        path.insert(0,c)
        if c.parent == None:
            return
        retracePath(c.parent)

    openList.append(current)
    while len(openList) is not 0:
        current = min(openList, key=lambda inst:inst.H)
        if current == end:
            return retracePath(current)
        openList.remove(current)
        closedList.append(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                if tile not in openList:
                    openList.append(tile)
                tile.parent = current
    return path

My question is that How i can modify above search algorithm so that it passes through all D points. I want all the paths included D points.

$\endgroup$

marked as duplicate by David Richerby, FrankW, Rick Decker, Juho, D.W. Oct 17 '14 at 3:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Blckknght in stackoverflow suggested that: Probably the best approach is to use A* to find the shortest paths from S to each D point and from each D to each other D and to E, then use a separate method to solve the traveling salesman problem using the distances from A*. – Blckknght $\endgroup$ – H'H Oct 14 '14 at 15:19
  • $\begingroup$ for that I have to find and sort all D then. Is it correct? $\endgroup$ – H'H Oct 14 '14 at 15:20
  • 1
    $\begingroup$ Crossposted to Stack Overflow and Computer Science SE. Please do not do this: it is against site policy because it fragments answers and wastes people's time when they duplicate contributions that already exist elsewhere. $\endgroup$ – David Richerby Oct 14 '14 at 15:37
  • $\begingroup$ The approach from SO sounds reasonable. $\endgroup$ – FrankW Oct 14 '14 at 15:37
  • $\begingroup$ @DavidRicherby sorry I was not aware of that. $\endgroup$ – H'H Oct 14 '14 at 20:48