CODEWITHSUNDEEP
algorithmsortingmathematical-optimization
Flot2011
Flot2011

Reputation: 4671

Cost minimizing algorithm (time limited)

Let's say I have a group of N people who is going to travel by train. I need to organize them in a line to the ticket office in a way that minimizes the total tickets cost. The cost can be minimized if families buy family tickets and people travelling to the same destination buy group tickets.

I do not know who of these people are families and where are they travelling.

All I can do is to send any M (1 <= M <= N) of them to the ticket office and get the answer, how much it will cost for these M people.

I also have a limited time, as a train is leaving in some minutes, so the near best solution is good enough for me.

The brute force solution is O(N!) and so is obviously unacceptable.

EDIT

The answer from the ticket office is always the total sum for M people, no details.

Group and/or family may start at 2 people and may include all N of them.

The cushier in the tickets office will always know who is a family and who is not.

EDIT

If I am sending to the tickets office a family and some more people, the family will not get a family ticket, they all will get their regular tickets.

Upvotes: 2

Views: 663

Answers (1)

amit
amit

Reputation: 178521

Since you mentioned you can settle for 'good enough', and you are time limited - here is a greedy any-time approach:

  1. p <- Create a random permutation
  2. estimate the cost of this permutation. (let that be cost)
  3. Find a new permutation p' such that cost(p') < cost(p) that is achieved from p using a single swap of two people (there are n(n-1)/2 such possible swaps)1
  4. If such p' exist: p <- p' and return to 2.
  5. Else, store p as a local minimum, and return to 1.
  6. When time is up - choose the best local minimum found.

This is basically a variation of steepest ascent hill climbing with random restarts.

Note that if your time->infinity, you will find optimal solution, because the probability of checking any possible permutation is getting closer and closer to 1 as time passes.

(1) getting the price can be done by first checking who is a family member/going to the same destination and is adjacent to each other in the permutation at O(n)using the fact that d(passenger1,passenger2) < d(passenger1) + d(passenger2), and then checking each group separately.

Upvotes: 3

Related Questions