[Algo-Prog C] Un ptit algo que je n'arrive pas à trouver[2,5 ans+tard]

Recherche :

Dernière réponse

Sujet : [Algo-Prog C] Un ptit algo que je n'arrive pas à trouver[2,5 ans+tard]

Giz

JagStang a écrit :

j'ai un algo en C qui implémente 3 heuristiques pour tenter la résolution de ce problème.

intéressé ? je l'ai pas sous la main, je dois fouiller

dit moi juste à quoi elles ressemblent en gros. J'en connais kk1 d'après google ;) mais juste pour savoir si les tiennes je les connais. ;)

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

Giz

JagStang a écrit :

j'ai un algo en C qui implémente 3 heuristiques pour tenter la résolution de ce problème.

intéressé ? je l'ai pas sous la main, je dois fouiller

dit moi juste à quoi elles ressemblent en gros. J'en connais kk1 d'après google ;) mais juste pour savoir si les tiennes je les connais. ;)

jagstang

j'ai un algo en C qui implémente 3 heuristiques pour tenter la résolution de ce problème.

intéressé ? je l'ai pas sous la main, je dois fouiller

Giz

Jubijub a écrit :

et sa variante le problème du postier (plus les noeuds mais les branches)...

mais si tu augmentes les noeuds il devient vite insoluble ce truc (enfin dans des limites de temps acceptables)?

:jap: ... le nombre de chemins différents dans un probleme du PVC avec n villes est :

(n-1)! / 2 ... ce qui commence a faire avec n > 10 :D

Jubijub

et sa variante le problème du postier (plus les noeuds mais les branches)...

mais si tu augmentes les noeuds il devient vite insoluble ce truc (enfin dans des limites de temps acceptables)?

Giz

noldor a écrit :

PVC ? kézako ?

PVC = probleme du voyageur de commerce = TSP = travelling salesman problem ;)

Jubijub

ca c du déterrage de topic ;)

noldor

Giz a écrit :

Me revoila 2 ans et demi plus tard, toujours dans l'info. T1 ce que g t nul avant :D.
Y'a pas plus facile comme pb ! ... et dire que l'algo de chrisbk ne marche pas faut vraiment etre benet! :lol:
Effectivement j'ai l'impression d'avoir progresse depuis ;)
Surtout que maintenant je m'interesse au pb du PVC :love:

PS : chrisbk , tu e t vraiment gentil de ne pas m'avoir envoyer en l'air.

PVC ? kézako ?

Giz

chrisbk

regarde :
1er tri
val = 30,5,10,15,20
indice = 2,1,0,3,4

2eme tri
val = 30,20,10,15,5
indice = 2,4,0,3,1

3eme tri
val = 30,20,15,10,5
indice = 2,4,3,0,1

dans le tableau original
original[2] = 30;
original[4] = 20;
original[3] = 15;
original[0] = 10;
original[1] = 5;

ca colle non ?

chrisbk

j'ai du mal a comprendre comment indiceTab pourra contenir deux fois 4

Giz	Non, déroule le à la main en récupérant les 3 plus grand nombre du tab suivant: tab={10,5,30,15,20} puis ton indicetab={0,1,2,3,4}(au départ) je te demande juste de récupérer les 3 1ere case du tableau indicetab ca te renverra 2,4,4!...(les 3 1ere valeur) au lieu de 2,4,3...

chrisbk

Giz a écrit a écrit :

ckrisbk ton algo ne marche pas!

Une otre proposition ?

mon algo marche, j'en suis certain :p

tgrx

Basé sur l'algo de chrisbk, mais sans le tableau d'indices (mais avec un tableau d'entiers ce qui revient au même en complexité mémoire).

Code :

#include <limits.h> // ou un truc du style, je sais plus très bien
int tab[10], tmptab[10], indices[5];
for (int i=0;i<10;i++) tmptab[i]=tab[i]; // simple recopie
for (int i=0;i<5;i++)
{
int max=INT_MIN, indice;
for (int j=0;j<10;j++)
if (tmptab[j]>=max) indice=j;
tmptab[j]=INT_MIN;
indices[i]=j;
}

La complexité est en O(nm), où m est la taille du tableau d'indices à déterminer.

Donc si m=n/2 dans le cas général, tu as du O(n²), si m reste fixé à 5, c'est du O(n)

:hello:

Giz	ckrisbk ton algo ne marche pas! Une otre proposition ?

Giz	Ca j'avais compris...surtout avec mon Tbird 1.4GHz ! :lol: Mais je parle avec n élément!

chrisbk

sur un truc de 10elements tu peux optimiser ca comme tu veux tu verras pas la difference :D

Giz	Sinon nivo optimization (rapidité) c bien adapté ?

Giz

chrisbk a écrit a écrit :

tu tri en parrallele
je veux dire, tu inverse deux val dans ton tableau "tab", tu inverse les meme val (enfin les val se situant au meme indice) dans le tableau indiceTab

a la fin du traitemnt tu as dans indiceTab les indices des plus grand chiffre du tableau par ordre decroissant (ou croissant, depend de comment tu fais ton tri)

enfin, ces indices s'appliquent au tableau original "tab" non trie

Ok je crois avoir compris...ton tableau de départ tu le parcours , tu y repère le plus grand tu échanges le plus gd nombre avec le 1er élément ds ton Tab de départ...et les cases que t'échange ds dans tab, tu echanges les meme cases ds ton indicetab
exemple: on échange la case 1 et 3 de tab, on change dc les cases 1 et 3 d'indicetab
puis on récupère les cinq valeurs des 5 cases d'indicetab...ok
c ca a peu près ?

[edtdd]--Message édité par Giz--[/edtdd]

chrisbk

Giz a écrit a écrit :

Ok...ton IndiceTab[10] sera = à : {0,1,2,3,4,5,6,7,8,9}

ensuite si je tri mon tableau de départ par ordre croissant, je PERD tout mes indices!...je ne vois pas comment tu fais.

tu tri en parrallele
je veux dire, tu inverse deux val dans ton tableau "tab", tu inverse les meme val (enfin les val se situant au meme indice) dans le tableau indiceTab

a la fin du traitemnt tu as dans indiceTab les indices des plus grand chiffre du tableau par ordre decroissant (ou croissant, depend de comment tu fais ton tri)

enfin, ces indices s'appliquent au tableau original "tab" non trie

Giz

chrisbk a écrit a écrit :

tu te fais un tableau annexe :

int indiceTab[10];

for (int i=0;i<10;i++)
indiceTab[i] = i;

ca c la phase 1

ensuite tu tri ton tableau tab, mais lors de tri quand tu change un element de place tu modifie aussi le tableau indiceTab

par ex :

int tab[10]={10,5,30,15,20,4,51,34,3,1}

mettons apres un debut de tri tu auras :
int tab[10]={30,5,10,15,20,4,51,34,3,1}

alors indiceTab doit etre :
{2,1,0,3,4,5,6,7,8,9}

et vala a fin du tri t'as plus qu'a rechope les 5 premieres entree de indiceTab

Ok...ton IndiceTab[10] sera = à : {0,1,2,3,4,5,6,7,8,9}

ensuite si je tri mon tableau de départ par ordre croissant, je PERD tout mes indices!...je ne vois pas comment tu fais.

chrisbk

encore que je complique la vie moi

Code :

int itab[5];
for (int i=0;i<5;i++)
{
int max = 0;
int indice = -1;
for (int j=0;j<10;j++)
{
if (tab[j] >= max)
{
for (int l=0;l<i;l++)
if (j==itab[l])
break; //pas inserer deux fois le meme indice
if (l == i)
{
max = tab[j];
indice = j;
}
}
itab[i] = indice;
}

[edtdd]--Message édité par chrisbk--[/edtdd]

chrisbk

tu te fais un tableau annexe :

int indiceTab[10];

for (int i=0;i<10;i++)
indiceTab[i] = i;

ca c la phase 1

ensuite tu tri ton tableau tab, mais lors de tri quand tu change un element de place tu modifie aussi le tableau indiceTab

par ex :

int tab[10]={10,5,30,15,20,4,51,34,3,1}

mettons apres un debut de tri tu auras :
int tab[10]={30,5,10,15,20,4,51,34,3,1}

alors indiceTab doit etre :
{2,1,0,3,4,5,6,7,8,9}

et vala a fin du tri t'as plus qu'a rechope les 5 premieres entree de indiceTab

Giz	Vous pouvez tjs proposez vos solutions directement en C...

Giz

Voilà je mi suis pris assez la tête comme ça dc je donne ma langue au chat ;)
l'algo consiste à trouver les 5 indices (d'un tableau de dix éléments) correspondant aux 5 plus grandes valeurs dans le tableau et mettre c indices dans un autre tableau contenant donc ces 5 indices (le premier élément de cet autre tableau contient l'indice du tableau de départ correspondant au plus grand nombre...le dernier element de cet autre tableau contient l'indice correspondant au cinquième plus grand nombre du tableau de départ.

Exemple:

Tableau de départ int tab[10]={10,5,30,15,20,4,51,34,3,1}
Les cinq nombres les plus grand sont: 51,34,30,20,15 et ont respectivement pour indice (en C): 6,7,2,4,3

L'autre tableau: il contiendra DANS L'ORDRE: int tab[5]={6,7,2,4,3} cad les indices du tableau de départ correspond aux cinq plus grand nombre.

Je pense avoir été suffisamment clair sinon posez vos questions...Moi je mi suis pris la tête et jsuis sûr que c qu'un ptit truc bête qui me repousse (comme tjs).
Proposez vos solutions, Merci.