Skip to content

fuscofrancesco/naive-tsp

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Travelling Salesman Problem - Naive Solver

This Repo provides a naive solver for the Travelling Salesman Problem.

The naive solution is based on the following three steps:

  1. Generate all possible permutations of nodes
  2. Iterate over each permutation and calculate path length
  3. Return shortest path

The Repo also contains a naive solver for the decision version of the Travelling Salesman Problem. Given a path length L, the solver follows these steps:

  1. generate all possible tours
  2. check if the length of the tours is less than L, if yes then return true

Usage

Option 1: online

Using runkit. Simply click here and copy/paste this code:

const { NaiveTsp } = require("naive-tsp");

const v = ['A', 'B', 'C', 'D'];

const e = {
  AB: 10,
  AC: 15,
  AD: 20,
  BA: 10,
  BC: 35,
  BD: 25,
  CA: 15,
  CB: 35,
  CD: 30,
  DA: 20,
  DB: 25,
  DC: 30
};

const len = 98;

console.log(new NaiveTsp(v, e, 'A').existsShorter(len));

Option 2: use npm

You will need node JS installed.

  1. Install the library:
npm install naive-tsp
  1. Run the below command:
node node_modules/naive-tsp/index.js
>.tsp A
{ path: [ 'A', 'B', 'D', 'C', 'A' ], length: 80 }

Option 3: clone this repo

You will need node JS installed.

You can clone this repo and start by using the sample graph included in the code, like this:

node index.js
>.tsp A
{ path: [ 'A', 'B', 'D', 'C', 'A' ], length: 80 }

The above calculates the shortest path.

If you want use the solver for the decision version of the problem, simply run:

node index.js
> .dectsp 98
{ exists: true, path: [ 'A', 'B', 'C', 'D', 'A' ], length: 95 }

Experiment

The included graph looks like this:

graph

If you would like to experiment, you can specify your own graph updating v and g constants in index.js:

const v = ['A', 'B', 'C', 'D'];

/*
 * The below is the representation of this graph:
 *
 *          10               15
 *    +-------------+ A +-------------+
 *    |               +               |
 *    |               |               |
 *    |               |20             |
 *    |               |               |
 *    |               |               |
 *    +     25        +      30       +
 *    B +-----------+ D +-----------+ C
 *    +                               +
 *    |                               |
 *    |                               |
 *    +-------------------------------+
 *                   35
 *
 */
const e = {
  AB: 10,
  AC: 15,
  AD: 20,
  BA: 10,
  BC: 35,
  BD: 25,
  CA: 15,
  CB: 35,
  CD: 30,
  DA: 20,
  DB: 25,
  DC: 30
};

About

Naive Solver for the Travelling Salesman Problem

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published