Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #14336 > unrolled thread

Problem C++ gas tank refuel

Back to article view | Back to comp.programming

Contents

  Problem C++ gas tank refuel Darioes <darioes078@gmail.com> - 2021-12-13 20:54 -0800
    Re: Problem C++ gas tank refuel Julio Di Egidio <julio@diegidio.name> - 2021-12-14 23:43 -0800
    Re: Problem C++ gas tank refuel Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-12-15 12:59 +0000
      Re: Problem C++ gas tank refuel Julio Di Egidio <julio@diegidio.name> - 2021-12-15 10:34 -0800
    Re: Problem C++ gas tank refuel Richard Heathfield <rjh@cpax.org.uk> - 2021-12-17 10:17 +0000
    Re: Problem C++ gas tank refuel Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-12-20 16:10 -0800
    Re: Problem C++ gas tank refuel Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-12-21 08:55 -0800

#14336 — Problem C++ gas tank refuel

Hi guys,



Im programing a new exerciese that i need to do for a college project, in C++.



That project consists in implementing an algorithm that just goes the minimal ways, not like Dijkstra’s algorithm but something similar: You are have a car, that needs to go from France to Corea and you need to refil your gas tank . You need to pick the minimal ways so that the car's fuel tank is as low as possible.



For example :



If the input is this:



From node 0 to node 1 cost 5



From node 0 to node 2 cost 4



From node 2 to node 1 cost 3



The algorithm should pick 0->2->1 . If you want to go from node 0 to node 1, the maximum car's fuel tank is 4. Firstly it seems easy as you can just pick the minimal ways, but in that example that doesn’t work :



From node 0 to node 1 cost 5



From node 0 to node 2 cost 4



From node 2 to node 1 cost 3



From node 2 to node 3 cost 6



From node 1 to node 3 cost 7



You should pick if you want to go from node 0 to node 3, 0->2->3, the car's fuel tank is 6.



This is what I think should be done, but it isn’t working. Do you have any ideas on how I can make it work?

int nodo = origen;
int minimo = INT_MAX;
while(nodo != destino){
     for (int j = 0; j < totalNodos; j++){      
            if(!visitado[j] &&  coste[nodo][j] < minimo){
                nodoMinimo = j;
                minimo = coste[nodo][j];
            }
        }
    nodo = v
    if(minimoTotal < minimo ) minimoTotal = minimo;
}

[toc] | [next] | [standalone]

#14337

On Tuesday, 14 December 2021 at 05:54:49 UTC+1, Darioes wrote:
> Hi guys, 
> 
> Im programing a new exerciese that i need to do for a college project, in C++. 
> 
> You need to pick the minimal ways so that the car's fuel tank is as low as possible. 

IOW, you need to pick the path such that the maximum cost of any single step is minimal.

> This is what I think should be done, but it isn’t working.

First you should decide the approach/algorithm: I suppose what you want to do here is a full, brute-force, search of all possible paths from origin to target and, for each path, compute the maximum cost of any single step (which you can do while building the path), and, if that cost is lower than what you have found for the paths visited so far, record this path as the new minimal in our sense.  At the end of the loop you will know which path is minimal overall. --  Right?

> Do you have any ideas on how I can make it work?
> 
> int nodo = origen; 
> int minimo = INT_MAX; 
> while(nodo != destino){ 
> for (int j = 0; j < totalNodos; j++){ 
> if(!visitado[j] && coste[nodo][j] < minimo){ 
> nodoMinimo = j; 
> minimo = coste[nodo][j]; 
> } 
> } 
> nodo = v 

Wasn't that supposed to be 'nodo = nodoMinimo'?  But that's not going to work anyway: minimal is a path, not a single step, of the single step you rather want to know if it is the maximum within that path...

> if(minimoTotal < minimo ) minimoTotal = minimo; 
> }

As a minimum, you seem to be missing pieces.  In particular, I assume 'coste' exists and is the adjacency matrix with graph connection costs that you get in input, but you are not showing how you initialise 'visitado' and you are only reading from it, which makes little sense anyway.

One way to approach programming problems in general is to decompose them.  Here you could as a first step write code that does the loop over all paths.  Once that works and, say, prints to the console all paths one after the other, you add another piece to it which is computing the maximum cost of the path's single step, and print that too along with the path.  Finally you add the piece that keeps track of the minimum such value found so far and which path was that, and at the very end of the loop now also prints that minimum together with which path was it.  And incrementally I suppose we can also help...

Julio

[toc] | [prev] | [next] | [standalone]

#14338

Darioes <darioes078@gmail.com> writes:

> Hi guys,
>
> Im programing a new exerciese that i need to do for a college project, in C++.
>
> That project consists in implementing an algorithm that just goes the
> minimal ways, not like Dijkstra’s algorithm but something similar: You
> are have a car, that needs to go from France to Corea and you need to
> refil your gas tank . You need to pick the minimal ways so that the
> car's fuel tank is as low as possible.

That last phrase is a little confusing.  The stages that make up the
final route have costs, and the route with the minimum cost is to be
found.

Look up depth first search.  I would do this recursively.  Keep a note
of the least cost so far and update it every time the search reaches the
destination.  When a search exceeds the least cost so far, update it.
Lots of details remain for you to work out...

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#14339

On Wednesday, 15 December 2021 at 13:59:23 UTC+1, Ben Bacarisse wrote:
> Darioes <dario...@gmail.com> writes: 
> 
> > Hi guys, 
> > 
> > Im programing a new exerciese that i need to do for a college project, in C++. 
> > 
> > That project consists in implementing an algorithm that just goes the 
> > minimal ways, not like Dijkstra’s algorithm but something similar: You 
> > are have a car, that needs to go from France to Corea and you need to 
> > refil your gas tank . You need to pick the minimal ways so that the 
> > car's fuel tank is as low as possible.
> 
> That last phrase is a little confusing.

Especially when one can't and won't read.

*Troll Alert*

Julio

[toc] | [prev] | [next] | [standalone]

#14342

On 14/12/2021 04:54, Darioes wrote:
> Hi guys,
> 
> 
> 
> Im programing a new exerciese that i need to do for a college project, in C++.
> 
> 
> 
> That project consists in implementing an algorithm that just goes the minimal ways, not like Dijkstra’s algorithm but something similar: You are have a car, that needs to go from France to Corea and you need to refil your gas tank . You need to pick the minimal ways so that the car's fuel tank is as low as possible.

Step 1: Using a permuting algorithm such as Heap's algorithm 
<https://en.wikipedia.org/wiki/Heap%27s_algorithm> evaluate the 
essential tank size required for each possible route, keeping track of 
the minimum as you go.
Step 2: print the answer.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#14348

On Tuesday, 14 December 2021 at 04:54:49 UTC, Darioes wrote:
> 
> That project consists in implementing an algorithm that just goes the minimal ways, not like Dijkstra’s algorithm but something 
> similar: You are have a car, that needs to go from France to Corea and you need to refil your gas tank . You need to pick the minimal 
> ways so that the car's fuel tank is as low as possible. 
> 
So the question is a bit different from the one anyone would expect. Instead of minimising
fuel consumption, you are minimising the size of the fuel tank you need. So we need the route
with the lowest maximum weight.

Richard Heathfield has suggested enumerating all paths, then taking the best. This will work, and
what you should do as a first attempt. However it is O(N!) in complexity. So it's only feasible for very 
small networks.

To go faster, sort allthe edges by weight. Now clearly the path through the maximum weight edge is
the worst. So eliminate it. Does a path from origin node to destination node still exist? If so, eliminate
the next maximum weight edge. Repeat until eliminating an edge disconnects the destination from
the origin. You must go through that edge, and that's your answer.

[toc] | [prev] | [next] | [standalone]

#14354

Darioes <darioes078@gmail.com> writes:

> Im programing a new exerciese that i need to do for a college
> project, in C++.
>
> That project consists in implementing an algorithm that just goes
> the minimal ways, not like Dijkstra's algorithm but something
> similar:  You are have a car, that needs to go from France to Corea
> and you need to refil your gas tank . You need to pick the minimal
> ways so that the car's fuel tank is as low as possible.

Assuming that I understand correctly what you are looking for,
this problem is a standard graph shortest path problem.  The
only difference is adding a new link to a path uses MAX rather
than addition.  The "distances" involved are still monotonic,
so the conventional algorithm works, just using MAX rather than
plus.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web