Problema do Caixeiro Viajante

[JOAOBERNARD070 0]

Boa tarde malta, queria vos pedir se me pediam ajudar neste problema, n percebo como vou conseguir definir este código. 

Se pudessem ajudar agradecia vos

[thoga31 579]

Tens dúvidas na escolha do algoritmo, na sua implementação ou na representação dos dados?

[JOAOBERNARD070 0]

É na escolha do algoritmo, já tenho os dados e as localidades

 

distancias = [
    [0, 394,126, 272, 199, 63, 350, 494, 160, 117, 253, 234, 76, 188, 289, 149, 160, 87], #Aveiro
    [389, 0, 498, 541, 274, 338, 81, 147, 366, 272, 177, 182, 444, 205, 144, 521, 520, 425], # Beja
    [126, 505, 0, 217, 309, 174, 415, 604, 251, 234, 363, 344, 57, 298, 400, 54, 105, 178], # Braga
    [272, 543, 217, 0, 273, 289, 462, 726, 178, 356, 485, 362, 210, 420, 521, 280, 120, 200], # Bragança
    [274, 275, 307, 272, 0, 137, 189, 433, 97, 166, 224, 85, 257, 159, 244, 320, 243, 150], # Castelo Branco
    [63, 344, 171, 287, 138, 0, 244, 444, 167, 74, 203, 172, 122, 137, 239, 195, 187, 92], # Coimbra
    [344, 81, 414, 462, 192, 293, 0, 226, 286, 226, 132, 103, 364, 121, 99, 437, 475, 361], # Évora
    [390, 147, 599, 721, 432, 440, 226, 0, 524, 373, 278, 379, 549, 306, 245, 622, 621, 526], # Faro
    [163, 364, 254, 182, 95, 157, 283, 522, 0, 241, 313, 184, 204, 248, 349, 278, 152, 80], # Guarda
    [118, 273, 233, 355, 166, 73, 229, 386, 235, 0, 131, 171, 183, 80, 180, 256, 255, 160], # Leiria
    [254, 178, 364, 486, 225, 204, 134, 278, 317, 134, 0, 200, 314, 83, 49, 387, 386, 291], # Lisboa
    [233, 183, 341, 362, 85, 172, 103, 378, 187, 172, 198, 0, 292, 137, 194, 365, 358, 260], # Portalegre
    [74, 446, 55, 207, 259, 124, 365, 554, 201, 184, 313, 294, 0, 248, 350, 75, 95, 128], # Porto
    [186, 207, 295, 417, 156, 136, 123, 307, 248, 79, 80, 137, 245, 0, 116, 318, 317, 222], # Santarém
    [290, 145, 399, 521, 260, 239, 100, 244, 352, 182, 50, 194, 349, 118, 0, 422, 421, 326], # Setúbal
    [149, 521, 54, 280, 320, 195, 437, 622, 278, 256, 387, 365, 75, 318, 422, 0, 200, 200], # Viana do Castelo
    [160, 520, 105, 120, 243, 187, 475, 621, 152, 255, 386, 358, 95, 317, 421,200, 0, 98], # Vila Real
    [86, 431, 176, 198, 152, 93, 360, 531, 76, 160, 290, 260, 127, 224, 326, 200, 98, 0]] #Viseu

cidades = ["Aveiro", "Beja", "Braga", "Bragança", "Castelo Branco", "Coimbra", "Évora", "Faro", "Guarda", "Leiria", "Lisboa", "Portalegre", "Porto"]

Edited January 16 by JOAOBERNARD070
Correção de palavra

[thoga31 579]

Podes usar programação dinâmica, por exemplo, uma vez que não são muitos dados. É um algoritmo mais fácil de entender e que obtém uma performance satisfatória.

[JOAOBERNARD070 0]

Podes me dar o exemplo do codigo q j´atei isso e não consigo

[thoga31 579]

Mostra o código que já tentaste.

[JOAOBERNARD070 0]

Tnetei mas já apaguei, n sei por onde começar 

[thoga31 579]

Ninguém vai dar código, até porque, mesmo que não consideremos mais nenhum motivo, vai contra as Regras do Fórum (2.2). Podemos dar dicas e esclarecer dúvidas concretas, mas dar um código feito não.

Já agora, sugiro não apagar todo um código mesmo que não se esteja a conseguir chegar ao resultado final. Podia ter uma ideia com esse código da tua forma de pensar e poderia começar a dar dicas com base nele. Além disso, não deixa de ser um bom ponto de aprendizagem comparar os códigos errados que fizemos com os novos que funcionam.

Posto isto, que dúvidas específicas tens?

[JOAOBERNARD070 0]

Como definir o caminho
Como escolher o minimo de cada array sendo q existe um 0