Avatar billede tango42 Nybegynder
04. januar 2008 - 13:47 Der er 13 kommentarer

Løkke tar for lang tid.

Hej Eksperten.

Jeg vil gerne lave en funktion, som undersøger samtlige kombinationer af 6 procentfordelinger (a,b,c,d,e,f), således at

a x funkt1 + b x funkt2 + c x funkt3 + d x funkt4 + e x funkt5 + f x funkt6.

bliver minds mulig. Et eksempel kunne være f.eks. være a=10%,b=25%,c=45%,d=15%,e=4%,f=1%. De 6 pct. fordelinger skal give 100% tilsammen.

Jeg har prøvet at lave 6 'for løkker', der kører fra 1-99, men der tar rigtig, rigtig lang tid. Jeg har lavet selve alt andet, mangler blot løkke-delen, som altså tar for lang tid. Nogle forlag til, hvordan man kan reducere tiden. Det skal lige nævnes

for (int intRkk=1; intRkk<=6; intRkk++)
{
  for (int a=1; a<=99; a++)
  {
    for (int b=1; b<=99; b++)
    {
        for (int c=1; c<=99; c++)
        {
          for (int d=1; d<=99; d++)
          {
              for (int e=1; e<=99; e++)
              {
              for (int f=1; f<=99; f++)
                          {
                          //Gør noget
                          }
                      }
                  }
              }
          }
    }
}
Avatar billede japping Nybegynder
04. januar 2008 - 14:01 #1
Du kan starte med at springe de ikke relevante værdier over.

  for (int a=1; a<=99; a++)
  {
    for (int b=1; b<=100-a; b++)
    {
        for (int c=1; c<=100-a-b; c++)
        {
          for (int d=1; d<=100-a-b-c; d++)
          {
              for (int e=1; e<=100-a-b-c-d; e++)
              {
              for (int f=1; f<=100-a-b-c-d-e; f++)
Avatar billede japping Nybegynder
04. januar 2008 - 14:02 #2
Jeg forstår ikke linien

for (int intRkk=1; intRkk<=6; intRkk++)

burde den  ikke være inderste led i dine løkker ?
Avatar billede Slettet bruger
04. januar 2008 - 14:06 #3
Hvis jeg har forstået dit problem korrekt står du med en instans af linær programmering.

Dit problem lyder:

Minimize a_{0}*x_{0} + ... + a_{5}*x_{0}
Subject to a_{0} + ... + a_{5} = 1, All a_{i} >= 0

Jeg vil tro at selv en standard algoritme uden optimeringer til løsning af linære problemer vil være hurtigere end dine løkker. Du kan jo evt. starte på Wiki: http://en.wikipedia.org/wiki/Linear_programming, og så google dig videre. Bemærk at din lighed: a_{0} + ... + a_{5} = 1 altid kan skrives som to uligheder:

a_{0} + ... + a_{5} <= 1

-(a_{0} + ... + a_{5}) <= -1

som påkrævet for linære problemer på standard form.
Avatar billede Slettet bruger
04. januar 2008 - 14:14 #4
Her er en implementation i C++:

http://www.cs.northwestern.edu/~agupta/_projects/optima/web/index.html

Det er inkl. en gui. Der er dog source-kode vedlagt, så hvis du ikke kan google dig til en konsolversion, kan du nok pille de relavante dele ud her...
Avatar billede Slettet bruger
04. januar 2008 - 14:20 #5
Umiddelbart vil jeg faktisk tro at du kan nøjes med Simplex.cpp og Simplex.h som kan hentes i sourcen til ovenstående.
Avatar billede Slettet bruger
04. januar 2008 - 14:24 #6
Og så skal du vist lige bytte rundt på x og a i ovenstående. x er variablen og a er konstanter. Så begrænsningerne skal lægges på x'erne og ikke a'erne, my bad!
Avatar billede tango42 Nybegynder
04. januar 2008 - 14:48 #7
Tak for de hurtige kommentarer.
Til japping: linien med rækken kan du se bort fra, den skal bruges i en anden sammenhæng. Jeg har også overvejet den mulighed, som du kommer med. Problemet er blot, at det ikke nødvendigvis er alle de 6 procentfordelinger, som skal anvendes senere i processen. Feks. kan være brug for at a + b = 100%, eller at a + e + f = 100%. Ville jeg ikke risikere at stå med f.eks. a + b = 94 % ved den metode, du nævner? 
Til Jjust. Ja, der er tale om lineær programmering. Jeg har prøvet med algoritmer, men får til tider en løsning med både positive og negative værdier. De negative værdier giver mig en forkert procentfordeling, når jeg laver dem til procent. (Jeg får negative procenter, og procenter større end 100). Men måske har jeg gjort det forkert. Siger det dig noget?
Avatar billede japping Nybegynder
04. januar 2008 - 15:38 #8
Så skal du vel bare sørge for at alle starter ved 0 og ikke 1. Slutteligt skal du kontrollere at Summer er lig med 100%, Hvis den ikke er det foretages valideringen ikke. Er den 100% kan du gemme resultatet for max/min sammenligning.
Avatar billede Slettet bruger
04. januar 2008 - 15:42 #9
Kriterierne:

sum_{i} x_{i} <= 1
sum_{i} -x_{i} <= -1
x_{i} >= 0 for alle i

Sikrer at du aldrig kan få negative løsninger eller løsninger der ikke summer til 1.
Avatar billede Slettet bruger
04. januar 2008 - 15:50 #10
Hvis du poster din opstilling af problemet på standard form skal jeg gerne se hvor det går galt.
Avatar billede tango42 Nybegynder
04. januar 2008 - 16:33 #11
Hej Jjust

Jeg tror det er her det går galt:

// koefficient-matricen løses med elimination (Gauss)
for (int intI=1; intI<=intDegree; intI++)
{
    double dblValue = dblCoef[intI][intI];
    if (dblValue == 0.0)
    {
    ShowMessage("Error: Division by 0");
    }
    for (int intJ=0; intJ<=intDegree; intJ++)
    {
        dblCoef[intI][intJ] = dblCoef[intI][intJ] / dblValue;
    }
  dblCoef[intI][intI] = 1.0;
  for (int intJ=1; intJ<=intDegree; intJ++)
  {
      if (intJ != intI)
      {
          dblValue = dblCoef[intJ][intI];
      if (dblValue != 0.0)
      {
          for (int intD=0; intD<=intDegree; intD++)
          {
              dblCoef[intJ][intD] = dblCoef[intJ][intD] -
                                        dblValue * dblCoef[intI][intD];
          }
          dblCoef[intJ][intI] = 0.0;
      }
      }
  }
}

Jeg får her nogle negative værdier til tider i dblCoef[intJ][intI], hvilket giver forkerte procenter senere.
Avatar billede Slettet bruger
04. januar 2008 - 16:46 #12
Du bliver lige nødt til at forklare mig hvad der står på indgang dblCoef[i][j] og hvad dblValue indeholder??

Den sidste for-løkke ligner noget pivotering?

Men - er det Simplex.cpp du benytter der?
Avatar billede tango42 Nybegynder
08. januar 2008 - 11:19 #13
Hej Jjust/japping.

Jeg beklager den lidt sene tilbagemelding. Men I har begge været meget hjælpsomme på hver jeres måde. Jeg har optimeret min kode i forhold til det du foreslog jjapping, hvilket reducerede tiden væsentligt. Dog var det ikke godt nok, så jeg har implementeret simplex algoritmen i stedet, som du foreslog jjust. Jeg vil gerne fordele pointene til jer begge. Så kan I ikke smide et svar begge to (og evt. lige fortælle hvordan jeg tildeler jer point hver især:-).
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester