A * - Heuristic of graph traversal

Question

I have a graph representing a city. I know the location of places of interest (nodes that matter), the location of the hotel where I stay, how the nodes connect, the transit time between them and the distance to latitude and longitude. There are no problems associated with the transition of time to distance and vice versa.

The goal is to tour the city, maximizing the importance of the day, but limiting one day of travel to 10 hours. The day begins and ends at the hotel. I have a working A * algorithm that selects the lowest value, but without heuristics, which, in my opinion, is now BB. With that in mind:

• Since I have access to Lat / Long, my first blow to heuristics, while only dealing with time, there will be a distance, like a crow between a node hotel and a hotel. Will this be a valid heuristic? This gives me the shortest distance and time, so he will not overestimate.

Now let's say that the node value is between 1-4. To enable it, one idea could be g (neighbor) = g (current) + (edge_cost / value ^ 2). Assuming this will be valid (if not, why?):

• But now heuristic values ​​will be in another block. Can a solution to this simply give Hotel Value = 1? If the value is the same, will it be acceptable? EDIT: I think this will eventually give me problems due to the difference in scale.
• I still have to limit the total time. If each node tracks the total time spent comparing with the limit, plus the values ​​of g () and h () due to different units?

And finally:

• Since I have to start and end in the same node that comes to my mind to explore the node and I have to find the hotel to see if I still have time to explore the neighbors instead of going back. However, if I still have time to go to another node, but time runs out, and I cannot get to the hotel from there, I assume that I will have to go back to my parents.
• I cannot help but see the similarities with the backpack problem. Although I have to use A *, is there a lesson I can learn from it?
• Should my heuristic be consistent in this case? If so, why?

By the way, the goal here is to find the path first, the second optimization.

Answer 1

It actually looks like a combination of Traveling Salesman Problem (TSP) and Backpack Problem (KP). This is KP in this regard: the backpack has a capacity of 10 (the total number of hours available per day), and items are places. The value of the item is equal to the value of the location. The weight of the item is equal to the time it takes to travel to the place (plus part of the place of travel back to the hotel). The problem arises due to the fact that the weight of the item is unknown, until you decide the optimal tour to the selected places - enter TSP and Pathfinding.

One approach may be to use a path search algorithm (for example, the A * algorithm, Bellman-Ford or Dijkstra), primarily to calculate the distance matrix between each node. Then the distance matrix can be used to solve part of the TSP problem: finding a tour by location and using the total time as a weight.

The next step is up to you. If you are looking for an approximate solution, there are many heuristics for TSP and KP: see Christofides TSP Heuristic or Minimum TSP and Maximum Backpack for NP Optimization Problem Collection .

If, on the other hand, you are looking for the best solution, you might be out of luck. However, I recommend that you find a copy of graph theory. Algorithmic Approach by Nikos Christofides (ISBN-13: 978-0121743505). It provides heuristics for early return in Deep-First-Search mode, which speeds up the search for optimal solutions for several NP-Complete problems.