Created
March 2, 2012 23:15
-
-
Save cstrahan/1962206 to your computer and use it in GitHub Desktop.
The A* algorithm, applied to finding airports routes with a given maximum leg distance.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# About: | |
# A flight planning algorithm, particularly useful for private pilots. | |
# The idea is that one might be interested in, say, flying into LED (in Russia) | |
# from DCA (in DC); bearing in mind that small aircraft can only go so far | |
# on a single tank of gas, this algorithm will perform the hard work of | |
# computing a rather tricky route. | |
# | |
# Concretely: | |
# Given a set of airports (and their code, latitude and longitude), | |
# find the shortest route between any given airport A and B, | |
# where any given leg is <= N miles. | |
# | |
# For the curious, this is, more or less, an implementation of A*. | |
require 'csv' | |
require 'algorithms' | |
require 'faster_haversine' | |
# The airport data structure. | |
class Airport | |
# The properties of an airport. | |
attr_accessor :code, :name, :lat, :lon, :elevation | |
# Returns an array of all the airports from a given CSV. | |
def self.from_csv(path) | |
# Keep CSV from complaining about illegal quotes. | |
options = {quote_char: '$'} | |
airports = CSV.read(path, options) | |
airports.map! do |array| | |
airport = Airport.new | |
airport.code = array[0] | |
airport.name = array[1] | |
# Radians to degrees | |
airport.lat = array[2].to_f * 57.29577951308232 | |
airport.lon = array[3].to_f * 57.29577951308232 | |
airport.elevation = array[4] | |
airport | |
end | |
airports | |
end | |
# Calculates the Haversine distance between this airport and the one given. | |
def distance_to(airport) | |
kilos = FasterHaversine.distance(self.lat, self.lon, airport.lat, airport.lon) | |
kilos / 1.609344 | |
end | |
end | |
# A simple undirected graph. | |
class Graph | |
def initialize | |
@graph = {} | |
end | |
# Gets all adjacent nodes of a given node. | |
def [](node) | |
@graph[node] | |
end | |
# Adds an edge to the graph, consisting of nodes a and b. | |
def add_edge(a, b) | |
(@graph[a] ||= []) << b | |
(@graph[b] ||= []) << a | |
self | |
end | |
# All nodes within the graph. | |
def nodes | |
@graph.keys | |
end | |
end | |
# The furthest distance that we think someone might query for. | |
# When we create the graph, we will only connect nodes (airports) | |
# that are within this distance. | |
max_distance = 700 | |
# Load up the airports from the CSV. | |
airports = Airport.from_csv("airports.csv") | |
# Obtain all combinations of size 2. | |
combinations = airports.combination(2) | |
# Populate the graph. | |
graph = Graph.new | |
combinations.each do |a, b| | |
graph.add_edge(a, b) if a.distance_to(b) <= max_distance | |
end | |
# This is the A* algorithm. | |
# `start' and `goal' can either be an instance of Airport, | |
# or the airport code as a string. | |
def find_path(graph, start, goal, max_distance) | |
start = graph.nodes.find {|a| a.code == start} if start.is_a?(String) | |
goal = graph.nodes.find {|a| a.code == goal} if goal.is_a?(String) | |
visited = {} | |
queue = Containers::PriorityQueue.new | |
queue.push([start, [], 1], 1) | |
until queue.empty? | |
spot, path_so_far, cost_so_far = queue.pop | |
next if visited[spot] | |
visited[spot] = true | |
newpath = path_so_far + [spot] | |
return newpath if spot == goal | |
graph[spot].each do |newspot| | |
next if visited[newspot] | |
distance_to_newspot = spot.distance_to(newspot) | |
if distance_to_newspot <= max_distance | |
newcost = cost_so_far + distance_to_newspot | |
priority = -1 * (newcost + newspot.distance_to(goal)) | |
queue.push([newspot, newpath, newcost], priority) | |
end | |
end | |
end | |
nil | |
end | |
# Given a graph of all airports, | |
# find the shortest route between DFW and BWI, | |
# where any given leg is <= 100 miles. | |
path = find_path(graph, "DFW", "BWI", 100) | |
puts path.map(&:code).join(", ") | |
# Output: | |
# DFW, 46TS, XS30, DEQ, 4AR6, RBM, 4AR5, 93AR, HZD, 36TN, 4KY1, 53KY, JKL, K22, WV01, WV52, 9VA4, 98VA, BWI |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
What an amazing gist.