Skip to content

Instantly share code, notes, and snippets.

@breinero-zz

breinero-zz/Solution to Traveling Santa Problem

Created December 21, 2015 20:50
Download ZIP

Revisions

  1. breinero-zz created this gist Dec 21, 2015.
    126 changes: 126 additions & 0 deletions Solution to Traveling Santa Problem
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,126 @@
    // Usage:
    // in the mongo shell,
    // 'use' the database where the city data is loaded
    // and execute the following lines
    //
    //
    // load( "pathto/function.js");
    // db.cities.find().forEach( buildEdges );
    // findShortestPath();

    function Path(){
    this.distance = 0;
    this.visited = [];
    this.clone = function() {
    var newPath = new Path();
    newPath.distance = this.distance;
    for ( i in this.visited )
    newPath.visited.push ( this.visited[i] );
    return newPath;
    };
    }

    function compare( a, b ) {
    if (a.distance > b.distance )
    return 1;

    if( a.distance < b.distance )
    return -1;

    return 0;
    };


    function findShortestPath() {
    var path = new Path();
    path.visited.push( "North Pole" );
    path.distance = 0;
    var path = visit ( path );

    print( "Best path: { distance: "+path.distance+", path: ["+path.visited +" ] }" );
    }


    function visit ( path ) {
    // get last city visited
    var city = path.visited[ path.visited.length - 1 ];

    var paths = [];

    db.edges.find( { from: city } ).forEach (
    function( edge ) {
    // avoid cities I've already visited
    if ( path.visited.indexOf( edge.dest ) == -1 ) {

    // branch out a new path
    var newPath = path.clone();
    //print( "Adding the next edge "+edge.dest );
    newPath.visited.push( edge.dest );
    newPath.distance += edge.dist;

    //recurse
    paths.push( visit ( newPath ) );
    }
    }
    );

    if( paths.length == 0 ) {

    // if no new paths the tour is complete. Now go home!
    var lastEdge = db.edges.findOne(
    { from: path.visited[ path.visited.length -1 ],
    dest: path.visited[0]
    }
    );

    path.visited.push( path.visited[0] );
    path.distance += lastEdge.dist;

    print( "Path complete "+path.visited );
    paths.push( path );
    }

    paths.sort( compare );
    return paths[0];
    }

    // Functions for calculating distance

    function Edge( from, dest, dist ) {
    this.from = from;
    this.dest = dest;
    this.dist = dist
    }

    function toRadians( degree ) {
    return degree * Math.PI / 180;
    }

    function haversine ( start, end ) {
    var lat1 = start[1];
    var lat2 = end[1];
    var lon1 = start[0];
    var lon2 = end[0];
    var R = 6371000;
    var φ1 = toRadians( lat1 );
    var φ2 = toRadians( lat2 );
    var Δφ = toRadians(lat2-lat1);
    var Δλ = toRadians(lon2-lon1);

    var a = Math.sin(Δφ/2) * Math.sin(Δφ/2) +
    Math.cos(φ1) * Math.cos(φ2) *
    Math.sin(Δλ/2) * Math.sin(Δλ/2);
    var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));

    var d = R * c;
    return d;
    }

    function buildEdges ( start ) {
    db.cities.find( { _id: { $ne: start._id } } ).forEach(
    function ( end ) {
    var d = haversine( start.location.coordinates, end.location.coordinates);
    db.edges.insert( new Edge( start._id, end._id, d ) );
    }
    );
    }