Tech Recipe Book
My Services
  • Book
    • About the author
    • Architect
      • Algorithms
        • DB index algorithms
          • How does database indexing work
        • Neural network optimization
          • Neural Network Optimization
        • Route search
          • Road network in a database to build a route
          • Traveling Salesman Problem (TSP)
      • Architecture Frameworks
        • DODAF
        • TOGAF
        • Enterprise Architecture (EA) Tools Reviews 2023 | Gartner
      • Zero Trust
      • Billing
        • SHM billing system
      • Bots
        • Discord
        • Telegram
          • Chat GPT Telegram bot
          • Получаем статистику Telegram-канала при помощи api и python или свой tgstat с регистрацией и смс
          • Как хостить телеграм-бота (и другие скрипты на Python) на Repl.it бесплатно 24/7
          • Создание Telegram бота на PHP #1: основные понятия для работы с API
          • Создание Telegram бота на PHP #2: создание первого бота для Telegram
          • Создание Telegram бота на PHP #3: примеры отправки сообщений с кнопками в Telegram
          • Создание Telegram бота на PHP #4: отправка файлов и изображений в Telegram
          • Создание Telegram бота на PHP #5: работа с хуками
      • Business intelligence
      • Cloud Storage
        • Ceph
        • Virtual Distributed File System
      • Cryptography
        • Open Source PKI Software
        • OpenPGP
          • Email Encryption
          • Kleopatra
          • Miscellaneous Tools
          • Server side applications
      • Message broker
        • Kafka
          • Kafka UI-tools
          • Kafka streams ksqlDb
        • RabbitMQ
      • DB
        • MySQL
          • Auto sharding
          • MariaDB Zabbix monitoring
          • MySQL and MariaDB replication with Zabbix monitoring
        • Postgres
          • HA PostgreSQL with Patroni, Haproxy, Keepalived
          • Mass parallel requests - Greenplum
          • PostgreSQL cluster for development and testing
        • Vitess - Scalable. Reliable. MySQL-compatible. Cloud-native. Database.
      • Identity and Access Management (IDM)
        • FreeIPA - Identity, Policy, Audit
        • FreeIPA as an Enterprise solution
        • Keycloak
          • Keycloak HA cluster
        • Open Identity Platform
        • SSO
          • Keycloak for Java app
          • OpenAM
          • OpenIG
      • Firewall
        • nftables
      • Infrastructure As a Code
        • Ansible
        • IaC Packer Ansible Teraform
        • Installing Jenkins using terraform in Kubernetes in Yandex Cloud with letsencypt
        • Teraform Crosplan Pulumi
        • Yandex IaC solutions
      • Kubernetes
        • Installation
          • Install Kubernetes cluster
          • Deploying a Kubespray cluster to OpenStack using Terraform
          • Kube deploy in Yandex cloud
        • Frameworks
          • Deckhouse
            • LDAP authentification
            • On premise Install
            • Yandex Cloud Install
          • K3S
          • OpenShift OKD
          • RKE2
          • Rancher
            • Rancher Install
        • Auth
          • Keycloak in k8s
          • LDAP
        • GUI management Lens
        • Monitoring
          • Monitoring with Falco
          • Network monitoring
          • Nginx ingress
          • Prometheus Graphana for sample Nodejs app
          • Rsource monitoring Avito
        • Exposing services
          • Exposing Kubernetes Services
          • Cilium BGP
        • CNCF
        • Helm
          • Repositories
            • Artifact Hub | official
            • Bitnami | vmware
          • Awesome helm charts and resources
          • Essential Services for Modern Organizations
          • Security and Compliance
          • Additional charts
        • Isolation
          • vcluster - Virtual Kubernetes Clusters
          • Kiosk
          • KubeArmor
          • Control Plane Hardening
          • Hierarchical namespaces
        • Security Center
          • Minesweeper
          • NeuVector by SUSE
          • SOAR in Kubernetes
          • Security Сenter for Kubernetes
        • Terraform CI security
          • Terraform plan analysis with Checkov and Bridgecrew
          • Yandex Terraform scan
        • Vulnerability management
          • Aqua
          • Sysdig
          • Kyverno
          • GitLab
          • NeuVector by SUSE
        • Image scanning
          • Snyk
          • Sysdig
          • Harbor
          • Trivy
        • Signature verification
          • Sigstore
        • Control plane security
          • Gatekeeper
            • Applying OPA Gatekeeper
          • Kyverno
            • Policy as a code. Kyverno
        • Runtime Security
          • Osquery
          • Falco
          • ClamAV
        • Network security
          • Cilium
          • Control Plane Hardening (API restriction)
          • Network policy recipes
          • Service mesh
            • Istio HA, LoadBalance, Rate limit
          • mTLS Autocert
        • Honeypot
          • Building honeypot using vcluster and Falco
        • Backup
          • Kasten K10
        • Secrets
          • Vault CSI Driver
      • Load Balance
        • Nginx
        • HAProxy
          • Proxy methods
          • HAProxy for RDP
          • Payment gateway A/B test with HAProxy
          • HAPRoxy for Percona or Galera
      • Monitoring
        • Zabbix
          • Apache Zabbix
          • Disc Quota
          • Nginx Zabbix
          • SSL certificates Zabix
          • Zabbix notifications
        • Nagios
          • Datacenter monitoring
        • Prometheus and Grafana
      • Windows
        • Sysmon enhanced Windows audit
        • Sysmon to Block Unwanted File
      • Linux
        • Rsync
        • Debian based
          • Apt-Cacher NG
          • Unattended Upgrades in Debian / Ubuntu
        • RedHat basede
          • RPM Server
        • Logs analysis
        • Build armhf qemu
      • NGFW
      • CI/CD
        • DevSecOps
          • DAST
            • Burp
              • Dastardly
            • StackHawk
            • ZAP and GitHub Actions
          • SAST
            • Checkmarx
            • OSV by Google
            • Snyk
            • SonarQube
        • GitLab Runner in Yandex Cloud
        • Dynamic Gitlab Runners in Yandex Cloud
        • GitLab runner in Kubernetes with Werf
        • Kubernetes deploy strategies
        • Kubernetes highload deploy. part 1
        • Kubernetes highload deploy. part 2
        • Kubernetes Argo Rollouts
        • Jenkins in Kubernetes
        • Ansible Semaphore
        • Image storage, scaning and signing
        • Install WireGuard with Gitlab and Terraform
        • CI/CD example fror small web app
        • Threat matrix for CI CD Pipeline
      • SIEM / SOC
        • Datadog
        • Splunk
          • Splunk — general description
        • MaxPatrol
          • MaxPatrol 8 and RedCheck Enterprise
        • QRadar IBM
        • Cloud Native Security Platform (CNAPP) - Aqua
        • OSSIM | AT&T
          • AlienVault (OSSIM) install
        • Wazuh
        • EDR
          • Cortex XDR | Palo Alto Networks
          • Cynet
          • FortiEDR | Fortinet
          • Elastic
        • Elastic
          • Install Elasticsearch, Logstash, and Kibana (Elastic Stack) on Ubuntu 22.04
          • Setting Up Elastic 8 with Kibana, Fleet, Endpoint Security, and Windows Log Collection
        • Threat Intelligence
          • MISP
          • msticpy Microsoft
          • X-Force | IBM
          • Elastic
      • VPN
        • Full-Mesh VPN fastd, tinc, VpnCloud
        • Wireguard
          • WireGuard for Internet access
          • WireGuard on MikroTik and Keenetic
          • WireGuard site to site
        • SoftEther VPN Project
        • Cisco AnyConnect client
        • OpenConnect
        • SSTP python server
      • OS hardening
        • CIS Benchmarks
      • Cloud Providers
      • OpenNebula
        • OpenNebula Edge Cloud - Open Source Cloud & Edge Computing
        • Discover OpenNebula – Open Source Cloud & Edge Computing Platform
        • OpenNebula Multi-Cloud
        • Kubernetes on OpenNebula
        • The Open Source Alternative to Nutanix
        • The Simple Alternative to OpenStack
        • OpenNebula Partner Ecosystem
      • OpenStack
        • Install manual
        • Install with DevStack
      • VM
        • Create a VHD file from a Linux disk
        • Backup / Migration
          • Coriolis
          • Proxmox Backup Server
        • oVirt
        • VMware vCenter
        • Proxmox
      • Docker
        • Container optimization
        • Ubuntu RDP container
      • LXC
        • LXD on Ubuntu 18.04
        • Install, Create and Manage LXC in Ubuntu/Debian
    • Big Data
      • OLAP data qubes
      • Storage and autoscale in Lerua
    • Machine Learning
      • Yandex YaLM 100B. GPT model
      • Kaggle Community Datasts Models
      • AI in video production
      • Image search
      • Chat bots
        • You.com
        • Chat GPT
          • Implementing GPT in NumPy
        • Jailbreak Chat
      • Coding plugins CodeWhisperer
    • Malware
      • Isiaon/Pitraix: Modern Cross-Platform Peer-to-Peer Botnet over TOR
      • theZoo A repository of LIVE malwares
    • Pentest
      • Red Team
        • MITRE ATT&CK matrix
        • C2 Frameworks
          • Brute Ratel C4
          • Cobalt Strike
          • Covenant
          • Havoc Framework
          • Merlin
          • Metasploit
          • Sillenttrinity
          • Sliver
        • Manage and report
          • Dradis Framework
          • Hexway
        • Underground
      • Social engineering
        • Social Engineer Toolkit setoolkit
      • OSINT
        • OSINT for comapny
        • Instagram fishing
      • Forensics
        • Forensics tools
      • Pentesting Methodology
      • Web
      • CI/CD Methodology
      • Cloud Methodology
        • Hacking The Cloud
      • Kubernetes Pentesting
      • Android
        • SSL Unpinning for Android applications
      • iOS
        • SSL unpinning iOS and macOS applications
      • HackBar tool
      • CyberChef Tools
      • Python virtualenv
      • IppSec - YouTube
      • Hacktricks.xyz
    • Compliance
      • 152 ФЗ. Personal data
      • PCI DSS and ГОСТ Р 57580.1-2017
      • Cloud compliance
      • ГОСТ Р 57580.1-2017 для Kubernetes
      • Kubernets as DevSecOps and NIST compliance
      • NIST SP 800-61 cyberincidece control
      • CIS Kubernetes Benchmark v1.6 - RKE2 v1.20
      • CIS Kubernetes Benchmark v1.23 - RKE2
      • Requirements for Russian Banks
      • Tools
        • Chef InSpec
        • Elastic SIEM
    • Asset management
      • CMDBuild
    • Project management
    • Incident management SRE
    • Risk management
      • IT risk management
      • BSI-Standard 200-3
    • Web Dev
      • Cookie security
      • OWASP Top 10 2021
      • Docker nginx php mysql
      • Docker tor hiddenservice nginx
      • Docker Compose wp nginx php mariadb
      • Dependency Checking
        • Nexus Analyzer
        • OWASP dependency-check
      • Yii skeeks cms
      • YiiStudio
    • Art
      • GTK Themes
      • Themes for Xfce Desktop
      • XFCE / Xubuntu Windows 95
      • Moscow events
      • Photo goods
      • Russian style gifts
    • Cryptocurrency
      • News
      • Arbitrage
      • Stocks
      • Exchange aggregators
      • Where to use
      • Prepaid cards
        • BitFree
        • Pyypl Your Money at Your Fingertips
    • IT magazines
      • WIKI and Writeups tools
        • BookStack
        • GitBook
        • MkDocs
        • Wiki.js
        • DokuWiki
    • Languages
    • Learning
      • (ISC)2
        • CISSP
      • Offensive Security
        • OSCP
        • OSEP
        • OSED
      • DevSecOps
        • Certified DevSecOps Professional (CDP)
        • Certified DevSecOps Expert (CDE)
      • Web Security Academy: PortSwigger
    • Relocation
      • London experience
      • IT visas in 2022
      • Remote work
      • Running business in UAE
    • Freenet
      • Independent online services: the philosophy of a free Internet
      • Tor Project Anonymity Online
      • I2P Anonymous Network
    • Services
      • SMS Registration
        • Registering ChatGPT in Russia
      • Local and regional eSIMs for travellers - Airalo
      • Digital busines cards
      • No KYC services and exchanges
Powered by GitBook
On this page

Was this helpful?

  1. Book
  2. Architect
  3. Algorithms
  4. Route search

Traveling Salesman Problem (TSP)

Last updated 1 year ago

Was this helpful?

Задача коммивояжера (TSP) точное решение — метод ветвей и границ

/592454ca03b8381d59084d2e72685653.png)

Путешествие в тысячу ли начинается с одного шага. (Лао-Цзы)

Что делает код хорошим? Большинство программистов ответят: хороший код должен быть структурирован, легко читаем и понятен. Но так ли важно качество кода, если он медленный? В большинстве задач производительность кода не критична, хотя и желательна. Но есть задачи, время выполнения которых столь огромно, что выигрыш в производительности доминирует над всем остальным.

Я говорю про NP-трудные задачи (NP-трудность - недетерминированная полиномиальная трудность по времени) и на одной из данного класса хочу акцентировать ваше внимание. Задаче коммивояжера.

Мы не будем рассматривать эвристические алгоритмы, нам нужно точное решение.

На данный момент не существует известного алгоритма способного найти точное решение задачи коммивояжёра в общем виде за число шагов выраженного, как полином фиксированной степени от размера входных данных.

В мы ознакомились с решением задачи коммивояжера на минимум методом динамического программирования. Метод конечно замечательный, но он ограничен объёмом памяти системы. Уже при n = 28 вершин, 16 Гб оперативной памяти недостаточно, а использовать память жёсткого диска очень неэффективно. Возможно, используя хитроумные подходы структурирования и сжатия памяти можно несколько улучшить алгоритм, но ненамного. Нужен иной подход, если мы хотим рассчитывать матрицы большего размера.

Метод ветвей и границ, пожалуй, самый известный и эффективный метод нахождения точного решения задачи коммивояжёра. Не будем тут останавливаться на его описании, в интернете существует множество подробных мануалов с примерами. Для новичков рекомендую где, на мой взгляд, всё описано понятным языком.

Так же в своё время разобраться с тонкостями алгоритма мне помогла . Как и её автор, я прошёл тот же путь, и совершил ровно те же ошибки, главная из которых заключалась в том, что при невозможности получить приемлемые результаты, начал использовать эвристики. Ещё один любопытный .

Хочу обозначить одну тонкость метода ветвей и границ, которую мало кто освещает:

На этапе выбора элемента ветвления и разделения решения на два подмножества M1 (содержащие ребро с максимальным штрафом) и M2 (не содержит ребро с максимальным штрафом), при рассмотрении множества M1 вычеркиваем относящиеся к выбранной клетке строку и столбец, а также заменяем значение ячейки соответствующей обратному пути на бесконечность.

Но вот что скрывается под понятием обратного элемента? Во многих реализациях, что я видел, смысл определения выражен не верно, проиллюстрируем.

/7fa7aeed65e29fd94eff360455c91d34.png)

Есть некий граф, для которого на предыдущих этапах мы уже нашли рёбра [0, 3], [3, 5], [6, 7], [7, 1] и на текущем шаге рассматриваем ребро [5, 6] множества M1.

Так вот обратным элементом для ребра [5, 6], будет не ребро [6, 5] (как можно было подумать), а ребро [1, 0]. И вычёркиваем данное ребро затем, чтобы избежать в графе подцикл. Естественно, мы так же вычёркиваем все дуги, исходящие из [5] (вычеркивание строки) и входящие в [6] (вычеркивание столбца).

Так вот, для получения обратного элемента нужно найти голову и хвост пути, вместе с которым добавленное ребро образует единую ветвь и уже для такого пути взять обратный элемент.

Игнорирование сего факта очень часто заводит полный перебор в тупик, про точное решение промолчу.

Далее по ходу текста я буду выдвигать утверждения, которые кому-то могут показаться спорными, просто примите за факт.

Метод ветвления и границ при полном переборе очень эффективный метод, но у него есть одна отвратительная черта: рекурсия. Мы постоянно делим дерево решений на два подмножества, каждое из которых занимает место в памяти, плюс добавим сюда расходы на рекурсию и служебные переменные, при больших размерах дерева ветвлений это огромная проблема. Мало того, что оперативной памяти может просто не хватать, так ещё и обращение к разным участкам памяти не самое дешёвое удовольствие.

Авторский подход заключается в том, чтобы рассматривать задачу коммивояжёра не как академическую, а как инженерную.

Вся суть сводится к тому, что мы несколько отклоняемся от алгоритма, предложенного Литлом, в сторону увеличения количества шагов при обходе дерева ветвлений, но зато значительно выигрывая из-за организации таких шагов.

Алгоритм состоит в применении трёх мета шагов:

  1. Производим приведение матрицы (редукция строк, столбцов), выбираем нулевой элемент с максимальной оценкой для разбиения.

  2. На каждом ветвлении между выбором множества M1 или M2, всегда двигаться в M1, пока мы не достигнем дна. В матрице останется только один элемент, не предусматривающий ветвления, так мы получаем опорное решение. Сравниваем лучшее с текущим решением и запоминаем его, если оно короче.

  3. Далее мы возвращаемся на уровень выше, проверяем для него множество M2 и вычёркиваем клетку. Переходим к шагу 1.

    Отдельно остановлюсь на условиях, при которых мы можем досрочно прекратить дальнейшее обследование ветви дерева ветвлений, тем самым сократив объём вычислений.

    • На первом шаге, если мы понимаем, что в какую-либо вершину или из неё больше невозможно проложить ни одного маршрута;

    • На втором шаге, если видим, что лучший из найденных пока маршрутов меньше нижней текущей границы;

    • На третьем шаге, если лучший из найденных пока маршрутов меньше суммы нижней текущей границы и максимальной оценки на шаге;

Пример расчёта множества M1

Для себя назвал подход алгоритмом ныряльщика. Уж больно напоминает мне, как охотник за жемчугом ныряет на дно, хватает раковину, отплывает в сторону, снова ныряет. Дно водоёма не ровное, это и есть дерево ветвления. У пловца есть верёвка, которую выбирают до натяжения, каждый раз как ныряльщик достигает дна. И так до тех пор, пока он не сможет больше достигать дна, кроме одного места, что и окажется минимальным возможным решением.

Вы можете спросить, к чему эти сложности? Именно так мы избавляемся от хвостовой рекурсии при расчёте множества М2 и гарантируем, что глубина рекурсии для множества M1 никогда не превысит n.

А если применить ещё небольшой фокус с выделением памяти только на стеке, не используя динамическое выделение памяти в куче (просить память у ОС относительно дорого), то алгоритм не будет покидать сверхбыструю память L1 процессора. То есть при таком подходе мы не будем использовать ужасную медленную оперативную память, ну разве что только при переключении потоков в ОС.

Например, при n = 33 программе требуется не более 63КБ стека, при любых входных данных.

Из прочих неочевидных оптимизаций:

  • Предлагаю хранить индексы матрицы одним куском с данными, это здорово сокращает количество операций при копировании в матрицу меньшего размера, а также повышает локальность данных;

  • Использовать только 32 битные переменные для всего, нужно для выравнивания обращений в памяти (выровненные обращения происходят быстрее);

  • Использовать максимальное число для расчётов inf = 2147483647 (0x7fffffff), для того чтобы при сложении двух бесконечностей не получать переполнение регистра (не нужно проверять);

  • Умышленный отказ от операций деления (очень дорогая инструкция);

  • Переменные по возможности высвобождаются сразу, как перестают быть нужными;

  • Объединить этап редукции с выбором нулевого элемента для разбиения, для уменьшения количества обращений к матрице;

    Последняя оптимизация интересна в том, что за один проход можно получить сразу два параметра: минимальное значение для редукции по строке и минимум по той же строке для анализа нулей. Для этого для каждого элемента матрицы применяем функцию two_lows, которая находит два минимума за один проход, что сокращает почти вдвое число обращений к матрице на данном этапе. Аналогично и для столбцов.

Алгоритм изначально разрабатывался на Pascal, затем я конвертировал его на Си и внёс множество изменений не доступных Паскалю, добившись ещё более чем двукратного увеличения производительности на шаг. Для удобства работы в Python обернул в динамическую библиотеку и тестировал производительность уже на ней.

В отличие от детерминированного алгоритма динамического программирования, метод ветвей и границ является стохастическим, и время работы очень сильно варьируется от набора входных данных.

Была проведена серия испытаний на случайном наборе точек на плоскости для оценки производительности алгоритма от количества вершин графа. Каждая серия состояла из тысячи случайно сгенерированных наборов.

Зависимость времени выполнения (сек) от размера матрицы - логарифмическая шкала

Графики были построены по 99, 98, 95 и 90 перцентилям от размера графа и времени в секундах. 99 перцентиль говорит о том, что мы найдём решение задачи в среднем в 99 случаях из ста, за указанное время для похожего набора входных данных.

Как вы можете заметить подход не панацея, но при определённых условиях даёт весьма неплохие результаты.

Как бонус алгоритм неплохо себя чувствует на не полно связанных матрицах (отсутствующие связи задаются как отрицательные числа или inf), а также на не симметричных матрицах. Последнее особо важно для задач транспортной логистики, где расстояние в точку доставки не равно обратному пути, из-за того, что дороги могут быть односторонними.

Задача коммивояжёра на минимум и максимум

Теперь о минусах, хоть алгоритм переваривает абсолютно любые матрицы для поиска минимального решения, но на некоторых экземплярах делает это крайне неэффективно. Одним из таких примеров это задача коммивояжёра на максимум.

Задача коммивояжёра на максимум

Хоть я и обожаю Python, но для ресурсоёмких задач он не подходит совершенно, даже с numpy. Привожу пример ранней наивной реализации с использование pandas чисто в целях ознакомления для новичков, но возможно кого-то подвигнет на изучение.

Я работал над данным алгоритмом более трёх лет наездами. Проект, для которого предназначался этот алгоритм, остался в далёком прошлом, но мне думается, что общественности будут любопытны мои наработки на данном поприще.

Буду рад откликам, замечаниям, предложениям, возражениям.

Код, приведённый к статье, разработан вашим покорным слугой и может быть использован вами под лицензией GNU GPL.

P.S. C Наступающим Новым годом!

/0ae6231387f7330b104eb5e4a4dd208a.png)

/b6dcb70c2319753e6708e38e25bd7ce4.png)

/6a2bb4f37ac9653e7afcfb6d3cbb1b0f.png)

/9a9eb6e6ef50791e30e8b335268405ac.png)

https://habr.com/ru/articles/708072/
прошлой работе
статью
работа
подход