Algorithme du voyageur de commerce

Version imprimable

Bonjour,

Je cherche à faire tourner les algorithmes suivants :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
maketsp=function(nCities)
{
    positions = 2*runif(nCities,2)-1
    distances = matrix(rep(0,(nCities*nCities),nCities,nCities)) 
    for (i in seq(nCities))
    {
        for (j in seq(i+1,nCities))
        {
            distances[i,j] = sqrt((positions[i,0] - positions[j,0])**2 + (positions[i,1] - positions[j,1])**2)
            distances[j,i] = distances[i,j]
            print (distances)
        }
    }
}

Le code d'erreur est le suivant :

Error in positions[i, 0] : incorrect number of dimensions
In addition: Warning message:
In runif(nCities, 2) : NAs produced

Je ne vois pas comment implémenter la matrice distance

Le deuxième algorithme est le suivant:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
greedy=function(distances)
{
    nCities = seq(1,distances)
    distanceTravelled = 0
 
    cityOrder = seq(0,nCities)
    cityOrder[0] = runif(nCities)
    distances[,cityOrder[0]] = Inf
 
    for ( i in seq(nCities-1))
    {
        cityOrder[i+1] = wich.min(distances[cityOrder[i],])
        distanceTravelled  = distances[cityOrder[i],cityOrder[i+1]]
        dist[,cityOrder[i+1]] = Inf
        distanceTravelled = distances[cityOrder[nCities-1],0]
        return(cityOrder)
        return(distanceTravelled)
    }
}

L'erreur est la suivante :

Error in seq.default(0, nCities) : 'to' must be of length 1

Les objets sont des matrices mais je ne sais pas comment les implémenter.

19/03/2014, 22h35
mamounMob

RTFM

Erreur1:
les indices débutent à partir de 1 pas 0 :scarymov:

Erreur2:
nCities doit être un entier, c'est pourtant dit dans le message d'erreur :massacre:

Réponse

Pour l'erreur 1, je remplace les indices 0 par des 1 :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
maketsp=function(nCities)
{
    positions = 2*runif(nCities,2)-1
    distances = matrix(rep(0,(nCities*nCities),nCities,nCities)) 
    for (i in seq(nCities))
    {
        for (j in seq(i+1,nCities))
        {
            distances[i,j] = sqrt((positions[i,1] - positions[j,1])**2 + (positions[i,1] - positions[j,1])**2)
            distances[j,i] = distances[i,j]
            print (distances)
        }
    }
}

j'obtiens l'erreur suivante :

Error in positions[i, 1] : incorrect number of dimensions
In addition: Warning message:
In runif(nCities, 2) : NAs produced

Pour l'erreur 2,j'indique nCities comme un entier :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
greedy=function(distances)
{
    nCities = 10
    distanceTravelled = 0
 
    cityOrder = seq(0,nCities)
    cityOrder[0] = runif(nCities)
    distances[,cityOrder[0]] = Inf
 
    for ( i in seq(nCities-1))
    {
        cityOrder[i+1] = wich.min(distances[cityOrder[i],])
        distanceTravelled  = distances[cityOrder[i],cityOrder[i+1]]
        dist[,cityOrder[i+1]] = Inf
        distanceTravelled = distances[cityOrder[nCities-1],0]
        return(cityOrder)
        return(distanceTravelled)
    }
}

j'obtiens l'erreur suivante :

Error in distances[, cityOrder[0]] = Inf : 
  incorrect number of subscripts on matrix

02/04/2014, 18h21
A. D.

Bonjour,

Je ne me suis pas penchée en détails sur votre code mais je pense déjà qu'un des problèmes vient du fait que l'élément "positions" est un vecteur et non une matrice, donc pour accéder à l'élément i de "positions" au sein de votre fonction, il faudrait plutôt faire : positions[i].

Ensuite, il y a clairement un problème avec votre utilisation de la fonction "runif". Je pense que vous devriez vérifier si les paramètres passés à cette fonction sont conformes. Pour info, pour accéder à l'aide de cette fonction : ?runif.

En espérant que cela vous aide un peu, bonne continuation ! :)

Cordialement,

A.D.