Keskustelu: Nettisivujen teko: Algoritmi reaktion tasapainotukseen

Eli aioin tehdä ohjelman, joka tasapainottaisi annetun reaktioyhtälön. Sain jo tehtyä ohjelmaan sen, että se katsoo siitä reaktio yhtälöistä, että montako on mitäkin alkuainetta eri aineissa. Enää pitäisi saada määriteltyä ne kertoimet, että olisi yhtä monta alkuainetta molemmilla puolilla.

Esimerkki reaktio: H2O + CO2 --> C6H12O6 + O2

Ajattelin käyttää yhtä taulukkoa, jossa on alkioina taulukot eri alkuaineiden määrät. Eli näin:

array(4) {
  [0]=>
  array(2) {
    ["H"]=>
    int(2)
    ["O"]=>
    int(1)
  }
  [1]=>
  array(2) {
    ["C"]=>
    int(1)
    ["O"]=>
    int(2)
  }
  [2]=>
  array(3) {
    ["C"]=>
    int(6)
    ["H"]=>
    int(12)
    ["O"]=>
    int(6)
  }
  [3]=>
  array(1) {
    ["O"]=>
    int(2)
  }
}

Ongelma on oikeastaan siinä, että ohjelman pitää kyetä tasapainottamaan mikä tahansa reaktioyhtälö, eli eri aineita on siis n määrä. Mitään bruteforcea tuskin kannattaa käyttää. :P

Tuostahan saisi tehtyä ikään kuin yhtälö ryhmän, mutta tuossa tapauksessa siihen tulee neljä muuttujaa, ja kolme yhtälöä. Tämä johtuu tietysti siitä, että tuosta voidaan ratkaista oikeastaan vain aineiden väliset suhteet. Yleensä siitä kuitenkin ilmoitetaan pienimmät mahdolliset kokonaisluvut.

Onko mitään ideoita?

Kyseessä on lineaarinen Diofantoksen yhtälö. Tälle on olemassa nopea ratkaisualgoritmi nimeltä Eukleideen algoritmi. Kutsut sitä tarpeeksi monta kertaa, jolloin saat aina lineaarisen Diofantoksen yhtälön, jossa on yksi tuntematon vähemmän kuin edellisessä yhtälössä. Algoritmi palauttaa myös kahden tuntemattoman tapauksessa ratkaisun.

(Samanlainen tehtävä oli kuulemma Datatähden alkukilpailussa 1999)

Yksi joissain tapauksissa toimiva vaihtoehto on reaktioyhtälön tasapainotus hapetuslukujen avulla, tosin tämä toimii vain jos reaktioyhtälössä on tarpeeksi sellaisia aineita, joiden hapetusluvut on selvitettävissä (I ja II pääryhmän aineet yms), jolloin voi käyttää kaavaa, jonka mukaan hapetuslukujen muutosten summan tulee olla yhtä suuria molemmilla puolilla reaktioyhtälöä.

Jos yhtälöitä on yhtälöryhmässä vähemmän kuin muuttujia, homma onnistuisi varmaan ratkaisemalla osa yhtälöistä Diofantoksen yhtälöinä.

Edit. hidas

Ratkaisu onnistuu kyllä yhtälöryhmän avulla. Kun tuntemattomia on liikaa, yhden muuttujan voi valita itse (esim. ensimmäinen kerroin on aina 1). Sitten kaikki kertoimet pitää vielä kertoa sopivalla luvulla niin, että tuloksena on kokonaislukukertoimet.

Luulenpa, että jopa kaikkien vaihtoehtojen kokeilu riittäisi useimmissa tapauksissa.

Hapetuslukuja en tähän sotkisi, jos aineet ovat varauksettomia, koska niiden laskeminen ei ole helppoa.

C3H6 + 6O2 + H2 + C ==> 4CO2 + 4H2O

Tuon tasapainottamiseen algoritmi kutsuu funkiotaan rekursiivisesti 7908 kertaa :/

Ja tuo on hieman optimoitu versio, alkuperäinen kutsui 82206 kertaa. Ongelmia tulee etenkin silloin, kun alkuaineita on monia.

Optimoimaton:

maks=1 | 0 | 7
maks=2 | 0 | 134
maks=3 | 0.01 | 1227
maks=4 | 0.1 | 6688
maks=5 | 0.57 | 26219
maks=6 | 2.16 | 82206

Optimoitu:

maks=1 | 0 | 7
maks=2 | 0 | 80
maks=3 | 0.01 | 489
maks=4 | 0.06 | 1990
maks=5 | 0.27 | 622
maks=6 | 0.75 | 7908

maks tarkoittaa, että mihin kertoimeen asti etsitään. Tuossa tarvittiin siis happeen kerroin kuusi, joten siihen asti piti etsiä. toinen luku on suoritusaika sekunteina, kolmas luku on funktion kutsukerrat.

Onhan tuo optimoitu yli 90% nopeampi, mutta algoritmi on vieläkin sangen tehoton...

Luulisi, että jollakin on tiedossa joku parempi algoritmi. Tuo optimoimaton käy siis kertoimia läpi näin:

1 1 1 1 1 1
1 1 1 1 1 2
1 1 1 1 2 1
1 1 1 1 2 2
1 1 1 2 1 1

jne... kunnes maks=2 on käyty läpi. Sitten käydään kaikki kolmoseen asti läpi..

Eukleideen algoritmit pitäisi olla huomattavasti nopeampi.

Samoin yhtälöryhmän. Jos ehdin nyt illalla, voisin koettaa tehdä tuollaista ohjelmaa...

Niin yhtälöryhmä... se olikin jossain välissä mielessä. Sitten kuitenkin ajattelin, että kun tulee desimaalilukuja, ettei se onnistuisi, mutta onnistuuhan se (kun ratkaisua ei haeta tuolla tavalla kokeilemalla). Voi tietty olla vähän ongelmaa tehdä ohjelma, joka ratkaisee sen yhtälöparin, mutta ainakin se olisi erittäin nopea.

Pitää huomenna ruveta pakertamaan sitä sitten.

Joskus tein C-harkkana tollasen matriiseja ja Gaussin menetelmää käyttävän yhtälöryhmälaskijan. Ei varmaan erityisen nopea, mutta noinkin sen voi tehdä: http://blaze.dyndns.ws:8080/~blaze/gauss.c

Yhtälöryhmän käyttö ei sittenkään taida olla mutkatonta. Ainakin tuossa uudemmassa yhtälössä eri alkuaineita on vain kolme, kun taas aineiden määrä on kuusi. Näin saadaan yhtälöryhmä, jossa on kolme yhtälöä ja kuusi tuntematonta!

3a + b = c    (hiili)
6a + 2d = 2e  (vety)
2f = 2c + e   (happi)

Nyt yhden muuttujan määrittäminen ykköseksi ei enää riitä.

Kuinka ratkaisu Diofantoksen yhtälöllä tarkalleen ottaen tapahtuisi?

Hmm... no periaatteessa mikä tahansa ratkaisu tuolle yhtälöryhmälle riittäisi. Pitäisi vain jotenkin päätyä siihen "ensimmäiseen" ratkaisuun, eli että esim. a+b+c+d+e on mahd. pieni.

Suoraan sanottuna en ole koskaan kokeillut soveltaa Eukleideen algoritmia kemiaan. Ideani on kuitenkin seuraava: Tehdään alkuaineista ja varauksista niin monta yhtälöä kuin saadaan. Käsitellään yhtälöitä yksi kerrallaan ja etsitään yhtälölle yleinen ratkaisu. Sijoitetaan tämä ratkaisu seuraavaan yhtälöön ja käytetään taas algoritmia. Iteroidaan tätä.

Lopulta eri alkuaineiden suhteita kuvaa yhtälöt, joissa esiintyy vapaita muuttujia. Näille voi sitten antaa sopivat arvot, jolloin kaikkia alkuaineita tulee yhtälöön positiivinen määrä.

Olen kyllä itse liian laiska tasapainottamaan yhtälöitä koodaamalla tai käsin. Symbolisella matikkaohjelmistolla pärjään hyvin.