Algoritmo: cammino minimo con più tappe

di
Andromeda42
il
2 risposte
A
Andromeda42
Pochi posts
Iscritto da
mar, 2024
Messaggi:
2

Algoritmo: cammino minimo con più tappe

Buongiorno a tutti, mi servirebbe un aiuto/consiglio per questo problema.

Data una matrice contenente celle con valori 0 o 1, sapendo che due celle sono collegate se hanno almeno un lato in comune (quindi non sono collegate in diagonale) quale è il minimo numero di 1 che devo aggiungere (sostituendo uno 0) per collegare tutti gli 1?

Esempio:

0 0 1 0 0 0 0				0 0 1 0 0 0 0
0 0 0 0 1 0 1      -->   	0 0 1 0 1 1 1
1 0 0 0 0 1 0 	   (6)		1 1 1 1 1 1 0
0 0 0 1 0 0 0				0 0 0 1 0 0 0

Difficoltà in più:

Se attivassi l'effetto pacman (prima e ultima riga/colonna sono collegate)?

Esempio:

0 1 0 0 0 0 0 0 0			1 1 1 1 0 0 0 1 1
0 0 0 0 0 0 0 1 0	-->		0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0	(6)		0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0			0 0 0 1 1 0 0 0 0

2 Risposte

  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6072

    Re: Algoritmo: cammino minimo con più tappe

    Che aiuto/consiglio vuoi?

    La soluzione, a ‘stima’/ ‘spannometricamente’ parlando, NON E' banale.

    1. e' un problema combinatorio, quindi COMPLICATO
    2. puo' essere modellato come un grafo/mesh/griglia, quindi si possono utilizzare gli algoritmi della teoria dei grafi
    3. il vincolo ‘no diagonale’ implica la distanza di Manhattan
    4. una soluzione ‘fighissima’ e' usare gli alberi di Steiner, ma e' robbba decisamente  ‘sofisticata’ di teoria dei grafi
    5. poiche' la griglia e' regolare, probabilmente c'e' qualcosa di meglio
    6. un'altra soluzione (che andrebbe di moda oggi) e' l'utilizzo del “Reinforcement Learning”
    7. ultimo, ma non meno importante, la soluzione "Chiedilo a ChatGPT" (se no OpenAI come fa a fare i miliardi vendendo fumo?) ;-)

    .

    Da dove salta fuori questo problema? Sapendo chi l'ha proposto e perche' magari si puo' supporre l'esistenza di un approccio decisamente piu' semplice, senza scomodare soluzioni complicate.

    DI SICURO, una soluzione NON BASATA sui concetti della teoria dei grafi sarebbe inutilmente complicata e arzigogolata. 

    Invece usando gli algoritmi per navigare sui grafi, una soluzione ‘elegante’ (quindi semplice da capire e implementare), anche se NON OTTIMA, c'e'.

  • A
    Andromeda42
    Pochi posts
    Iscritto da
    mar, 2024
    Messaggi:
    2

    Re: Algoritmo: cammino minimo con più tappe

    23/03/2024 - migliorabile ha scritto:

    Che aiuto/consiglio vuoi?

    La soluzione, a ‘stima’/ ‘spannometricamente’ parlando, NON E' banale.

    1. e' un problema combinatorio, quindi COMPLICATO
    2. puo' essere modellato come un grafo/mesh/griglia, quindi si possono utilizzare gli algoritmi della teoria dei grafi
    3. il vincolo ‘no diagonale’ implica la distanza di Manhattan
    4. una soluzione ‘fighissima’ e' usare gli alberi di Steiner, ma e' robbba decisamente  ‘sofisticata’ di teoria dei grafi
    5. poiche' la griglia e' regolare, probabilmente c'e' qualcosa di meglio
    6. un'altra soluzione (che andrebbe di moda oggi) e' l'utilizzo del “Reinforcement Learning”
    7. ultimo, ma non meno importante, la soluzione "Chiedilo a ChatGPT" (se no OpenAI come fa a fare i miliardi vendendo fumo?) ;-)

    .

    Da dove salta fuori questo problema? Sapendo chi l'ha proposto e perche' magari si puo' supporre l'esistenza di un approccio decisamente piu' semplice, senza scomodare soluzioni “ufo” ;-) e complicate.

    DI SICURO, una soluzione NON BASATA sui concetti della teoria dei grafi sarebbe inutilmente complicata e arzigogolata. 

    Invece usando gli algoritmi per navigare sui grafi, una soluzione ‘elegante’ (quindi semplice da capire e implementare), anche se NON OTTIMA, c'e'.

    Il problema me lo sono inventato, avevo anche già provato a chiedere a ChatGPT ma senza successo.
    L'aiuto/consiglio che chiedevo erano, appunto, appigli teorici su cui basare l'algoritmo, ringrazio per gli spunti dati e per il momento posso solo dire che approfondirò.

    Rimango vigile per ulteriori future idee :)

Devi accedere o registrarti per scrivere nel forum
2 risposte