tspvis README

README проекта с github.com/jhackshaw/tspvis. Одним файлом markdown: README.md.

Netlify Status code style: prettier Live Demo Contributors GitHub

[!WARNING]
Seeking maintainers: If you're qualified and interested in taking over this project, I'd love to hear from you! The analytics suggest it is still helpful to a number of users, but I don't currently have the time to give it the attention it deserves. There's a lot of potential here and I'm looking to transition this to someone interested in making it better. Please shoot me a message if you're interested.

Traveling Salesman Problem

The traveling salesman problem (TSP) asks the question, "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?".

This project

Heuristic algorithms

Heuristic algorithms attempt to find a good approximation of the optimal path within a more reasonable amount of time.

Construction - Build a path

Improvement - Attempt to take an existing constructed path and improve on it

Exhaustive algorithms

Exhaustive algorithms will always find the best possible solution by evaluating every possible path. These algorithms are typically significantly more expensive then the heuristic algorithms discussed above. The exhaustive algorithms implemented so far include:

Dependencies

These are the main tools used to build this site:

Contributing

Pull requests are always welcome! Also, feel free to raise any ideas, suggestions, or bugs as an issue.

Instructions on How to Install

To set up the project locally, follow these steps:

  1. Clone the repository:

    git clone https://github.com/jhackshaw/tspvis.git
    cd tspvis
    
  2. Install libvips: On macOS, you can install libvips using Homebrew:

    brew install vips
    
  3. Install dependencies: Ensure you have Node.js installed. Then, run:

    npm install
    
  4. Start the development server: To run the project locally, use:

    npm run develop
    

    This will start a local development server, typically accessible at http://localhost:8000.

  5. Build for production: If you want to create a production build, run:

    npm run build
    

    The output will be in the public/ directory.

  6. Serve the production build: To test the production build locally, use:

    npm run serve
    
  7. Clean the cache: If you encounter issues, you can clean the Gatsby cache and public directories:

    npm run clean
    

tspvis (jhackshaw/tspvis)

Ищем в базе…

466 ·GitHub
Что это такое?Веб-приложение, которое визуализирует и управляет алгоритмами для задачи коммивояжёра (TSP), в первую очередь как обучающий инструмент. Распространяется с открытым исходным кодом под лицензией MIT.
Это библиотека, которую можно импортировать, или самостоятельное приложение?Самостоятельное веб-приложение, а не библиотека. Оно создано на Gatsby и React и работает в браузере, либо локально, либо на размещённом сайте.
Как запустить его локально?Клонируйте репозиторий, установите libvips (на macOS через Homebrew), установите зависимости Node.js, затем запустите локальный сервер разработки, который обычно работает на localhost. В README также описаны сборка для продакшена и раздача готовой сборки.
Нужно ли что-то установить заранее?Node.js и libvips. В README сказано, что libvips нужно установить до зависимостей проекта. На macOS libvips можно получить через Homebrew.
Проект всё ещё поддерживается?Автор ищет нового сопровождающего и говорит, что сейчас у него нет времени должным образом заниматься проектом, поэтому обновления могут выходить медленно. Pull request'ы и issues приветствуются.
Что такое задача коммивояжёра?Дан список городов и расстояния между каждой парой из них. Требуется найти кратчайший возможный маршрут, который проходит через все города и возвращается в исходную точку. Это классическая задача в исследовании алгоритмов и оптимизации.
Можно ли попробовать без установки?Да, автор разместил приложение онлайн по адресу tspvis.com, так что им можно сразу пользоваться в браузере.
Практичны ли полные перебора алгоритмы для больших входных данных?Они всегда находят наилучший возможный путь, но работают гораздо медленнее эвристических алгоритмов, поэтому быстро замедляются с ростом количества городов.
Какие есть похожие проекты?algorithm-visualizer, city-roads, kepler.gl, prettymaps, vistep, deck.gl, mapcn, gralobe
Автор
jhackshaw
Размер
3.3 MB
Звёзды
466
Обновлён
КоммитJun 06
Возраст
7 г
Коммиты · 90 дней