Chcem napísať rutinu Java, ktorá kontroluje, či je systém lineárnych rovníc uskutočniteľný alebo nie. Mám viac premenných ako rovníc, takže systém je nedostatočne určený.
Existuje na to nejaký štandardný algoritmus? A ak áno, aká je jeho časová zložitosť?
odpovede:
1 pre odpoveď č. 1Verím, že to, čo hľadáte (napísať aj úplného riešiteľa), by bolo Gaussova eliminácia, Len na kontrolu, či je to riešiteľnéMyslíte si, že môžete skontrolovať, či máte aspoň toľko lineárne nezávislých rovníc, aké existujú pre premenné (lineárna nezávislosť v podstate znamená, že vektory vytvorené z koeficientov rovníc nie sú rovnobežné). Pre video s vysvetlením lineárnej nezávislosti a prechodu príkladom Gaussovej eliminácie, pozri tu.
Pokiaľ ide o časovú zložitosť, odvrátim vašu pozornosť tejto diskusii, aj keď pochybujem, že to bude mať najmenší zmysel, až kým sa neoboznámite s procesom Gaussovej eliminácie.
Ospravedlňujem sa za nedostatok informácií týkajúcich sa jazyka Java, skôr som chlapík z C ++ a väčšinou vás len poukazujem na to, ako si hodiť svoj vlastný.
1 pre odpoveď č. 2
To, čo hľadáte, sa nazýva simplexná metóda, Stačí spustiť lineárny programovací riešiteľ (Lineárne programovacie nástroje / knižnice pre Javu) na váš problém nastavením objektívnej funkcie na nulu (alebo akúkoľvek inú ľubovoľnú konštantu).
Očakávaná časová zložitosť je polynóm. Najhoršia zložitosť je síce exponenciálna, ale je veľmi veľmi vzácny; sú známe iba umelé príklady.