Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>If I've understood your question correctly, so your cost function is as Haile describes in his/her comment, there's an easy solution since you can reduce to a one-dimensional problem.</p> <p>Note that in the Manhattan metric, the distance in columns that the cars must traverse is just summed with the distance in rows, so we can minimise them separately.</p> <p>So we've reduced the problem to one dimension. To work out what was going on, I had to switch this to a continuous problem. So suppose that I have a density function, p(x), (let's say it's continuous with compact support, so that the maths works). Then the cost function is given by</p> <p><img src="https://i.stack.imgur.com/Y3dAY.png" alt="\int p(x) |x-x0|"></p> <p>Splitting this into two halves to get rid of the mod sign and differentiating (this is where you need to assume p(x) is well behaved), you get</p> <p><img src="https://i.stack.imgur.com/gVzOr.png" alt="\int_-\infty^x_0 p(x) - \int_{x_0}^\infty p(x) "></p> <p>Now, the optimal position for x0 is going to be the one that makes this derivative zero. But notice that this is the median of the distribution.</p> <p>For the discrete setting, which was the original question, the same arguments work. Basically you can take a discrete derivative, which is E(k+1)-E(k). If you write a[n] for the number of cars at position n, then the cost function splits up as</p> <p><img src="https://i.stack.imgur.com/H1GNL.png" alt="E(k) = \sum_{n&lt;k} a_n(k-n) + \sum_{n&gt;k} a_n(n-k)"></p> <p>Assuming I haven't made a stupid mistake, the discrete derivative comes out as</p> <p><img src="https://i.stack.imgur.com/rVNRZ.png" alt="E(k+1)-E(k) = \sum_{n&lt;k+1} a_n - \sum_{n&gt;k+1} a_n"></p> <p>so the solution will be at the median again (rounded either way if you end up at a half-integer). To see why this is true, note that if k is a large negative number, this derivative is definitely negative (so increasing k by 1 will decrease the cost). Now, as k increases, the derivative slowly increases. At some point, it will become positive for the first time. This happens as soon as k+1 is larger than the median. After that, it will stay positive, so the correct k to choose is the largest k less than or equal to the median.</p> <p>The original question was in two dimensions, so you need to run this twice, once for each axis.</p>
    singulars
    1. This table or related slice is empty.
    1. POPetrol Pump establishment algorithm
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USRupert Swarbrick
    1. USRupert Swarbrick
    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. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI think so: Suppose we are in a 1d situation with cars spaced on the real line. Then the total distance travelled is the sum over cars of the distance between pump and that car. I'm pretty certain that this sum is minimised at the mean position of the cars.
      singulars
      1. PO
      1. USRupert Swarbrick
    2. CO(Er, that comment was in response to one that seems to have gotten deleted: it's meant to justify why taking the mean is the correct thing to do on each axis)
      singulars
      1. PO
      1. USRupert Swarbrick
    3. COsorry for deleting my comment, i wanted to double-check. anyway, imagine that there are just two populated blocks, one with 9 and the other with 10 cars - the optimal location is always in the cell with the 10 cars, although the mean location may vary
      singulars
      1. PO
      1. USstaafl
 

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