Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

backtracking

Werbeanzeige

Sk!p

Alter Hase

  • »Sk!p« ist der Autor dieses Themas

Beiträge: 568

  • Private Nachricht senden

1

05.05.2007, 21:45

backtracking

hi,

ich brauche mal etwas Unterstützung von euch ;)

Und zwar will ich in einem 2-dimensionalen Array, dass mit int Werten gefüllt ist, den einfachsten Weg (den mit der kleinsten Summe) von einer eingegebenen Start- zur Endkoordinate finden. Man kann von einem Feld alle 8 umliegenden Felder erreichen.

Zurückgegen werden soll dann wieder ein 2-dimensionales Array, dass die Koordinaten enthält (zb. {{0,1}{0,2}{1,3}})

Ich bin jetzt schon studenlang am rumprobieren, aber ich krieg es einfach nicht hin. Ich muss noch dazu sagen, dass ich keinen bekannten Backtracking-Algorithmus benutzen will, sondern nur durch frühzeitiges Abbrechen eines ungünstigeren Weges und normales Backtracking zum Ergebnis kommen will.

In Pseudocode hab ich mir folgendes überlegt:

- Aufruf der rekursiven Funktion ShortestPathOrigin(orig_x, orig_y, dest_x, dest_y)
- aktuelle Koordinaten zum minimum dazuzählen
- return falls minimum größer als beste bisher gefundene Lösung
- falls der Zielknoten nur noch 1 Feld weit entfernt ist, Wert der Zielkoords zum minimum dazuzählen, überprüfen ob dieses nun kleiner ist als beste Lösung und gegebenfalls einsetzen, Wert wieder vom minimum abziehen und return
- für alle 8 Felder um das aktuelle herum überprüfen, ob sie noch in den Grenzen liegen, falls ja rekursive Funktion mit dem aktuellen Feld aufrufen

ich hab jetzt nur gerade überhaupt keine Ahnung, wie ich den besten Weg dann in das Array krieg, ohne dass ich einen komplett anderen Ansatz verfolgen soll. Ich hoffe inständig, irgendjemand findet sich mit einer Idee :)

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

2

05.05.2007, 23:40

ist über die zahlen was bekannt (z.B. alle positiv, nur in bestimmten wertbereich, bestimmte verteilung...) oder sind es irgendwelche zahlen?
kannst du die wegkosten von einem punkt zum zielpunkt irgendwie abschätzen (wenn ja, bietet sich evtl. A* an, sonst nicht).
was genau bezweckst du damit?
m4studios

grek40

Alter Hase

Beiträge: 1 491

Wohnort: Dresden

  • Private Nachricht senden

3

05.05.2007, 23:41

Unabhängig von deinem genauen Vorgehen empfehle ich an dieser Stelle std::list für die Koordinaten, da du so flexibler als mit einem Array an Datenbestand und Reihenfolge arbeiten kannst.

Sk!p

Alter Hase

  • »Sk!p« ist der Autor dieses Themas

Beiträge: 568

  • Private Nachricht senden

4

06.05.2007, 00:21

Zitat von »"dot"«

ist über die zahlen was bekannt (z.B. alle positiv, nur in bestimmten wertbereich, bestimmte verteilung...) oder sind es irgendwelche zahlen?


sind alle zwischen 0 und 100 :)

Zitat von »"dot"«


kannst du die wegkosten von einem punkt zum zielpunkt irgendwie abschätzen (wenn ja, bietet sich evtl. A* an, sonst nicht).


das wäre aber ein bekannter algorithmus -> NOT :)

Zitat von »"dot"«


was genau bezweckst du damit?

frag das die veranstalter an meiner uni, die mir die aufgabe gestellt haben, keine ahnung.

deshalb fällt std::list auch flach und ist zudem noch in java (auch wenn es da sicherlich ähnliche konstrukte gibt)
versteht mich nicht falsch, ich will hier keine komplette lösung haben, nur ich darf mir höchstens 2 praktika leisten, die nicht fehlerfrei durch das testsystem durchkommen, ansonsten keine klausurzulassung.
und da die abgabe immer näher rückt, und ich trotzdem einfach immer an der gleichen stelle hänge werde ich langsam nervös.
laut unserem prof sollten die aufgaben in 2-3 stunden lösbar sein und das hab ich schon doppelt und dreifach reingesteckt, aber ich komm halt nicht weiter und das wird hier leider leider mit 0 punkten geahndet :/

/edit: also um es nochmal zu beschreiben, mein problem ist nicht der algorithmus an sich, sondern den kram in das array einzutragen. den wert des kürzesten weges zu berechnen könnte mit dem was ich im moment habe sogar schon klappen. aber es funktioniert ja nicht immer die koordinaten des aktuellen feldes schon in das ergebnisarray einzutragen (falls der aktuelle weg wirklich cder kürzeste sein sollte). genauso wenig kann man aber zb. in nem bool array speichern welche felder alle besucht wurden, weil man danach die reihenfolge nicht mehr weiß.
ich hasse es unter druck zu coden weil mir fallen dann auch echt keine ideen mehr ein :(

grek40

Alter Hase

Beiträge: 1 491

Wohnort: Dresden

  • Private Nachricht senden

5

06.05.2007, 11:09

Also ich weiß jetzt nicht, wie es bei Java aussieht, aber falls es da etwas vergleichbares zu std::list gibt solltest du es auch dringend nutzen, da das genau das Problem mit eintragen und austragen von Koordinaten ins Ergebnisarray lösen würde... wenn am Ende unbedingt ein Array stehen muss kannst du immernoch sobald du fertig bist ein Array erstellen, was die entsprechende Größe hat und dort alle Listenelemente reinkopieren...

Soll der Algorithmus eigentlich eher effizient oder gründlich sein?

Sk!p

Alter Hase

  • »Sk!p« ist der Autor dieses Themas

Beiträge: 568

  • Private Nachricht senden

6

06.05.2007, 12:24

hab ich auch gemacht, gibt eine datenstruktur, die heißt vector, da kann man das genauso machen. allerdings hagelt es nur noch NullPointerExceptions und ArrayIndexOutOfBoundsExceptions und ich hab keine ahnung und keinen überblick mehr und ich lass es jetzt sein. keine lust mehr mich stundenlang mit dem kram rumzuplagen, wenn am ende sowieso 0 punkte rauskommen.

/edit: ich kann ja hier mal meinen code posten, ist zu c++ sehr ähnlich. dass er unübersichtlich und umständlich hoch 10 ist braucht ihr mir nicht zu sagen, aber ich weigere mich bei so einem Zeitdruck ordentlich zu coden, wenn wir in der uni beigebracht kriegen, dass wir in aller ruhe das problem analysieren sollen.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

public int[][] getShortestPath(int destinationX, int destinationY){
        
if((destinationX < 0) || (destinationX > map.length) ||
           (destinationY < 0) || (destinationY > map[0].length))
            throw new IllegalArgumentException("Coordinates invalid!");
                
        InitBest();
                
        for(int i = 0; i < map.length; i++)
        {
            min = 0;
                    
            ShortestPathOrigin(i, 0, destinationX, destinationY);
        }
        
        return result;
    }

private void ShortestPathOrigin(int orig_x, int orig_y, int dest_x, int dest_y)
    {
        int[] coords = {orig_x, orig_y};
        
        min += map[orig_x][orig_y];
        
        if((min > bestSolution) || (tmp.contains(coords)))
        {
            min -= map[orig_x][orig_y];
            return;
        }
        
        tmp.add(coords);
        
        if((Math.abs(orig_x - dest_x) <= 1) && (Math.abs(orig_y - dest_y) <= 1))
        {
            min += map[dest_x][dest_y];
            
            if(min < bestSolution)
            {
                bestSolution = min;
                
                int counter = 0;
                
                result = new int[tmp.size()][2];
                
                while(!tmp.isEmpty())
                {
                    int[] value = (int[])tmp.firstElement();
                    
                    result[counter][0] = value[0];
                    result[counter][1] = value[1];
                    
                    counter++;
                }
                
                result[counter][0] = dest_x;
                result[counter][1] = dest_y;
            }
            
            min -= map[dest_x][dest_y];
            
            return;
        }
        
        for(int x = -1; x <= 1; x++)
        {
            for(int y = -1; y <= 1; y++)
            {
                if(ValidCoords(orig_x + x, orig_y + y))
                    ShortestPathOrigin(orig_x + x, orig_y + y, dest_x, dest_y);
            }
        }
        
        min -= map[orig_x][orig_y];
        tmp.setSize(tmp.size() - 1);
    }
    
    private void InitBest()
    {
        bestSolution = 0;
        
        for(int x = 0; x < map.length; x++)
        {
            for(int y = 0; y < map.length; y++)
            {
                bestSolution += map[x][y];
            }
        }
    }
    
    private boolean ValidCoords(int x, int y)
    {
        if((x < 0) || 
           (x > map.length) ||
           (y < 0) ||
           ((x == 0) && (y == 0)))
            return false;
        
        return true;
    }


Wenn ich später noch Lust hab kommentier ich das vielleicht noch aber jegliche Abgaben, die unter 100% Funktionstüchtigkeit liegen sind nicht bestanden, deshalb fehlt mir da gerade die Motivation zu.

Werbeanzeige