1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
|
IEnumerable<List<Mine>> Inserer( double p, Mine mine, List<Mine> chemin )
{
Mine courante = null, precedente = null;
// Insertion des mines avant chacune de celles de la séquence
for ( int i = 0 ; i < chemin.Count ; i++ )
{
courante = chemin[i];
// C'est après la précédente (s'il y en a une) et que l'insertion après celle ci est optimale
// et avant la mine courante si l'insertion avant celle ci est optimale
// Note :
// Les limites sont testées sur "un intervalle semi ouvert" :
// t(precedente, mine) <= t(mine, precedente) et t(mine, courante) < t(courante, mine)
// Sinon, on génère une combinatoire importante si plusieurs mines sont identiques
if ( (precedente == null || Optim( precedente, mine, p - precedente.Production ) <= 0) && Optim( mine, courante, p ) < 0 )
{
// Récupération de toutes les mines arpès la mine courante (et y compris celle ci)
List<Mine> mines = new List<Mine>( chemin.Skip( i ) );
// Pour chaque sous chemins optimaux constitué de ces mines avec la production après la mine insérée
foreach ( List<Mine> sousChemin in Traiter( p + mine.Production, mines ) )
{
// Si la concaténation du chemin avant et du sous chemin est optimale
if ( Optim( mine, sousChemin[0], p ) <= 0 )
{
// Constitution du chemin complet constitué...
// ...de toutes les mines avant...
List<Mine> resultat = new List<Mine>( chemin.Take( i ) );
// ...de la mine en cours...
resultat.Add( mine );
// ...et du sous chemin
resultat.AddRange( sousChemin );
yield return resultat;
}
}
}
p += courante.Production;
precedente = courante;
}
// enfin ajout de la mine en dernier, si cela est optimal
if ( precedente == null || Optim( precedente, mine, p - precedente.Production ) <= 0 )
{
List<Mine> resultat = new List<Mine>( chemin );
resultat.Add( mine );
yield return resultat;
}
} |
Partager