2

Olá, estou testando umas ideias, fazendo uns programas em python 3, e preciso de ajuda com uma coisa complicada na qual não entendo nada, nem consigo bolar qualquer solução minimamente viável. para resumir, preciso criar uma função que receberá 3 parâmetros (ainda a serem comentados), e me retorne a menor rota possível entre dois terrenos.

para entender melhor o funcionamento que essa função deverá ter, demostrarei com uma imagem. a imagem abaixo.

inserir a descrição da imagem aqui

como podemos ver, a imagem é composta de Bolinhas e segmentos de retas, pense em cada bolinha como um terreno, cada uma possui um código único (ID por assim dizer) para ser identificado, esse código é uma string, pode ser uma letra, nome, seja lá o que for, só devemos observar que não pode conter ponto. ou barra/ e será um código único para cada terreno, não podendo por tanto, ter dois terrenos com o mesmo código.

os terrenos por sua vez, são ligados por segmentos de retas, pensem nelas como estradas, logo podemos pensar em rotas também. e é isso que preciso, preciso de uma função que irei fornecer uma listra como primeiro parâmetro, essa listra será uma espécie de mapa, fornecerei o ponto de saída como segundo parâmetro, e o destino como terceiro parâmetro, ela deve retornar uma string com a rota do ponto de saída, até o ponto de chegada, dai a necessidade do primeiro parâmetro, como o mapa pode se alterar, sempre forneceremos para a função calculadora de rotas, o mapa atualizado para ela poder formar e retornar a menor rota possível.

o primeiro parâmetro que ela receberá será uma listra cheia de string que identificam um segmento de rota, uma string que identifica um segmento de rotas é montada da seguinte maneira "ID1.ID2" o ponto é depois usado para separar o ID1 do ID2 com o método .split(), ambos os ID(s) no caso são identificadores de terrenos, antes mencionados, veja por exemplo na imagem, o terreno W está ligado ao terreno D, uma string que represente isso nesse caso seria "W.D", a tal listra nada mais é do que isso, ela possui varias strings dentro que identificam as rotas e os pontos juntos, uma listra que serviria de parâmetro para essa função, baseada na imagem acima ficaria da seguinte forma:

["O.H", "H.R", "E.Q", "G.A", "A.L", "K.A", "B.C", W.D, "J.I", "J.P", "M.E", etc etc etc...] é um resumo do mapa de maneira geral

ela deve inicialmente entender que existe os terrenos, ela então devera extrai-los da listra que recebera como parametro 1, ou seja, no caso do mapa acima, saber que existe os pontos A, B, C, D, E, F, G, H... as vezes eles aparecem mais de uma vez nas listra, pois por exemplo, na foto acima, é possivel ver que o ponto E se liga a mais de um terreno, então ele aparecerá mais de uma vez na listra ["E.H", "E.Q", "E.M", etc etc etc] quando visto pela primeira vez, a função pode por assim dizer, "registrar ele" e se visto depois, pode ignorar enquanto faz a primeira varredura, isso depende também de como ela procede, pode ser de outra forma, o que queremos de fato é, passar uma listra que será da forma descrita acima, esse parâmetro pode ser chamado de Map, irei depois passar duas strings/parâmetros que serão o ponto de saída e destino. vamos considerar a foto acima, supomos que devemos partir do ponto A e devemos chegar no ponto E pela menor rota possível, passamos o ponto de saída, o destino e o Map para a função, nesse caso deverá retornar a string "A.E" que representa, traduzindo para termos lógicos: iniciamos em A, movemos de A para E, fim. ela retorna a menor rota possível, agora supomos que queiramos sair de A e chegar no ponto S, a função devera nos retornar a string "A.E.Q.S" que significa: iniciamos em A, movemos de A para E, movemos de E para Q, movemos de Q para S, fim. nota, apesar de visualmente ter segmentos maiores que outros, a menor rota possível considera somente o numero de terrenos que tivermos de cruzar, se sairmos de A para D, o menor caminho seria "A.E.H.D", embora também possa existir o caminho "A.E.Q.S.U.D", ele é mais longo, portanto, inútil.

outra observação, é que haverá raras situações em que ele poderá identificar duas ou mais rotas diferentes porem com igual distancia, a função então terá de arbitrar escolhendo uma das rotas para retornar, porem não pode ser uma escolha ao acaso, imaginem um caso em um mapa no qual se sai de um ponto fictício P para um ponto fictício C, a função chega a duas menores rotas possíveis como conclusão, a rota ["P.Q.E.C"] e ["P.Q.F.C"] quando eu realizar o calculo chamando a função N vezes, todas as vezes terá de retornar a mesma rota, senão, hora no mapa será desenhada uma rota, hora será desenhada outra rota entre os terrenos, ficaria estranho, não sei ao certo como ficaria para arbitrar entre ambas as rotas, mais poderia ser feito por algum calculo, ou ordem alfabética. o primeiro e o ultimo ponto em ambas as rotas são iguais, mais os outros não, enfim, enquanto estiver sendo fornecido um mesmo mapa para a função, ela nesses casos deverá retornar a mesma resposta sempre.

gostaria de um exemplo de código, se possível, mas mais do que isso, uma explicação de como funciona esse sistema de calcular a menor rota possível. com uma função desse tipo, consigo até variar outras funções como obter uma distancia em números de segmentos de um ponto A ate B, é muitas coisas mais, se entende-la a fundo, posso fazer o inverso, criar uma função que retorna a maior rota possível ou o número de possíveis rotas distintas de ponto A ate B, interessante.

Não me considero um iniciante mais não sou profissional, consegui até fazer um bom sistema de inventario dinâmico, istanciavel com capacidade de transferência de item de um inventario a outro, mais garrei aqui, se está lendo até aqui, obrigado pela atenção.

3
  • é parecido com isso aqui, pt.stackoverflow.com/questions/426570/… Commented 31/01/2021 às 22:52
  • sim, é praticamente a mesma coisa, obrigado, vou ver isso mais a fundo e ver se consigo bolar uma solução inspirado nisso. Commented 31/01/2021 às 23:00
  • analisei o código que me mandou e fiz aqui, funciona quase certinho, é só fazer umas correções e funcionará adequadamente. obrigado. vou deixar o código abaixo para caso outras pessoas se interessem. Commented 1/02/2021 às 11:28

1 Resposta 1

1
mapa = {
     "1":"2345",
     "2":"134",
     "3":"124",
     "4":"123",
     "5":"1697",
     "6":"5g",
     "7":"508",
     "8":"07",
     "9":"5",
     "0":"87",
     "a":"bc",
     "b":"ac",
     "c":"abdg",
     "d":"ecf",
     "e":"d",
     "f":"d",
     "g":"6c",
     "h":"ij",
     "i":"hj",
     "j":"hik",
     "k":"j"}


def procurar(saida, destino, mapa):
    if len(saida) != len(set(saida)): return

    if saida[-1] == destino:
        print(saida)
        return 

    for i in mapa[saida[-1]]:
        procurar(saida+i, destino, mapa)

while True:   
     print()
     opc1 = input("--> saida: ")
     opc2 = input("--> destino:")
     print()

    if procurar(opc1, opc2, mapa) == None:
        print("erro, caminho não achado")

    else:
        print("SUCESSO")

não consegui por o código todo bonitinho aqui, alguém no futuro se quiser, pode editar isso a vontade, obrigado a ajuda.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .