[generico] Trovare percorso ottimo in una matrice per coprirla tutta

[Dani88]

Ciao a tutti :)
avrei bisogno di alcuni consigli: in pratica io ho una matrice di 0 e 1 ove uno dei due rappresenta la possibilità di passare da quel quadrato, l'altro invece mi dice che non posso passare.
Una cosa del tipo

[1] [1] [1] [1] [1] [1]
[1] [0] [0] [0] [0] [1]
[1] [0] [1] [0] [0] [1]
[1] [0] [0] [0] [0] [1]
[1] [0] [0] [0] [0] [1]
[1] [1] [1] [1] [1] [1]

mi delimita un quadrato all'interno cui posso muovermi che presenta un ostacolo nella parte centrale verso SXalto.

Ora io avrei bisogno, partendo da un punto della matrice (per ora non so se fissato o meno) di calcolare il percorso ottimo per attraversare tutta la matrice, ovvero passare su tutte le caselle con gli zeri.
Ci sto pensando da un po di tempo, ma non sono riuscito per ora a tirare fuori nulla di utile...
Riuscite a darmi qualche dritta?

[:.Blizzard.:]

Prima di tutto servirebbe ben capire cosa intendi per cammino ottimo.

Ad ogni modo, visto che parliamo di cammini sarebbe utile vedere la tua matrice proprio come un grafo (attenzione, non una matrice di adiacenza!).

Praticamente gli 0 rappresentano nodi. Per ogni nodo controlli i suoi vicini all'interno della matrice. Se il vicino è 0, allora puoi aggiungere un arco che li collega. Così facendo ti crei il grafo connesso.

Dopodiché si tratta appunto di capire cosa intendi tu per cammino ottimo. Perché se per cammino ottimo intendi un cammino hamiltoniano

http://upload.wikimedia.org/wikipedia/it/b/bd/Grafo_con_circuito_hamiltoniano.png


allora siamo nella classe di problemi NP-completi.

Prova a girare per internet, magari trovi qualcosa a riguardo.


Altrimenti, se non ti interessa di avere come soluzione un'unico cammino ma semplicemente di visitare tutti i vertici (che ti ricordo essere i tuoi 0 della matrice) allora la cosa è molto più semplice e ti basta fare una DFS del grafo:

http://www.cs.sunysb.edu/~skiena/combinatorica/animations/anim/dfs.gif

Con la DFS riesci a vedere anche se ci sono componenti sconnesse, ovvero nel tuo caso se ci sono degli 0 circondati completamente da 1.

[Dani88]

ti ringrazio per la dritta del grafo!! non ci avevo proprio pensato....
Dunque provo a definirti meglio il problema: io ho un robot che deve fare auto-learn dell'ambiente dove viene messo e deve coprirlo tutto.
A questo punto ho pensato: la prima volta lo faccio andare a caso e gli faccio costruire una matrice che mi rappresenta l'ambiente (dove ad esempio ogni casella della matrice rappresenta una zona di 10x10cm) e finchè incontra libero segna 0 se incontra un'ostacolo marca 1...
(la cosa è da perfezionare un attimo...anche se inizio a pensare che non sia il metodo più furbo e veloce)
Comunque nell'ipotesi di fare in tal modo, ho pensato una volta costruita la matrice (oppure che gli venga data dall'esterno) il robot dovrebbe coprire tutto l'ambiente andando però non più a caso ma seguendo un percorso che gli permetta di minimizzare gli spostamenti e l'urto con gli ostacoli...quindi non più a caso... :D

[:.Blizzard.:]

Purtroppo intelligenza artificiale ancora mi manca come corso da seguire :D

Il mio amico che l'ha già seguita invece ha programmato con LabView proprio un robottino. Praticamente per terra aveva messo un telo bianco e con dello scotch nero ha costruito una sorta di percorso. Ogni tanto la strada era sbarrata da scotch rosso che veniva interpretata (tramite i sensori di cui il robottino era dotato) come un ostacolo. Il goal era far sì che il robot raggiungesse un determinato punto indicato con lo scotch verde all'interno di tutto il percorso.

Ad ogni modo, così a senso ti dico che secondo me la soluzione ideale è vedere appunto la tua matrice come un grafo.

Poi tutto dipende da come è fatto l'ambiente. Nel senso se c'è un percorso per terra disegnato in qualche modo oppure se si tratta di un ambiente aperto.

Nel primo caso, ovvero quello in cui lo spazio esplorabile è qualcosa di molto semplice come può essere un percorso segnato con dello scotch, secondo me non serve nemmeno che il robot abbia noto a priori l'ambiente che lo circonda. Questo perché l'esplorazione avrebbe una logica molto a "stack" proprio come nella DFS: se guardi la gif animata si capisce proprio bene, e l'atto di riprendere da un punto per imboccare una nuova strada lo raggiungi semplicemente facendo tornare a ritroso il robot al punto di bivio.

Comunque le mie sono osservazioni da profano, prendile come semplici spunti da cui partire. Considera che la questione è abbastanza complessa da trattare. Se vuoi trovare una soluzione seria ti conviene consultare qualche libro di intelligenza artificiale.

[Dani88]

si forse hai ragione...
Lo spazio sarebbe aperto, senza riferimenti (robot che seguono linee o simili ne ho fatto qualcuno, però li è molto più semplice perchè il robot ha riferimenti...).
Le uniche cose che ha come "riferimenti" sono i dati provenienti dai sensori di tocco o di distanza...
Inoltre stavo pensando che implementare un algoritmo del genere che lavori su matrici che sarebbero anche "grosse" (se si considera un ambiente di tipo 4x5m comincia a diventare di 40x50 elementi) su microcontrollore non so quanto possa essere efficiente...

[:.Blizzard.:]

Allora visto che deve essere un progetto serio, ti consiglio di armarti di pazienza e di partire da qualche libro di intelligenza artificiale.

In italiano esiste questo:

http://books.google.it/books?id=cNyndn1eI64C&pg=PA160&lpg=PA160&dq=intelligenza+artificiale+esplorare+ambienti&source=bl&ots=fhrJttcRXS&sig=DQZBN0sJapqGU1KqywtR4uwQQhY&hl=it&ei=ru3TTOf1JYuVOrXwxdMF&sa=X&oi=book_result&ct=result&resnum=4&ved=0CCQQ6AEwAw#v=onepage&q&f=false