Testköra min A* algoritm - Vad tycker ni?

[AndLi]

Jag lyckas med mycket. Även det omöjliga.

Testa nu då? Första inlägg.

Bygger inte, innan du postar kan du ju prova din kod i någon vanilla C miljö som tex
https://www.onlinegdb.com/online_c_compiler

Får du den att bygga där kan du posta koden, annars får du göra om och göra rätt...

Just nu gnäller den på:

Kod: Markera allt

main.c: In function ‘show_path’:
main.c:221:4: warning: implicit declaration of function ‘print’ [-Wimplicit-function-declaration]
    print(map, height, width);
    ^~~~~
/tmp/ccQdXDeF.o: In function `show_path':
main.c:(.text+0xae1): undefined reference to `print'
collect2: error: ld returned 1 exit status

Så laga den och posta igen... Du kan ju också förklara hur den kan bygga på din maskin...

[DanielM]

Nu är den lagad. Hade missat print_int igen. Har testkört den och den fungerar.

Jag kan annars ladda upp med C Eclipse project. Jag kör alltid Eclipse.

[AndLi]

Visst vill du begränsa dig till de som bara kör eclipse så är du såklart välkommen...

varför printas det ut en massa x = -1 y= -1 i slutet?

[DanielM]

Det finns inga andra sätt att skriva C kod. Nej, jag tänker inte använda några beta program så som Vim, Emacs eller andra "Pro Hackers"-IDE. Dom fungerar bra om man kör endast terminaliskt och ska ändra någon parameter.
Seriöst folk som investerar i framtiden kör Eclipse och oseröst folk leker runt med attityder och lyxiga utvecklingsverktyg som kostar pengar. Dessutom genererar Eclipse faktiskt en make-fil. Så Eclipse generera projekt som kan komplimeras överallt.

Jag kör mycket Java och C och Java och Eclipse går riktigt bra ihop. Även C också för Eclipse har profiling inbyggt. Då kan jag söka efter minnesläckor.

-1 är mitt sätt att säga att det är slut. Så om du får en lista med massa koordinater så kommer dom alltid vara över -1. -1 indikerar slut.
Jag använder mig av statiskt minne och använder inte heap-minnet. Många A* algoritmer använder sig av malloc, calloc och recalloc. Men jag har lyckats skriva A* utan att använda heap.
Jag börjar att använda så mycket minne så det fyller upp värsta tillfället.

Jag har lyssnat på Sojan, sur Tomas och IceCap

[MJH]

I grunden är de samma algoritm. Som jag just skrev så kommer Dijkstra alltid att hitta närmaste vägen. Det garanterar inte A*, även om den oftast gör det. Därför är Dijkstra en utmärkt referensalgoritm när du trimmar in din A*. Dessutom är den aningen enklare att implementera, eftersom man slipper bekymret med att räkna avstånd till målet.

Dijkstra är dessutom stegare. Använder du t.ex 2-3 normer för att beräkna distans så kommer du hitta den kortaste vägen med A*.

Det viktigaste inom planering är inte att hitta kortaste vägen. Det viktigaste är att den är snabb.

Följer tråden med intresse men är inte den kortaste även snabbaste?
Så förklara ditt synsätt att snabbaste är viktigare än kortaste väg!

[AndLi]

-1 är mitt sätt att säga att det är slut.

Men varför sägs det att det är slut +20 ggr?

Det finns inga andra sätt att skriva C kod. Nej, jag tänker inte använda några beta program så som Vim, Emacs eller andra "Pro Hackers"-IDE. Dom fungerar bra om man kör endast terminaliskt och ska ändra någon parameter.
Seriöst folk som investerar i framtiden kör Eclipse och oseröst folk leker runt med attityder och lyxiga utvecklingsverktyg som kostar pengar. Dessutom genererar Eclipse faktiskt en make-fil. Så Eclipse generera projekt som kan komplimeras överallt.

Du gör ju dina val, En C fil kan byggas överallt där det finns en C byggmiljö... Eclipse projekt kräver ju förutom C byggmiljön, även just eclipse... Att kunna köra det i tex den onlinemiljön som jag visa gör ju tröskeln väldigt liten för att någon ska orka prova din kod...

[svanted]

Följer tråden med intresse men är inte den kortaste även snabbaste?
Så förklara ditt synsätt att snabbaste är viktigare än kortaste väg!

pratar vi om gpsnavigering i bil är det väl självklart

[DanielM]

I grunden är de samma algoritm. Som jag just skrev så kommer Dijkstra alltid att hitta närmaste vägen. Det garanterar inte A*, även om den oftast gör det. Därför är Dijkstra en utmärkt referensalgoritm när du trimmar in din A*. Dessutom är den aningen enklare att implementera, eftersom man slipper bekymret med att räkna avstånd till målet.

Dijkstra är dessutom stegare. Använder du t.ex 2-3 normer för att beräkna distans så kommer du hitta den kortaste vägen med A*.

Det viktigaste inom planering är inte att hitta kortaste vägen. Det viktigaste är att den är snabb.

Följer tråden med intresse men är inte den kortaste även snabbaste?
Så förklara ditt synsätt att snabbaste är viktigare än kortaste väg!

Jag menade beräkningstiden. Dijkstra beräknar väldigt mycket för att komma fram till samma resultat.

Dijkstra tar för lång tid för du kanske vill köra A* kontinuerligt för varje millisekund. Du kanske har en radarfunktion som uppdaterar kartan hela tiden och A* jobbar tillsammans med radarn.
Har själv besökt att företag som jobbar åt båtindustrin och framtidens båtar inom försvaret kommer vara självkörda. Då är det en radar som uppdaterar området och dess begränsningar. Det dom lade vikt på är att få en algoritm så snabb som möjligt som kan beräkna en korrekt väg, dock inte den absolut bästa vägen.

Optimalhet är något som man idag går ifrån. Nu handlar det om att hitta "Goda värden" istället för "Optimala värden". Inom reglerteknik så har fler och fler gått över till Model Predictive Control jämfört med Linear Quadratic Regulator när det finns möjlighet. MPC använder optimeringslära t.ex. kvadratisk programmering eller linjär programmering. LQR använder styrlag beräknat fram igenom Algebraic Riccati Ekvationer. Båda fungerar bra. LQR är bra om man har snålt om minne. Men som det ser ut idag så är processorer allt mer snabbare. Så därför passar sunt för nuft, goda värden osv bättre än absolut perfekta.

[MJH]

Följer tråden med intresse men är inte den kortaste även snabbaste?
Så förklara ditt synsätt att snabbaste är viktigare än kortaste väg!

pratar vi om gpsnavigering i bil är det väl självklart

GPS, framkomligt är helt annan frågeställning än tråden så förklara dig varför du framhäver GPS? navigering i denna tråd
Där tas helt andra hänsyn till snabbaste väg!

[DanielM]

-1 är mitt sätt att säga att det är slut.

Men varför sägs det att det är slut +20 ggr?

Det finns inga andra sätt att skriva C kod. Nej, jag tänker inte använda några beta program så som Vim, Emacs eller andra "Pro Hackers"-IDE. Dom fungerar bra om man kör endast terminaliskt och ska ändra någon parameter.
Seriöst folk som investerar i framtiden kör Eclipse och oseröst folk leker runt med attityder och lyxiga utvecklingsverktyg som kostar pengar. Dessutom genererar Eclipse faktiskt en make-fil. Så Eclipse generera projekt som kan komplimeras överallt.

Du gör ju dina val, En C fil kan byggas överallt där det finns en C byggmiljö... Eclipse projekt kräver ju förutom C byggmiljön, även just eclipse... Att kunna köra det i tex den onlinemiljön som jag visa gör ju tröskeln väldigt liten för att någon ska orka prova din kod...

För att jag börjar med att initialisera en array som är höjd*bredd till -1 för varje element.

Eclipse projekt finns inte Det heter C/C++ project eller Maven/Gradle/Ant osv. Eclipse använder ingen egen projektstruktur.
Den där onlinemiljö är inget annat än till för utbildning. Du bygger inte seriösa projekt med onlinemiljö.

[AndLi]

Och ändå funkar den utmärkt att provköra din kod i... betyder det att din kod inte är seriös?

[DanielM]

Provköra är en annan sak, t.ex. utbildning. Jag talar om att utveckla projekt.

Du kunde lika gärna använda terminalen och kompilera den med gcc. Har fungerat lika bra.

[AndLi]

Och jag tipsar dig om sätt på att få folk att ta av sin tid och provköra/ utvärdera din implementation... då gäller det att ribban ligger nedgrävd..

[DanielM]

Det är professionella C kodare på detta forum. Jag behöver bara ge dom koden, vilket den fungerar nu. Sedan kan dom köra den.

[sodjan]

OK, så vad är det som ska "testas"? Är det något problem med koden?

Kod: Markera allt

$ cc a_star.c
$ link a_star
$ run a_star
Initial map
-1      -1      -1      -1      -1      -1      -1      -1      -1      -1
-1      -1      -1      -1      -1      -1      -1      -1      -1      -1
-1      -1      0       0       0       0       0       0       0       -1
-1      -1      0       -1      -1      -1      -1      -1      0       -1
-1      -1      0       -1      0       0       0       -1      0       -1
-1      -1      0       -1      0       -1      0       -1      0       -1
-1      -1      0       -1      0       -1      0       -1      0       -1
-1      -1      0       -1      0       -1      0       -1      0       -1
-1      0       0       0       0       -1      0       -1      0       -1
-1      -1      -1      -1      -1      -1      0       -1      0       -1
-1      -1      0       0       0       0       0       -1      0       -1
-1      -1      0       0       -1      -1      -1      -1      0       -1
-1      -1      0       0       0       0       0       0       0       -1
-1      -1      -1      -1      -1      0       -1      -1      0       -1
-1      -1      -1      -1      -1      -1      -1      -1      -1      -1

Compute the coordinates
Shortest step is = 20

Total speed  was 0.000000,
Computed map
-1      -1      -1      -1      -1      -1      -1      -1      -1      -1
-1      -1      -1      -1      -1      -1      -1      -1      -1      -1
-1      -1      -107    -108    -109    -110    -111    -112    -113    -1
-1      -1      -106    -1      -1      -1      -1      -1      -114    -1
-1      -1      -105    -1      32      28      24      -1      -115    -1
-1      -1      -104    -1      28      -1      20      -1      -116    -1
-1      -1      -103    -1      24      -1      16      -1      -117    -1
-1      -1      -102    -1      20      -1      12      -1      -118    -1
-1      -100    -101    20      16      -1      8       -1      -119    -1
-1      -1      -1      -1      -1      -1      6       -1      1       -1
-1      -1      8       7       6       5       4       -1      2       -1
-1      -1      9       8       -1      -1      -1      -1      3       -1
-1      -1      10      9       8       7       6       5       4       -1
-1      -1      -1      -1      -1      8       -1      -1      5       -1
-1      -1      -1      -1      -1      -1      -1      -1      -1      -1

x = 1, y = 8
x = 2, y = 8
x = 2, y = 7
x = 2, y = 6
x = 2, y = 5
x = 2, y = 4
x = 2, y = 3
x = 2, y = 2
x = 3, y = 2
x = 4, y = 2
x = 5, y = 2
x = 6, y = 2
x = 7, y = 2
x = 8, y = 2
x = 8, y = 3
x = 8, y = 4
x = 8, y = 5
x = 8, y = 6
x = 8, y = 7
x = 8, y = 8
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
x = -1, y = -1
$