1. Forum
  2. Usenet
  3. COMP.PROGRAMMING

  • Problem C++ gas tank refuel

    From Darioes@21:1/5 to All on Mon Dec 13 20:54:47 2021
    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;
    }

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Julio Di Egidio@21:1/5 to Darioes on Tue Dec 14 23:43:44 2021
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Ben Bacarisse@21:1/5 to Darioes on Wed Dec 15 12:59:20 2021
    Darioes <[email protected]> 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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Julio Di Egidio@21:1/5 to Ben Bacarisse on Wed Dec 15 10:34:20 2021
    On Wednesday, 15 December 2021 at 13:59:23 UTC+1, Ben Bacarisse wrote:
    Darioes <[email protected]> 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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Richard Heathfield@21:1/5 to Darioes on Fri Dec 17 10:17:53 2021
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Malcolm McLean@21:1/5 to Darioes on Mon Dec 20 16:10:47 2021
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Tim Rentsch@21:1/5 to Darioes on Tue Dec 21 08:55:46 2021
    Darioes <[email protected]> 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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)