- Forum
- General C++ Programming
- greedy algorithm - advanced/theoretical
greedy algorithm - advanced/theoretical question
In order to connect 9 airports with the least number of flights, you'd just go round in a loop (think a ring). Thus, each city has 1 arrival and 1 departure and you can get to any city from any city (indirectly).
True, but I think that relies on a specific formation of the input file. But what if the input file renders that solution impossible to create? Or, what if 10 different airports each have some number of incoming/outgoing flights to all other 9 airports so it was one gigantic web?
Last edited on
Your using an existing network and adding flights to it to make it possible to fly from any city, to any other city directly correct?
Yes, if you change directly to "directly or indirectly". My apologies if I have explained this wrong.
So the purpose is to make it possible for a passenger to fly from one city in the network to any other city (it could take 5 connections) with the overall network having the smallest number of total flights (an intrinsic parameter for each airport).
The goal is the devise a solution that would work for a number of different airport networks.
So the purpose is to make it possible for a passenger to fly from one city in the network to any other city (it could take 5 connections) with the overall network having the smallest number of total flights (an intrinsic parameter for each airport).
The goal is the devise a solution that would work for a number of different airport networks.
Do you mean that you are inputting an invariant configuration of flight paths between the airports; some being one way, some having layovers, etc. and you want to walk the valid routes and determine which ones have the fewest layovers? I'm still not clear on what you mean by the number of flights; it sounds like you are saying a count of flights per day or something.
So far, it sounds like the airports should be modeled to store destinations and your algorithm might walk the destination "tree" counting the stops.
Additionally, you could model a route as an object and implement it's < operator to make comparing/sorting routes a snap!
So far, it sounds like the airports should be modeled to store destinations and your algorithm might walk the destination "tree" counting the stops.
Additionally, you could model a route as an object and implement it's < operator to make comparing/sorting routes a snap!
Last edited on
No, all flights are one-way in nature, meaning that there is a source airport, and a destination airport. You can think about the total goal of this sytem to "reduce airplane traffic as much as possible while still enabling all cities in the network to be connected (directly or indirectly through intermediary airports)".
I can see how this is confusing because it isn't completely intuitive... but say one route is from Las Vegas to Seattle and another route from New York to Seattle (I tried to use this as an example but probably was confusing).
Each of these routes has a number of total flights attached to it. Say the New York to Seattle route had 100 flights (again, all one-way) and the Las Vegas to Seattle route had 10 flights. In a vacuum, assuming no other interdependencies or flights to Seattle, the algorithm should take the Las Vegas to Seattle route.
I think it would be best to just think of it as a parameter for which to minimize, .... I guess you could even replace it with COST, it would still be the same thing.
***** Yes, let's assume that the number is COST because it makes more intuitive sense (i can worry about the number of flights thing on my own) ******
So, let's now say that the goal is to: "reduce COST as much as possible while still enabling all cities in the network to be connected (directly or indirectly through intermediary airports)".
I can see how this is confusing because it isn't completely intuitive... but say one route is from Las Vegas to Seattle and another route from New York to Seattle (I tried to use this as an example but probably was confusing).
Each of these routes has a number of total flights attached to it. Say the New York to Seattle route had 100 flights (again, all one-way) and the Las Vegas to Seattle route had 10 flights. In a vacuum, assuming no other interdependencies or flights to Seattle, the algorithm should take the Las Vegas to Seattle route.
I think it would be best to just think of it as a parameter for which to minimize, .... I guess you could even replace it with COST, it would still be the same thing.
***** Yes, let's assume that the number is COST because it makes more intuitive sense (i can worry about the number of flights thing on my own) ******
So, let's now say that the goal is to: "reduce COST as much as possible while still enabling all cities in the network to be connected (directly or indirectly through intermediary airports)".
Last edited on
If your starting off with an empty network. Then the greedy algorithm is merely going to do what I said. It'll start at one city and build a loop around each city. This gives you the smallest amount of possible flights. Each city has 1 inbound and 1 outbound.
e.g
New York to Seattle
Seattle to Boston
Boston to Detroit
Detroit to New York.
This isn't really a problem that fits the minimization of a function. You don't have any metrics or objective function to score the candidate solutions against.
e.g
New York to Seattle
Seattle to Boston
Boston to Detroit
Detroit to New York.
This isn't really a problem that fits the minimization of a function. You don't have any metrics or objective function to score the candidate solutions against.
Topic archived. No new replies allowed.