Databases
StackOverflow2013
Postsdbo
POCalculate shortest path through a grocery store
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POCalculate shortest path through a grocery store
    primarykey
    data
    text
    <p>I'm trying to find a way to find the shortest path through a grocery store, visiting a list of locations (shopping list). The path should start at a specified start position and can end at multiple end positions (there are multiple checkout counters). Also, I have some predefined constraints on the path, such as "item x on the shopping list needs to be the last, second last, or third last item on the path". There is a function that will return true or false for a given path. Finally, this needs to be calculated with limited CPU power (on a smartphone) and within a second or so. If this isn't possible, then an approximation to the optimal path is also ok.</p> <p>Is this possible? So far I think I need to start by calculating the distance between every item on the list using something like A* or Dijkstra's. After that, should I treat it like the traveling salesman problem? Because in my problem there is a specified start node, specified end nodes, and some constraints, which are not in the traveling salesman problem. </p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USBill the Lizard
    1. USBart
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POCalculate shortest path through a grocery store
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POCalculate shortest path through a grocery store
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POCalculate shortest path through a grocery store
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO@Bart: You want to solve the TSP ... on a smartphone ... in a second or so. I think you are going to have a hard time - unless it is a very short list :) Have you tried a simple heuristic/greedy approach? Since most supermarkets have euclidean distance it might give a "good enough" solution. Also I think it might make more sense for humans viewing the result if you do something, that resembles what we would actually do. It might mean a 15 meter longer walk, but I still think most humans would do something akin to what is described by ndp. And be baffled if they were told to do otherwise.
      singulars
      1. POCalculate shortest path through a grocery store
      1. USMads Ravn
    2. COEdit: 'Since most supermarkets have euclidean distance it might give a "good enough" solution' should read 'Since distances in supermarkets will satisfy the triangle in ineq., it might give a "good enough" solution'
      singulars
      1. POCalculate shortest path through a grocery store
      1. USMads Ravn
    3. COThanks. An imperfect path would be fine, but it would be nice if it could find the optimal path when the number of items it small, and an approximation if the number of items is large. This is just a theoretical assignment by the way, so I don't have to implement anything. I'm thinking maybe Ant Optimization would be good, since I can just cut it off at some time limit and get the best approximation found so far.
      singulars
      1. POCalculate shortest path through a grocery store
      1. USBart
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload