create  a  tsp / traveling saleman  tool with  3000 nodes,

Notebook Fujitsu  

Betriebsystemname	Microsoft Windows 11 Enterprise
Version	10.0.26100 Build 26100
Weitere Betriebsystembeschreibung 	Nicht verfügbar
Betriebsystemhersteller	Microsoft Corporation
Systemname	FOURTH-ELEMENT
Systemhersteller	FUJITSU CLIENT COMPUTING LIMITED
Systemmodell	LIFEBOOK E5511
Systemtyp	x64-basierter PC
System-SKU	SK02
Prozessor	11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz, 2803 MHz, 4 Kern(e), 8 logische(r) Prozessor(en)
BIOS-Version/-Datum	FUJITSU CLIENT COMPUTING LIMITED Version 2.40, 03.09.2024
SMBIOS-Version	3.3
Version des eingebetteten Controllers	255.255
BIOS-Modus	UEFI
BaseBoard-Hersteller	FUJITSU CLIENT COMPUTING LIMITED
BaseBoard-Produkt	FJNB2E8
BaseBoard-Version	C3
Plattformrolle	Mobil
Sicherer Startzustand	Ein
PCR7-Konfiguration	Erweiterung zum Anzeigen erforderlich
Windows-Verzeichnis	C:\WINDOWS
Systemverzeichnis	C:\WINDOWS\system32
Startgerät	\Device\HarddiskVolume2
Gebietsschema	Deutschland
Hardwareabstraktionsebene	Version = "10.0.26100.1"
Benutzername	FOURTH-ELEMENT\karlheinz
Zeitzone	Mitteleuropäische Sommerzeit
Installierter physischer Speicher (RAM)	64,0 GB
Gesamter physischer Speicher	63,6 GB
Verfügbarer physischer Speicher	42,9 GB
Gesamter virtueller Speicher	67,6 GB
Verfügbarer virtueller Speicher	47,6 GB
Größe der Auslagerungsdatei	4,00 GB

create  a  tsp / traveling saleman  tool with  3000 nodes,

<|channel|>analysis<|message|>Provide C++ program using simulated annealing or branch & bound? Just give code skeleton. Provide minimal but functional for 3000 nodes random coordinates and heuristic like 2-opt.<|end|><|start|>assistant<|channel|>final<|message|>```cpp

8,58  Sekunden..  Denken...  Ergebnis


/* Traveling Salesman Tool – 3000 nodes, 2‑Opt improvement */
#include <bits/stdc++.h>
using namespace std;

const int N = 3000;
struct Pt { double x,y; };
Pt pts[N];
int tour[N+1];           // last = start to close the loop

// ------------------------------------------------------------------
// Utility
double dist(int a,int b)
{
    double dx=pts[a].x-pts[b].x, dy=pts[a].y-pts[b].y;
    return sqrt(dx*dx+dy*dy);
}
inline double tourLen()
{
    double s=0; for(int i=0;i<N;i++) s+=dist(tour[i],tour[i+1]); return s;
}
// ------------------------------------------------------------------
// 2‑Opt core
bool improve()
{
    bool changed=false;
    for(int i=1;i<N-1;i++)
        for(int k=i+1;k<N;k++){
            double d0 = dist(tour[i-1],tour[i]) + dist(tour[k],tour[(k+1)%N]);
            double d1 = dist(tour[i-1],tour[k]) + dist(tour[i],tour[(k+1)%N]);
            if(d1<d0-1e-9){
                reverse(&tour[i],&tour[k+1]); changed=true;
            }
        }
    return changed;
}
// ------------------------------------------------------------------
// Main
int main()
{
    srand((unsigned)time(nullptr));
    for(int i=0;i<N;i++){ pts[i].x = rand()%10000; pts[i].y = rand()%10000;}
    // initial tour: 0..N-1
    for(int i=0;i<N;i++) tour[i]=i;
    tour[N]=tour[0];

    cout<<"Initial length: "<<fixed<<setprecision(2)<<tourLen()<<"\n";

    int iters=0;
    while(improve()){
        if(++iters%10==0) cout<<"Iter "<<iters<<"  len="<<tourLen()<<"\n";
    }
    cout<<"Final length: "<<tourLen()<<"\n";
    return 0;
}