Premiär! Fyndchans i SweClockers Månadens Drop
Forum Mjukvara Programmering och digitalt skapande Tråd Inlägg

TSP_brute

1
Skriv svar
Permalänk
Medlem
●

TSP_brute

Här har vi ett exempel på Travelling Salesman Problem:
TSP_brute in C
Ett litet exempel bifogas 5x5.
Det är dock i minsta lagens för dagens datorer så jag har utökat till 12x12, 13x13 och 14x14.
Det som dock förbryllar är att 12x12 är den sista som kör enligt:
Antal vägar = n! (dvs n fakultet)
På 13x13 och 14x14 blir det något slags fusk....

Redigera
Citera flera Citera
Permalänk
Medlem
●

Så ser 14x14 ut:

0.0 3.1 4.2 2.3 7.4 9.5 8.6 5.7 8.8 6.9 4.0 4.0 3.4 2.9
3.1 0.0 4.0 6.0 3.0 9.0 5.0 6.0 3.0 2.0 4.0 5.0 3.0 2.5
4.2 4.0 0.0 5.0 8.0 7.0 3.0 4.0 9.0 3.0 1.0 1.0 8.0 3.5
2.3 6.0 5.0 0.0 6.0 5.0 6.0 9.0 7.0 1.0 5.0 5.0 6.0 1.0
7.4 3.0 8.0 6.0 0.0 3.0 7.0 8.0 5.0 4.0 8.0 8.0 1.0 4.0
9.5 9.0 7.0 5.0 3.0 0.0 4.0 5.0 4.0 9.0 7.0 7.0 3.0 9.0
8.6 5.0 3.0 6.0 7.0 4.0 0.0 6.0 3.0 2.0 3.0 3.0 7.0 2.0
5.7 6.0 4.0 9.0 8.0 5.0 6.0 0.0 1.0 7.0 4.0 4.0 8.0 7.0
8.8 3.0 9.0 7.0 5.0 4.0 3.0 1.0 0.0 5.0 9.0 9.0 5.0 5.0
6.9 2.0 3.0 1.0 4.0 9.0 2.0 7.0 5.0 0.0 3.0 3.0 4.0 8.8
4.0 4.0 1.0 5.0 8.0 7.0 3.0 4.0 9.0 3.0 0.0 6.0 8.0 3.0
4.0 5.0 1.0 5.0 8.0 7.0 3.0 4.0 9.0 3.0 6.0 0.0 9.3 3.7
3.4 3.0 8.0 6.0 1.0 3.0 7.0 8.0 5.0 4.0 8.0 9.3 0.0 4.0
2.9 2.5 3.5 1.0 4.0 9.0 2.0 7.0 5.0 8.8 3.0 3.7 4.0 0.0

Redigera
Citera flera Citera
Permalänk
Medlem
●

long och int är samma

Med min kompilator är long och int samma.
long long paths borde fungera men ger bara 1900 mega paths
13!= cirka 6000 mega
Så vad annat måste vara long long?

printf("%lld ", paths); bör fungera för jättetal

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av Greyguy1948:

Med min kompilator är long och int samma.
long long paths borde fungera men ger bara 1900 mega paths
13!= cirka 6000 mega
Så vad annat måste vara long long?

printf("%lld ", paths); bör fungera för jättetal

Gå till inlägget

Tips: Använd inte long och dylikt när du verkligen bryr dig om precisionen på typen, och använd bara int när det knappt spelar roll. Ha istället för vana att använda typerna från inttypes.h, så slipper du hålla i huvudet vilka bredder alla int-typer har, och råka på överraskningar när du kompilerar koden på främmande plattformar.

Exempel:

#include <stdio.h>
#include <inttypes.h>

uint64_t fac(uint64_t n) {
    return n == 0 ? 1 : n * fac(n - 1);
}

int main() {
    printf("%" PRIu64 "\n", fac(13));
    return 0;
}
Senast redigerat
Visa signatur

Arbets- / Spelstation: Arch Linux - Ryzen 5 3600 - RX 7900 XT - 32G DDR4
Server: Arch Linux - Core i5-10400F - 16G DDR4

Redigera
Citera flera Citera
Permalänk
Medlem
●

Tack för tipset!
Är detta standard i C99?

Jag vet ännu inte varför det sårar ut efter ca 1800 miljoner paths.
Men på Anandtech forum har jag fått en bättre algoritm som klarar 13x13 på 69 ms med en Raspberry Pi 3.

Redigera
Citera flera Citera
Permalänk
Medlem
●
Skrivet av Greyguy1948:

Tack för tipset!
Är detta standard i C99?

Gå till inlägget

Ja precis. Del av standardbiblioteket sedan C99.

Visa signatur

Arbets- / Spelstation: Arch Linux - Ryzen 5 3600 - RX 7900 XT - 32G DDR4
Server: Arch Linux - Core i5-10400F - 16G DDR4

Redigera
Citera flera Citera
1
Skriv svar
Senaste nyheterna
Hårdvara
Mjukvara
Övrigt
Nytt i forumet
Datorkomponenter
System
Ljud, bild och kommunikation
Spel och mjukvara