0
$\begingroup$

I have the following problem: Let's say I'm in a city with some friend we have a bunch of tasks to do. All persons start on a different position, for example (0/0), (10/5), (-20/0), ... , and every person can move x coordinates per second. Every task has:

  • A coordinate where it can be completed (for example (40/50))
  • A importance value ranging from 0 to X (for example importance = 5)
  • A time that is needed to complete this task

Also, some tasks can only be done if a certain other task has already been completed.

Now comes the tricky thing: The group has a certain time, in which they can complete tasks. They now need to choose which tasks they want to complete, the goal is that the summarized "importance value" of the completed tasks is as high as possible. The group is also allowed to split up.


I tried to bruteforce it, but that didn't work out. There are around 11 tasks usually and 4-6 can be done, resulting in up to a million and something possiblities. Also, I had a solution without calculating the time needed to travel between the points which was basically calculating a importance per time value and just doing the tasks based on this value... which won't work for the full problem.

$\endgroup$
  • $\begingroup$ After some thinking i tried to bruteforce it, but that didn't work out. There are around 11 tasks usually and 4-6 can be done, resulting in up to a million and something possiblities ... Edit: Also, i had a solution without calculating the time needed to travel between the points which was basically calculating a importance per time value and just doing the tasks based on this value ... which won't work for the full problem :/ $\endgroup$ – Random Noob Apr 2 '15 at 16:22
  • 2
    $\begingroup$ But did you try for a single person? (I do not know the answer, but I would try that first. $\endgroup$ – babou Apr 2 '15 at 16:30
  • $\begingroup$ yes, i did it for a single person and without the time needed to travel between points. I do not know how to continue though $\endgroup$ – Random Noob Apr 2 '15 at 16:31
  • 1
    $\begingroup$ You have to begin by a topological sort, afterward.. do you want an exact algorithm or an approximation algorithm is enough ? $\endgroup$ – François Apr 3 '15 at 6:01
-1
$\begingroup$

Depending on how you want to model the problem, you can approach it in several ways. Since it seems like you are working with an imaginary 2D plane I will start with the most relevant options.

Arrange waypoints. Obviously if X comes before Y, then with lower precedence if X is easier than Z. You will need a difficulty function which will depend primarily on distance to the waypoint, which means that you will probably need to calculate the path from every other possible waypoint and then calculate according to the path. (Though I may be missing some nice method to solve this).

EDIT: To clarify, you need to determine the best order of steps, first in relation to one another (if Y requires X), and then in order of optimal path (see below). This isn't an algorithm, it is a necessary prerequisite for further calculations. If you don't do this then the brute force method below will be extremely resource hungry.

A* path finding (to calculate difficulty from each 'end point'). By 'end point' I mean the initial location and the location of every other objective. This method is inefficient, especially when you have lots of waypoints, but it has obstacle navigation built in if you need it, and once each waypoint has a path length value relative to every other waypoint, you can use simpler functions to approach the objective sequence.

EDIT: This is useful instead of drawing a direct path in the case of obstacles. It will calculate the shortest distance from point A to point B with and without obstacles in the way. WIKIPEDIA

Brute force paths. This is a starting point for what should be a better algorithm. Calculate every possible configuration (I would use a branching method to simplify the concept) and remove less optimal ones after calculating scores.

def NextStep(Plan,Steps,ID): ##Warning: written at 5AM. Run at own risk.
    if len(Steps)==0:
        print "Possible plan: ",ID; ALL_THE_PLANS.append(Plan);
        return;
    for s in Steps: ##Uncomment next line for multiple people.
      #for ppl in PEOPLE:
        temp_plan = Plan; temp_steps = Steps; #Use ID.copy() for objects.
        temp_id = ID+"Then "+ppl+" does "+s;
        temp_plan+=Steps[s]; temp_steps.replace(Steps[s],""); #Or .remove
        NextStep(temp_plan, temp_steps, temp_ID);
        #This will recurse until all possible arrangements are calculated.

Once you have a list of all paths you can remove those which break the rules (ie Y before X). Note that it helps to do this BEFORE calculating the paths, but it is still very slow and you should try to rewrite the above code to skip illegal plans.

PPL = ALL_THE_PEOPLE_IN_THE_GROUP()
for P in PLANS:
    p = PLANS[P] ##Just makes my job easier...
    STEPS = p.Objectives ##...And the code looks nicer.
    ##Assume that all PPL have .Location == START_POINT
    for O in STEPS:
        p.DIST+=AStar(PPL[O.Person].Location,OBJS[O].Location).Dist;
        #Add the distance that the person will travel from their last
        # location to the objective to the total distance of this plan.
        PPL[O.Person].Location=OBJS[O].Location;

Now just use some imagination... Get the PLAN with the smallest DIST.

Other approaches. You could also model the problem mathematically and try using other optimizing methods here. I'm not sure how applicable any of these are since it is 5AM and I can't think of ways to remodel your problem, but I will make you aware of them in case you aren't in the hopes that someone benefits.

  • Neural networks
  • Finite State Automata
  • Genetic algoritms
  • Minimax (probably only applicable in a 2-player version)

Hope I could help!

$\endgroup$
  • $\begingroup$ 1. I can't understand what you are saying in the paragraph marked "Arrange waypoints". (For instance, I can't parse the first sentence. And, I can't see any algorithm suggested here.) Might you be able to try editing that to explain? 2. Why A* rather than shortest paths? 3. The problem is easy if there is only one person. The challenge comes when there are multiple people (since this introduces some dependencies between people: if my friend does a task, there's no point in me doing it too). I don't see anything in your answer that explains how to handle multiple people. $\endgroup$ – D.W. Apr 3 '15 at 23:48
  • $\begingroup$ 1. Clarified. This is not an algorithm, it is a step. 2. A* is the shortest path, is just allows for obstacles, which tend to exist in a city scenario. 3. Added to the code, please read it carefully as it is fairly simple and explains the simplest method of solving this problem. Multiple people are simply a matter of calculating from the last objective point for that person (or the start point). $\endgroup$ – Marked Verbs Apr 4 '15 at 8:01
  • $\begingroup$ I think simulated annealing can do well here too. $\endgroup$ – Albert Hendriks Jun 3 '15 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.