Dynaaminen ongelma (algoritmit) - Dynamic problem (algorithms)

Ei pidä sekoittaa dynaamiseen ohjelmointiin .

Dynaaminen ongelmia on laskennan vaativuus ongelmia ilmaistu muuttuvan syöttödatan. Yleisimmässä muodossa tämän luokan ongelma todetaan yleensä seuraavasti:

  • Kun kyseessä on tuloobjektien luokka, etsi tehokkaita algoritmeja ja tietorakenteita vastaamaan tiettyyn kyselyyn syöttöobjektien joukosta joka kerta, kun syöttötietoja muokataan, ts. Objekteja lisätään tai poistetaan.

Tämän luokan ongelmilla on seuraavat monimutkaisuusmitat:

  • Tila  - tietorakenteen tallentamiseksi tarvittava muistitila ;
  • Alustusaika  - aika, joka tarvitaan tietorakenteen alustavaan rakentamiseen;
  • Lisäysaika  - aika, joka tarvitaan tietorakenteen päivittämiseen, kun yksi lisäsyöttöelementti lisätään;
  • Poistoaika  - aika, joka tarvitaan tietorakenteen päivittämiseen, kun syöttöelementti poistetaan.
  • Kyselyaika  - kyselyyn vastaamiseen tarvittava aika;
  • Muut kyseiseen ongelmaan liittyvät toiminnot

Dynaamisen ongelman kokonaista laskentajoukkoa kutsutaan dynaamiseksi algoritmiksi .

Monilla algoritmisilla ongelmilla, jotka ilmaistaan ​​kiinteän tulotiedon perusteella (joita tässä yhteydessä kutsutaan staattisiksi ongelmiksi ja jotka on ratkaistu staattisilla algoritmeilla ), on merkityksellisiä dynaamisia versioita.

Erikoistapaukset

Inkrementaaliset algoritmit tai online-algoritmit ovat algoritmeja, joissa sallitaan vain elementtien lisäykset, mahdollisesti alkaen tyhjästä / triviaalisesta syöttötiedosta.

Vähennysalgoritmit ovat algoritmeja, joissa vain elementtien poistot ovat sallittuja, alkaen täydellisen tietorakenteen alustamisesta.

Jos sekä lisäykset että poistot ovat sallittuja, algoritmia kutsutaan joskus täysin dynaamiseksi .

esimerkit

Suurin elementti

Staattinen ongelma 
Löydä N-numerosarjasta suurin.

Ongelma voidaan ratkaista O (N) -jaksossa.

Dynaaminen ongelma 
Alkuperäisen N-numerosarjan osalta ylläpitä dynaamisesti maksiminumero, kun lisäys ja poistot ovat sallittuja.

Tunnettu ratkaisu tähän ongelmaan on itsetasapainottavan binaarisen hakupuun käyttäminen . Se vie tilaa O (N), voidaan alun perin konstruoida ajassa O (N log N) ja tarjoaa lisäys-, poisto- ja kyselyajat O: ssa (log N).

Prioriteettijono ylläpito ongelma
Se on yksinkertaistettu versio tästä dynaamisesta ongelmasta, jossa vaaditaan vain suurimman elementin poistaminen. Tämä versio voi liittyä yksinkertaisempiin tietorakenteisiin.

Käyrät

Pidä annetussa kuvaajassa sen parametrit, kuten yhteydet, maksimitaso, lyhyimmät reitit jne., Kun sen reunojen lisääminen ja poistaminen on sallittua.

Katso myös

Viitteet

  1. ^ D. Eppstein , Z. Galil ja GF Italiano . Msgstr "Dynaamiset graafiset algoritmit". In CRC Handbook of algoritmit ja Laskennan teoria , 22 luvun CRC Press, 1997.