Encontrando a rota entre duas UFs

[JoséQuintas]

A IA me deu uma rotina que achei interessante, mas não funcionava.
Acabei refazendo, porque achei a idéia interessante.
Tem a lista de cada UF, e a lista das UFs vizinhas de cada uma.
A rotina vai testando a passagem pelas vizinhas, até encontrar uma lista que chegue ao destino.

Código: Selecionar todos

PROCEDURE Main

   SetMode(33,100)
   CLS
   AltD()
   ? "SP-RJ"
   ? hb_ValToExp( TrajetoPorUF( "SP", "RJ" ) )
   ? "SP-SE"
   ? hb_ValToExp( TrajetoPorUF( "SP", "SE" ) )
   ? "SP-RS"
   ? hb_ValToExp( TrajetoPorUF( "SP", "RS" ) )
   ? "RR-SP"
   ? hb_ValToExp( TrajetoPorUF( "RR", "SP" ) )

   Inkey(0)

   RETURN

FUNCTION TrajetoPorUF( cUFOrigem, cUFDestino )

   LOCAL aList, aList2, aTrajeto, aNewList, cUF, xItem, xItem2

   IF cUFOrigem == cUFDestino
      ? "Passando por: " + cUFOrigem
      RETURN NIL
   ENDIF

   aList := { { cUFOrigem, { cUFOrigem } } }

   DO WHILE .T.
      IF Len( aList[1][2] ) > 20
         ? "Quase o Brasil inteiro na lista"
         EXIT
      ENDIF
      FOR EACH xItem IN aList
         IF xItem[1] == cUFDestino
            RETURN xItem[2]
         ENDIF
      NEXT
      cUF := aList[1][1]
      aList2 := aList[1][2]
      hb_ADel( aList, 1, .T. )
      aTrajeto := GetVizinhos( cUF )
      //? "vizinhos", nPass, hb_ValToExp( aTrajeto )
      //Inkey(10)
      FOR EACH xItem IN aTrajeto
         aNewList := {}
         FOR EACH xItem2 IN aList2
            AAdd( aNewList, xItem2 )
         NEXT
         AAdd( aNewList, xItem )
         //? "adicionado", nPass, hb_ValToExp( { xItem, aNewList } )
         //Inkey(10)
         AAdd( aList, { xItem, aNewList } )
      NEXT
   ENDDO

   ? "Não foi possível encontrar trajeto entre " + cUFOrigem + " e " + cUFDestino
   RETURN NIL

FUNCTION GetVizinhos( cUF )
   LOCAL aVizinhos := { ;
      { "AC", { "AM", "RO" } }, ;
      { "AL", { "PE", "SE", "BA" } }, ;
      { "AP", { "PA" } }, ;
      { "AM", { "RR", "PA", "MT", "RO", "AC" } }, ;
      { "BA", { "SE", "AL", "PE", "PI", "TO", "GO", "MG", "ES" } }, ;
      { "CE", { "PI", "PE", "PB", "RN" } }, ;
      { "DF", { "GO", "MG" } }, ;
      { "ES", { "BA", "MG", "RJ" } }, ;
      { "GO", { "DF", "MG", "BA", "TO", "MT", "MS" } }, ;
      { "MA", { "PI", "TO", "PA" } }, ;
      { "MT", { "PA", "TO", "GO", "MS", "RO", "AM" } }, ;
      { "MS", { "MT", "GO", "MG", "SP", "PR" } }, ;
      { "MG", { "SP", "RJ", "ES", "BA", "GO", "DF", "MS" } }, ;
      { "PA", { "AP", "MA", "TO", "MT", "AM" } }, ;
      { "PB", { "RN", "CE", "PE" } }, ;
      { "PR", { "SP", "MS", "SC" } }, ;
      { "PE", { "PB", "CE", "PI", "BA", "AL" } }, ;
      { "PI", { "MA", "TO", "BA", "PE", "CE" } }, ;
      { "RJ", { "ES", "MG", "SP" } }, ;
      { "RN", { "PB", "CE" } }, ;
      { "RS", { "SC" } }, ;
      { "RO", { "AC", "AM", "MT" } }, ;
      { "RR", { "AM", "PA" } }, ;
      { "SC", { "PR", "RS" } }, ;
      { "SP", { "RJ", "MG", "MS", "PR" } }, ;
      { "SE", { "BA", "AL" } }, ;
      { "TO", { "MA", "PI", "BA", "GO", "MT", "PA" } } ;
   }
   LOCAL nPos

   nPos  := hb_ASCAN( aVizinhos, {|e| e[1] == cUF } )

   IF nPos > 0
      RETURN aVizinhos[ nPos, 2 ]
   ENDIF

   RETURN {} // Sem vizinhos encontrados (não deve ocorrer para UFs válidas)

rotas.png (28.07 KiB) Exibido 125 vezes

Poderia ser feito o mesmo pra cidades.... sei lá se vale a pena...

[JoséQuintas]

Como funciona:

Começa SP, SP
Vizinhos:

Código: Selecionar todos

      { "SP", { "RJ", "MG", "MS", "PR" } }, ;

Isso cria uma lista de 4 itens
Item RJ, e lista SP,RJ
Item MG, e lista SP,MG
Item MS, e lista SP,MS
Item PR, e lista SP,PR

Como encontra nessa nova lista RJ, pega o array SP,RJ

Se esse primeiro nome for o destino, significa que encontrou.
Senão, a lista vai aumentando com vizinhos de vizinhos.

[JoséQuintas]

Mais uma complementar: rota pra passar em várias UFs.
É selecionado o caminho com menos UFs, pode não ser o mais curto, e pode não ser o caminho mais usado.

Código: Selecionar todos

PROCEDURE Main

   SetMode(33,100)
   CLS
   AltD()
   ? "SP-RN-RS-RJ"
   ? hb_ValToExp( TrajetoVariasUFs( "SP", "RN", "RS", "RJ" ) )
   //? "SP-SE"
   //? hb_ValToExp( TrajetoVariasUFs( "SP", "SE" ) )
   //? "SP-RS"
   //? hb_ValToExp( TrajetoVariasUFs( "SP", "RS" ) )
   //? "RR-SP"
   //? hb_ValToExp( TrajetoVariasUFs( "RR", "SP" ) )
   //? "SP-RN"
   //? hb_ValToExp( TrajetoVariasUFs( "SP", "RN" ) )
   //? "RS-RN"
   //? hb_ValToExp( TrajetoVariasUFs( "RS", "RN" ) )
   //? "MG-DF"
   //? hb_ValToExp( TrajetoVariasUFs( "MG", "DF" ) )

   Inkey(0)

   RETURN

FUNCTION TrajetoVariasUFs( ... )

   LOCAL aUFSource := hb_AParams(), nPos, aUFDestino, aRotaFinal, aRotaOk
   LOCAL cUFOrigem, aItem, cUF, aRotas, aUFList := {}

   FOR EACH cUF IN aUFSource
      IF hb_AScan( aUFList, { | e | e == cUF } ) == 0
         AAdd( aUFList, cUF )
      ENDIF
   NEXT

   IF Len( aUFList ) == 0
      RETURN {}
   ENDIF
   IF Len( aUFList ) == 1
      RETURN { aUFList[1] }
   ENDIF
   FOR EACH cUF IN aUFList
      IF hb_AScan( GetVizinhos(), { | e | e[1] == cUF } ) == 0
         RETURN {}
      ENDIF
   NEXT
   cUFOrigem := aUFList[ 1 ]
   hb_ADel( aUFList, 1, .T. )
   aUFDestino := aClone( aUFList )
   aRotaOk := {}
   DO WHILE .T.
      aRotas := {}
      FOR EACH cUF IN aUFDestino
         AAdd( aRotas, TrajetoPorUf( cUFOrigem, cUF ) )
      NEXT
      ASort( aRotas,,, { | e | Len( e ) } )
      AAdd( aRotaOk, aRotas[ 1 ] )
      nPos := hb_ASCan( aUFDestino, { | e | e == Atail( aRotas[1] ) } )
      cUFOrigem := aUFDestino[ nPos ]
      hb_ADel( aUFDestino, nPos, .T. )
      IF Len( aUFDestino ) == 0
         EXIT
      ENDIF
   ENDDO
   aRotaFinal := {}
   FOR EACH aItem IN aRotaOk
      FOR EACH cUF IN aItem
         IF Atail( aRotaFinal ) != cUF
            AAdd( aRotaFinal, cUF )
         ENDIF
      NEXT
   NEXT

   RETURN aRotaFinal

FUNCTION TrajetoPorUF( cUFOrigem, cUFDestino )

   LOCAL aList, aList2, aTrajeto, aNewList, cUF, xItem, xItem2, aVisitados := {}

   // origem = destino
   IF cUFOrigem == cUFDestino
      RETURN { cUFOrigem }
   ENDIF

   // UF inválida
   IF hb_AScan( GetVizinhos(), { | e | e[1] == cUFOrigem } ) == 0 .OR.  ;
      hb_ASCan( GetVizinhos(), { | e | e[1] == cUFDestino } )  == 0
      RETURN {}
   ENDIF

   aList := { { cUFOrigem, { cUFOrigem } } }

   DO WHILE .T.
      IF Len( aList ) == 0
         EXIT
      ENDIF
      IF Len( aList[1][2] ) > 20
         RETURN {} // Quase o Brasil inteiro na lista
      ENDIF
      IF Len( aVisitados ) > 20
         RETURN {} // Visitou demais
      ENDIF
      FOR EACH xItem IN aList
         IF xItem[1] == cUFDestino
            RETURN xItem[2]
         ENDIF
      NEXT
      cUF := aList[1][1]
      aList2 := aList[1][2]
      hb_ADel( aList, 1, .T. )
      aTrajeto := GetVizinhos( cUF )
      FOR EACH xItem IN aTrajeto
         aNewList := {}
         FOR EACH xItem2 IN aList2
            IF hb_AScan( aNewList, xItem2 ) == 0
               AAdd( aNewList, xItem2 )
            ENDIF
         NEXT
         IF ! Empty( aNewList )
            AAdd( aNewList, xItem )
            AAdd( aList, { xItem, aNewList } )
         ENDIF
      NEXT
   ENDDO

   ? "Não foi possível encontrar trajeto entre " + cUFOrigem + " e " + cUFDestino
   RETURN NIL

FUNCTION GetVizinhos( cUF )
   LOCAL aList := { ;
      { "AC", { "AM", "RO" } }, ;
      { "AL", { "PE", "SE", "BA" } }, ;
      { "AP", { "PA" } }, ;
      { "AM", { "RR", "PA", "MT", "RO", "AC" } }, ;
      { "BA", { "SE", "AL", "PE", "PI", "TO", "GO", "MG", "ES" } }, ;
      { "CE", { "PI", "PE", "PB", "RN" } }, ;
      { "DF", { "GO" } }, ;
      { "ES", { "BA", "MG", "RJ" } }, ;
      { "GO", { "DF", "MG", "BA", "TO", "MT", "MS" } }, ;
      { "MA", { "PI", "TO", "PA" } }, ;
      { "MT", { "PA", "TO", "GO", "MS", "RO", "AM" } }, ;
      { "MS", { "MT", "GO", "MG", "SP", "PR" } }, ;
      { "MG", { "SP", "RJ", "ES", "BA", "GO", "MS" } }, ;
      { "PA", { "AP", "MA", "TO", "MT", "AM" } }, ;
      { "PB", { "RN", "CE", "PE" } }, ;
      { "PR", { "SP", "MS", "SC" } }, ;
      { "PE", { "PB", "CE", "PI", "BA", "AL" } }, ;
      { "PI", { "MA", "TO", "BA", "PE", "CE" } }, ;
      { "RJ", { "ES", "MG", "SP" } }, ;
      { "RN", { "PB", "CE" } }, ;
      { "RS", { "SC" } }, ;
      { "RO", { "AC", "AM", "MT" } }, ;
      { "RR", { "AM", "PA" } }, ;
      { "SC", { "PR", "RS" } }, ;
      { "SP", { "RJ", "MG", "MS", "PR" } }, ;
      { "SE", { "BA", "AL" } }, ;
      { "TO", { "MA", "PI", "BA", "GO", "MT", "PA" } } ;
   }
   LOCAL nPos

   IF pCount() == 0
      RETURN aList
   ENDIF
   nPos  := hb_ASCAN( aList, {|e| e[1] == cUF } )

   IF nPos > 0
      RETURN aList[ nPos, 2 ]
   ENDIF

   RETURN {}

Ele pega a rota pra cada UF, e vê qual a com menos UFs.
Depois repete o teste a partir dessa pras próximas UFs da lista, até acabar a lista.
Relativamente simples, apenas exige declarar/controlar direito as variáveis.