Algoritmo cammino matrice

phi

il 01 giu 2023, 11:06

14 risposte

phi

Pochi posts

Iscritto da: ago, 2020

Messaggi:: 8

Algoritmo cammino matrice

01 giu 2023, 11:09

Ho bisogno di un piccolo input per creare un algoritmo. Assumiamo di avere una matrice NxM di interi. Possiamo avere come valori o 0 oppure un numero da 1 a 9. Le celle con lo zero indicano le celle accessibili, mentre le altre no. Partendo dal punto inziale 0,0 in alto a sinistra, devo arrivare all'ultima cella in basso a destra (n-1, m-1). Ci si puo spostare in quattro direzioni: sopra, sotto, destra e sinistra. Mi serve trovare un algoritmo del cammino minimo per questo problema, ma non saprei come adattarmi non avendo mai usato i cammini minimi nelle matrici ma sempre nei grafi. Grazie tante.

14 Risposte

M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6072
Re: Algoritmo cammino matrice
01 giu 2023, 13:21
Suvvia, “spremi” quell'UNICO neurone che ti e' rimasto ;-)
Suggerimento: una matrice E' un grafo!
Lo hai PURE SCRITTO !
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1238
Re: Algoritmo cammino matrice
01 giu 2023, 14:37
Io non ne so niente di “grafi” e "cammino minimo" come argomenti di studio, ma andando a logica qualche idea ce l'avrei:
- inizialmente, quando ancora non è stato individuato alcun percorso che collega il punto di partenza a quello di arrivo, mi limiterei ad utilizzare un semplice processo iterativo di ricerca che si sposta da un elemento all'altro nelle 4 direzioni;
- se non viene trovato alcun cammino, abbiamo finito, in caso contrario invece andiamo a memorizzarne la lunghezza in un'apposita variabile N;
- a questo punto si riprende il suddetto processo iterativo e nel momento in cui si trova un nuovo cammino di lunghezza minore di N, allora si aggiorna N col nuovo valore;
- ovviamente ci sono vari accorgimenti per ottimizzare la ricerca. Per esempio dopo che un elemento è stato già testato in tutte e 4 le direzioni possiamo associargli un vettore contente il cammino minimo parziale che lo collega al punto di arrivo (ossia contenente la sequenza di indirizzi degli elementi costituenti il cammino minimo parziale). A questo punto se nel processo iterativo ci imbattiamo in un nodo che è stato già precedentemente analizzato in tutte le direzioni, allora possiamo utilizzare N e il vettore cammino minimo parziale ad esso associato per trarne le dovute conclusioni.
Ovviamente nel momento in cui si passa dalla teoria alla pratica possono insorgere problemi a cui non si aveva pensato, ma in linea di massima mi sembra che possa aver senso come algoritmo.
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6072
Re: Algoritmo cammino matrice
01 giu 2023, 15:12
Hai appena descritto l'algo per camminare su un grafo :-)
comunque l'algo si trova su QUALUNQUE LIBRO di algoritmi e strutture dati
Non serve inventarsi niente, BASTA leggere/studiare ;-)
P
phi
Pochi posts
Iscritto da
ago, 2020
Messaggi:
8
Re: Algoritmo cammino matrice
01 giu 2023, 15:22
01/06/2023 - Nippolo ha scritto:
Io non ne so niente di “grafi” e "cammino minimo" come argomenti di studio, ma andando a logica qualche idea ce l'avrei:
- inizialmente, quando ancora non è stato individuato alcun percorso che collega il punto di partenza a quello di arrivo, mi limiterei ad utilizzare un semplice processo iterativo di ricerca che si sposta da un elemento all'altro nelle 4 direzioni;
- se non viene trovato alcun cammino, abbiamo finito, in caso contrario invece andiamo a memorizzarne la lunghezza in un'apposita variabile N;
- a questo punto si riprende il suddetto processo iterativo e nel momento in cui si trova un nuovo cammino di lunghezza minore di N, allora si aggiorna N col nuovo valore;
- ovviamente ci sono vari accorgimenti per ottimizzare la ricerca. Per esempio dopo che un elemento è stato già testato in tutte e 4 le direzioni possiamo associargli un vettore contente il cammino minimo parziale che lo collega al punto di arrivo (ossia contenente la sequenza di indirizzi degli elementi costituenti il cammino minimo parziale). A questo punto se nel processo iterativo ci imbattiamo in un nodo che è stato già precedentemente analizzato in tutte le direzioni, allora possiamo utilizzare N e il vettore cammino minimo parziale ad esso associato per trarne le dovute conclusioni.
Ovviamente nel momento in cui si passa dalla teoria alla pratica possono insorgere problemi a cui non si aveva pensato, ma in linea di massima mi sembra che possa aver senso come algoritmo.
Ci provo, grazie tante
P
phi
Pochi posts
Iscritto da
ago, 2020
Messaggi:
8
Re: Algoritmo cammino matrice
01 giu 2023, 15:25
01/06/2023 - migliorabile ha scritto:
Hai appena descritto l'algo per camminare su un grafo :-)
comunque l'algo si trova su QUALUNQUE LIBRO di algoritmi e strutture dati
Non serve inventarsi niente, BASTA leggere/studiare ;-)
Guardi che non c'è bisogno di rispondere in modo scortese. Questo forum è per chi ha bisogno, non starei qui a scrivere se sul libro era presente la soluzione al MIO problema!
Ora faccio marciare l'unico neurone che mi rimane e cerco di risolvere il problema, se ha consigli su come procedere sono ben accetti, il resto non lo leggo. grazie tante anche a lei ;)
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1238
Re: Algoritmo cammino matrice
01 giu 2023, 16:35
01/06/2023 - migliorabile ha scritto:
Hai appena descritto l'algo per camminare su un grafo :-)
comunque l'algo si trova su QUALUNQUE LIBRO di algoritmi e strutture dati
Non serve inventarsi niente, BASTA leggere/studiare ;-)
Preferisco inventare piuttosto che leggere/studiare, e coi soldi del libro mi ci compro un bel gelato!
M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6072
Re: Algoritmo cammino matrice
01 giu 2023, 17:06
@Nippolo, e' un punto di vista ovviamente ;-)
Comunque, dato il prezzo dei libri a cui mi riferivo, di gelati ne puoi acquistare una quarantina ;-)
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1238
Re: Algoritmo cammino matrice
01 giu 2023, 17:20
Si scherza, figurati! =)
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1238
Re: Algoritmo cammino matrice
02 giu 2023, 22:18
Dal momento che mi sto cimentando nell'implementare il suddetto algoritmo, mi chiedevo se di cammino minimo ce n'è più di uno, è corretto considerarne solo uno ed ignorare gli altri? Cioè di solito come ci si comporta a tal riguardo?
P
phi
Pochi posts
Iscritto da
ago, 2020
Messaggi:
8
Re: Algoritmo cammino matrice
02 giu 2023, 22:31
02/06/2023 - Nippolo ha scritto:
Dal momento che mi sto cimentando nell'implementare il suddetto algoritmo, mi chiedevo se di cammino minimo ce n'è più di uno, è corretto considerarne solo uno ed ignorare gli altri? Cioè di solito come ci si comporta a tal riguardo?
Nel caso di più cammini, bisogna considerare quello che attraversa il minor numero di celle. Nel caso più cammini attraversano lo stesso minor numero di celle, si prenda in considerazione il primo trovato.

phi

Pochi posts

Iscritto da: ago, 2020

Messaggi:: 8

Re: Algoritmo cammino matrice

03 giu 2023, 18:55

Dal momento che mi sto cimentando nell'implementare il suddetto algoritmo, mi chiedevo se di cammino minimo ce n'è più di uno, è corretto considerarne solo uno ed ignorare gli altri? Cioè di solito come ci si comporta a tal riguardo?

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int row;
    int col;
} Cell;

void explorePaths(int matrix[5][5], int row, int col, Cell* currentPath, int pathLength, Cell** paths, int* numPaths) {
    int n = 10;
    
    if (row == n - 1 && col == n - 1) {
        // Siamo arrivati alla cella di arrivo
        Cell* newPath = malloc(pathLength * sizeof(Cell));
        for (int i = 0; i < pathLength; i++) {
            newPath[i] = currentPath[i];
        }
        paths[*numPaths] = newPath;
        (*numPaths)++;
        return;
    }
    
    // Movimenti possibili: sopra, sotto, destra, sinistra
    int directions[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    
    for (int i = 0; i < 4; i++) {
        int newRow = row + directions[i][0];
        int newCol = col + directions[i][1];
        
        // Verifica se la nuova posizione è all'interno della matrice e se è accessibile
        if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && matrix[newRow][newCol] == 0) {
            // Segna la cella come visitata
            matrix[newRow][newCol] = 1;
            currentPath[pathLength] = (Cell){newRow, newCol};
            
            // Continua l'esplorazione ricorsiva
            explorePaths(matrix, newRow, newCol, currentPath, pathLength + 1, paths, numPaths);
            
            // Ripristina la cella come non visitata per le iterazioni successive
            matrix[newRow][newCol] = 0;
        }
    }
}

Cell** findPaths(int matrix[5][5], int* numPaths) {
    Cell** paths = malloc(1000 * sizeof(Cell*));
    Cell* currentPath = malloc(100 * sizeof(Cell));
    currentPath[0] = (Cell){0, 0};
    
    *numPaths = 0;
    explorePaths(matrix, 0, 0, currentPath, 1, paths, numPaths);
    
    free(currentPath);
    return paths;
}

void printPaths(Cell** paths, int numPaths, int n) {
    for (int i = 0; i < numPaths; i++) {
        for (int j = 0; j < n * n; j++) {
            printf("(%d, %d) ", paths[i][j].row, paths[i][j].col);
        }
        printf("\n");
    }
}

void printShortestPath(Cell** paths, int numPaths, int n) {
    int shortestIndex = 0;
    int shortestLength = n * n;
    
    for (int i = 0; i < numPaths; i++) {
        int pathLength = 0;
        for (int j = 0; j < n * n; j++) {
            if (paths[i][j].row == -1 && paths[i][j].col == -1) {
                break;
            }
            pathLength++;
        }
        
        if (pathLength < shortestLength) {
            shortestLength = pathLength;
            shortestIndex = i;
        }
    }
    
    printf("Percorso minimo (%d celle):\n", shortestLength);
    for (int i = 0; i < shortestLength; i++) {
        printf("(%d, %d) ", paths[shortestIndex][i].row, paths[shortestIndex][i].col);
    }
    printf("\n");
}

void freePaths(Cell** paths, int numPaths) {
    for (int i = 0; i < numPaths; i++) {
        free(paths[i]);
    }
    free(paths);
}

int main() {
    int matrix[5][5] = {
        {0, 0, 0, 0, 0},
        {1, 1, 0, 1, 0},
        {0, 0, 0, 0, 0},
        {1, 0, 1, 0, 1},
        {0, 0, 0, 0, 0}
    };

    int numPaths = 0;
    Cell** paths = findPaths(matrix, &numPaths);

    printPaths(paths, numPaths, 5);

    freePaths(paths, numPaths);

    printShortestPath(paths, numPaths, 10);

    return 0;
}

Ho provato a scrivere questo algoritmo ma non funziona, non riesco a trovare l'errore. Cosa ne pensi?

Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1238
Re: Algoritmo cammino matrice
05 giu 2023, 12:32
03/06/2023 - phi ha scritto:
Ho provato a scrivere questo algoritmo ma non funziona, non riesco a trovare l'errore. Cosa ne pensi?
Appena ho tempo rifletto meglio sul problema, e quando avrò le idee più chiare darò uno sguardo al tuo codice per cercare di capire quello che non va.

Weierstrass

Utente Famoso

Iscritto da: feb, 2019

Messaggi:: 2248

Re: Algoritmo cammino matrice

06 giu 2023, 17:44

Perché non parti dall'algoritmo standard?

#include <stdio.h>

#define N 5
#define M 5
 
typedef struct {
    int row;
    int col;
    int dist;
} LOC;

LOC QUEUE[N * M];
int Rear  = -2;
int Front = -1;

void push(int r, int c, int d){
    if (Rear < 0)
        Rear = 0;
    else
        Rear++;
    if (Front < 0)
        Front = 0;
    QUEUE[Rear].row = r;
    QUEUE[Rear].col = c;
    QUEUE[Rear].dist = d;    
} 
 
void pop(){
    Front++;
}

char empty(){
    return Front > Rear;
}
 
int minDist(int grid[N][M]){
    int visited[N][M];
    
    // copy
    for (int i = 0; i < N; i++) 
        for (int j = 0; j < M; j++)
            visited[i][j] = grid[i][j];

    // start
    push(0, 0, 0);
    visited[0][0] = 1;
    
    while (!empty()) {
        LOC p = QUEUE[Front];
        pop();
 
        // end
        if (p.row == N - 1 && p.col == M - 1)
            return p.dist;
 
        // up
        if (p.row - 1 >= 0 && !visited[p.row - 1][p.col]) {
            push(p.row - 1, p.col, p.dist + 1);
            visited[p.row - 1][p.col] = 1;
        }
 
        // down
        if (p.row + 1 < N && !visited[p.row + 1][p.col]) {
            push(p.row + 1, p.col, p.dist + 1);
            visited[p.row + 1][p.col] = 1;
        }
 
        // left
        if (p.col - 1 >= 0 && !visited[p.row][p.col - 1]) {
            push(p.row, p.col - 1, p.dist + 1);
            visited[p.row][p.col - 1] = 1;
        }
 
        // right
        if (p.col + 1 < M && !visited[p.row][p.col + 1]) {
            push(p.row, p.col + 1, p.dist + 1);
            visited[p.row][p.col + 1] = 1;
        }
    }
    return -1; // path not found
}
 
int main(){
    int matrix[N][M] = {
        {0, 0, 0, 0, 0},
        {1, 1, 0, 1, 0},
        {0, 0, 0, 0, 0},
        {1, 0, 1, 0, 1},
        {0, 0, 0, 0, 0}
    };
 
    printf("%d", minDist(matrix));
    return 0;
}

Nippolo

Molto attivo

Iscritto da: mar, 2018

Messaggi:: 1238

Re: Algoritmo cammino matrice

08 giu 2023, 15:49

06/06/2023 - Weierstrass ha scritto:
Perché non parti dall'algoritmo standard?

Io stavo implementando una versione ricorsiva basata su un'idea di fondo un po' diversa, ma questa versione iterativa la trovo concettualmente più semplice, in pratica si analizzano le celle in ordine di distanza dall'origine finché non viene individuata la destinazione.

Nel far girare il codice per capirne il funzionamento già che c'ero l'ho generalizzato per cella di partenza e arrivo generiche e ho aggiunto una funzione per estrarre il cammino minimo dall'array QUEUE:

#include <stdio.h>
#include <string.h>
#include <windows.h>

#define R 16
#define C 15

typedef struct
{
    unsigned int i;
    unsigned int j;
    unsigned int n;
}   nodo;

void estrai_cammino_minimo(nodo v[R * C], int *u[R * C], int m[R][C], unsigned int K)
{
    u[0] = &m[v[0].i][v[0].j];
    u[v[K].n - 1] = &m[v[K].i][v[K].j];
    for(unsigned int k = K; --K;)
    {
        if(v[K].i == v[k].i ? v[K].j == v[k].j + 1 || v[K].j + 1 == v[k].j : v[K].j == v[k].j && (v[K].i == v[k].i + 1 || v[K].i + 1 == v[k].i))
        {
            for(u[v[k = K].n - 1] = &m[v[K].i][v[K].j]; v[K].n == v[K - 1].n; --K);
        }
    }
}

unsigned int cammino_minimo(int *u[R * C], int m[R][C], int *START, int *END)
{
    if(!*START && !*END && START != END)
    {
        int m2[R][C];
        memcpy(*m2, *m, R * C * sizeof(**m));
        nodo v[R * C];
        m2[v[0].i = (START - *m) / C][v[0].j = (START - *m) % C] = v[0].n = 1;
        for(unsigned int i_end = (END - *m) / C, j_end = (END - *m) % C, last = 0, curr = 0; curr <= last; ++curr)
        {
            if(v[curr].i == i_end && v[curr].j == j_end)
            {
                estrai_cammino_minimo(v, u, m, curr);
                return v[curr].n;
            }
            if(v[curr].j != C - 1 && !m2[v[curr].i][v[curr].j + 1])//RIGHT
            {
                m2[v[last].i = v[curr].i][v[last].j = v[curr].j + 1] = v[++last].n = v[curr].n + 1;
            }
            if(v[curr].i != R - 1 && !m2[v[curr].i + 1][v[curr].j])//DOWN
            {
                m2[v[last].i = v[curr].i + 1][v[last].j = v[curr].j] = v[++last].n = v[curr].n + 1;
            }
            if(v[curr].j && !m2[v[curr].i][v[curr].j - 1])//LEFT
            {
                m2[v[last].i = v[curr].i][v[last].j = v[curr].j - 1] = v[++last].n = v[curr].n + 1;
            }
            if(v[curr].i && !m2[v[curr].i - 1][v[curr].j])//UP
            {
                m2[v[last].i = v[curr].i - 1][v[last].j = v[curr].j] = v[++last].n = v[curr].n + 1;
            }
        }
    }
    return 0;
}

void stampa_cammino_minimo(int *u[R * C], int m[R][C], const unsigned int n)
{
    for(unsigned int i = 0; i < R; ++i)
    {
        printf("\n");
        for(unsigned int j = 0; j < C; ++j)
        {
            SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), m[i][j] ? 12 + 16 * 8 : 7 + 16 * 8);
            printf(" %c", 254);
        }
    }
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 10 + 16 * 8);
    for(unsigned int k = 0; k < n; ++k)
    {
        SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), (COORD){(u[k] - *m) % C * 2 + 1, (u[k] - *m) / C + 1});
        printf("%c", 254);
    }
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), (COORD){0, R});
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
    printf("\n\n LUNGHEZZA CAMMINO MINIMO: %u\n", n);
}

int main()
{
    int m[R][C] = {{0, 0, 0, 0, 2, 7, 0, 0, 1, 0, 0, 0, 0, 0, 0},
                   {0, 3, 0, 0, 0, 4, 0, 0, 0, 2, 0, 8, 0, 0, 0},
                   {0, 0, 8, 0, 0, 0, 6, 0, 0, 0, 5, 0, 5, 0, 0},
                   {0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                   {0, 0, 0, 5, 0, 0, 0, 0, 1, 0, 0, 0, 0, 7, 2},
                   {0, 0, 2, 0, 7, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0},
                   {5, 0, 0, 0, 0, 5, 0, 0, 9, 0, 0, 0, 0, 4, 0},
                   {0, 1, 9, 0, 0, 0, 4, 0, 0, 7, 0, 0, 0, 0, 0},
                   {0, 0, 6, 0, 0, 6, 0, 8, 0, 0, 1, 0, 3, 0, 0},
                   {0, 0, 0, 0, 3, 0, 1, 0, 0, 0, 0, 8, 0, 0, 0},
                   {0, 7, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0},
                   {0, 0, 9, 0, 0, 0, 0, 0, 0, 4, 0, 0, 1, 0, 0},
                   {0, 1, 0, 4, 0, 0, 9, 0, 2, 0, 0, 9, 5, 8, 0},
                   {0, 0, 0, 0, 6, 0, 0, 4, 0, 0, 6, 0, 6, 0, 0},
                   {2, 0, 8, 3, 0, 7, 0, 0, 8, 0, 0, 0, 0, 0, 0},
                   {0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 9, 0, 0}};

    int *u[R * C];
    unsigned int n = cammino_minimo(u, m, &m[13][3], &m[1][12]);
    stampa_cammino_minimo(u, m, n);
    return 0;
}

Devi accedere o registrarti per scrivere nel forum

14 risposte