Skip to content

Latest commit

 

History

History
123 lines (79 loc) · 6.73 KB

READMEOLD.md

File metadata and controls

123 lines (79 loc) · 6.73 KB
Raw
traveler.py -> Python Results:

Path validation successful: Each city is visited once, and path returns to origin.

Initial Distance: 1257.0209779547552

Optimized Distance: 1051.0785415861549

Initial Solution Time (seconds): 0.0009884834289550781

Optimization Time (seconds): 0.005000591278076172

Initial Path: 
['City0', 'City1', 'City2', 'City4', 'City7', 'City9', 'City12', 'City14', 'City17', 'City19', 'City22', 'City24', 'City27', 'City29', 'City32', 'City34', 'City37', 'City39', 'City42', 'City44', 'City47', 'City49', 'City48', 'City46', 'City45', 'City43', 'City41', 'City40', 'City38', 'City36', 'City35', 'City33', 'City31', 'City30', 'City28', 'City26', 'City25', 'City23', 'City21', 'City20', 'City18', 'City16', 'City15', 'City13', 'City11', 'City10', 'City8', 'City6', 'City5', 'City3', 'City0']

Optimized Path: 
['City0', 'City1', 'City2', 'City4', 'City7', 'City9', 'City12', 'City14', 'City17', 'City19', 'City22', 'City24', 'City27', 'City29', 'City32', 'City34', 'City37', 'City39', 'City42', 'City44', 'City47', 'City49', 'City48', 'City46', 'City45', 'City43', 'City41', 'City40', 'City38', 'City36', 'City35', 'City33', 'City31', 'City30', 'City28', 'City26', 'City25', 'City23', 'City21', 'City20', 'City18', 'City16', 'City15', 'City13', 'City11', 'City10', 'City8', 'City6', 'City5', 'City3', 'City0']

Initial Distance: 1257.0209779547552

Optimized Distance: 1051.0785415861549

Initial Solution Time (seconds): 0.0009884834289550781

Optimization Time (seconds): 0.005000591278076172

Below is JavaScript where I built it to test the results in what I know best.

The visual mouse over object is added to display origions of x and y with hover options. -Try visual folder speedy html!

image Shows mouse over a object in the example below canvas

solvedtsp.js Module

Module Name: solvedtsp.js
Primary Purpose: Solves the Traveling Salesman Problem (TSP) using an optimized and asynchronous approach, incorporating distance memoization and heuristic methods.

Module Overview

The solvedtsp.js module provides an optimized solution for solving the Traveling Salesman Problem (TSP). It utilizes a combination of memoization for distance calculations, the Nearest-Neighbor heuristic for route generation, and a 2-opt swap technique for further optimization. Designed to handle a range of datasets efficiently, this module allows you to compute the shortest possible route for a set of cities based on their coordinates.

This module is particularly useful for smaller to medium datasets and provides an approximate solution to the TSP, with performance that scales well as the number of cities increases.

Module Components

  1. Memoized Distance Calculation

    • Purpose: Computes the Euclidean distance between two cities while caching the results for faster retrieval.
    • Operation: A key-value cache stores distances between cities, ensuring that repeated calculations are avoided, improving performance.

  2. Total Path Distance Calculation

    • Purpose: Calculates the total distance for a path that visits each city exactly once.
    • Operation: Uses the cached distances between cities to sum up the total distance of a given path, enhancing efficiency.

  3. Nearest-Neighbor Heuristic for TSP

    • Purpose: Provides a solution to the TSP by visiting the closest unvisited city at each step.
    • Operation: The nearest-neighbor approach selects the closest city to the current city, iteratively building a path that approximates the optimal route.

  4. 2-Opt Optimization

    • Purpose: Refines the solution to the TSP by optimizing the path using the 2-opt swap technique.
    • Operation: The algorithm checks pairs of cities in the current route and swaps segments if it results in a shorter path, continuing until no further improvements can be made.

How to Use

// Import the module
const { solveSatisfiabilityAndTSP } = require('./solvedtsp.js');

// Define cities data
const cities = [
    { name: "City1", x: 8.69, y: 46.44 },
    { name: "City2", x: 55.30, y: 90.43 },
    // Add other cities as needed
];

// Run the function and log the result
solveSatisfiabilityAndTSP(cities).then(result => {
    console.log("Optimal Path:", result.path);
    console.log("Total Distance:", result.distance);
});

Performance Highlights

  • Memoization Efficiency: By caching distances between cities, the module avoids redundant calculations, leading to faster execution times for larger datasets.
  • Approximate TSP Solution: The nearest-neighbor heuristic generates a path that approximates the optimal solution. The 2-opt technique further optimizes this path, reducing the overall distance.
  • Scalability: The module efficiently handles datasets ranging from a few cities to several hundred, providing fast results even with an increasing number of cities.

Feedback

  • Efficiency: The module performs well for medium-sized datasets, providing results in a reasonable time frame. For larger datasets, further optimizations or advanced algorithms like simulated annealing could improve performance.
  • Clarity: The module is easy to understand and maintain, with well-defined functions for each major step in the TSP solution.
  • Suggestions:
    • Adding error handling to ensure valid city data is passed to the function could improve robustness.
    • The nearest-neighbor heuristic could be enhanced by incorporating more advanced techniques for path optimization, like genetic algorithms.

Module History and Evolution

This module represents a refined version of the initial approach to solving the TSP. Early versions of this module focused on brute-force methods, which were inefficient for larger datasets. Over time, optimizations such as memoization, the nearest-neighbor heuristic, and the 2-opt swap technique were introduced, leading to a significant performance boost and more efficient solutions.

  • Initial Version: Focused on basic, unoptimized TSP solutions with brute force.
  • Subsequent Versions: Introduced memoization, heuristic algorithms, and optimization techniques to handle larger datasets and reduce computation time.

Notes

  • Cities Object: Ensure that the cities array is passed as an argument when using the solveSatisfiabilityAndTSP function. The module does not include predefined city data; it expects the caller to provide it.
  • Asynchronous Execution: The module utilizes asynchronous execution, allowing it to handle larger datasets efficiently. However, for very large datasets, the algorithm’s performance might still be limited, and further optimization might be necessary.