last day (17 days later) » 

09:19
0
Q: Problem of the traveler in the desert, greedy and dynamic approach

Moudjahed MohamedA traveler in a desert wants to move from one oasis to another to a final destination without taking the risk of dying of thirst (ie lack of water). It knows the position of all the oases from its starting point to its final destination. The traveler must drink a liter of water for each kilometer...

"We must also take into account the amount of water emptied at the final destination" - take into account how?
Okay, the phrasing is awkward but I think I see - he pays for what he has left at each oasis, not for what he needs?
I'm not clear in your equations - why are you subtracing C? You refill fully, so it should just be (CMax - distance)^2, right?
We have to take them into account that the traveler must have enough water even to go to the final destination Each time if the traveler decides to stop in an oasis he must refuel and pay what it takes for the bottle to be filled. For example if the 4L bottle and its capacity is 10L, it will have to pay 6L of water, so 6² euros
Okay, so he has to pay that at the final destination as well?
(Cmax - Distance)^2 It is only if the full has been done. If the full has not been done you have to do (Cmax - (C -discount)) ², C being the number of liters of water remaining in the bottle
He does not pay when he arrives at the final destination I think, he must just pay to go there
Okay, I don't think you need the C term - in the equation you wrote out, the left hand side of the < represents the total cost if you stop at B and the right hand side represents the cost if you don't, right? In every term you're showing the distance since you last refilled, so the bottle always "starts" full.
Could you rephrase the part you're confused by? Sorry, I think there's a bit of a language barrier
09:19
Yes, if we decided to estimate the cost of a stop with a bottle not full the equation would be (cmax - (c - (distance)))^2. And if the bottle is full the equation would then be (cmax - (distance)) 2
I must first try to make a greedy algorithm to answer the problem. But I don't think I have the logic
What exactly is C in that equation? And when exactly was the bottle not full? I feel like the only time we should do this equation is when distance is the distance to the last oasis we stopped at, i.e., when the bottle was full.
So A: do you understand what a greedy algorithm is in general, and B: can you double check if you have to pay to refill at the last point or not? I can't tell from your post.
A greedy algorithm is an effective algorithm that could answer the question, not necessarily optimal and not brutforce either by listing all possible cases. And yes sorry we have to pay the final destination
Not quite, a greedy algorithm is more specific - it's an algorithm that makes a locally optimal choice by some heuristic. Greedy algorithms are generally very fast, because they don't involve backtracking or trying to wrangle the possibility space as a whole - you just have to make sure they're accurate, because sometimes locally optimal is not globally optimal.
In this case a good local heuristic to optimize might be "How much am I paying for liter of water consumed on this leg of the trip?"
I had thought about this kind of approach for the dynamic aspect by creating a matrix or the columns corresponds to the number of liters consumed and the lines to the number of oasis traveled. But I don't really know how to complete the elements of the matrix (the cost) intelligently. I tried without success
For the greedy approach I tried to do something in python but it doesn't work well, I think my logic is flawed
(if you understand French it would help me a lot for communication)
If you edit your python code into the question that might be best - I can help understand what's going wrong. For the dynamic one, think about how you're breaking it up into subproblems.
09:19
Sorry I'm new to this forum, I don't know how to insert code. I am not asked to make a python program, my program is incomplete but I can still show it to you
So there's an "edit" button just under the text of your question, click that and then paste in code. To make it format as code there are some buttons along the top of the text box. Surrounding a block with single `s will make it format as code inline, or three ``` will make a section appear as code.
I'll check in later today and see if I can help
I added (it's incomplete it's just so you can see what I started with and it doesn't work well), I don't need the code corrected, I will need help with logic or with pseudo code please
So my first thought is still that the C variable isn't helping anything - don't keep track of current water, just keep track of the distance where you last filled it.
Also, as a general word of advice, the sooner you stop naming variables things like d_i0_i1 the happier everyone will be - give them verbose names if you have to, but give them clear names. (Eventually you'll get in the habit of having fewer variables, because you'll be reusing more code in neatly composed functions.)
I do think you've gotten some logic crossed - I'm not really able to see the algorithm you're trying to use, from reading your code. Dynamic programming is all about breaking problems up into sub-problems, such that the solutions to those sub problems can be re-used. I think you have some of that there, but you'd be better off - I think - tossing your current code, really reviewing the logic on paper, and then re-implementing. Trying to fix a mess (even a mild mess) is much harder than starting over.
For this problem, I suggest your sub-problem relationship should be framed as cost(current, lastStop) = min(cost(next, lastStop), cost(next, current) + distance(lastStop, current)**2). Try just implementing that recursively, then see about saving the results of sub-problems in some sort of array.
 
2 hours later…
11:16
Thank you for your answer, I am trying to implement an algorithm in python but I do it, it returns me 0
def _cost(oasis1, oasis2, lastStop, d, Cmax, C, i) :

    if i == len(d)-1 :
        #We pay the rest arrived at the final destination
        return (Cmax- C)**2

    current = d[i]
    next = d[i+1]
    price = (Cmax-(C-(lastStop-current)))**2

    #We have water left
    if C-(next-lastStop) >= 0 :
        return min(_cost(next, lastStop, lastStop, d, Cmax, C-(next-lastStop), i+1), _cost(next, current, current, d, Cmax, Cmax, i+1) + price)
    #We don't have enough water we have to stop and refuel
 
9 hours later…
19:56
C is the current amount of water remaining, right? I still think that's not a useful parameter. Look at your function header: oasis1, oasis2, lastStop, d, Cmax, C, i. d is where we are now, right? And you can never refill to less than full. So the current water we have remaining will always be Cmax - (d[i] - lastStop) - i.e., less by the distance since the last stop. There's no need to track C as its own parameter, and I think doing so will only lead to bugs.
In general you have too many parameters. There should be a total of four: The maximum water (cMax), the array of oases (d), the position of the last stop (lastStop), and the index of the current stop (i). You have an additional three - oasis1, oasis2 and C, none of which are needed, and including them will only make it harder to figure out what the recursive call should be.
I think I see a few places where you're mis-using or miss-assigning C, but it's really not worth going over them. It's better to just get rid of that parameter altogether.

  last day (17 days later) »