Ero sivun ”Graafi” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
Ei muokkausyhteenvetoa |
|||
Rivi 15:
Graafeja ja niihin liittyviä algoritmeja käytetään varsin monissa erilaisissa sovellutuksissa. Esimerkkeinä mainittakoon vaikkapa lyhimmän tai ylipäätään reitin etsiminen ja riippuvuussuhteiden esittäminen sopivassa järjestyksessä (ks. [[topologinen lajittelu]]). Ylipäätään minkä hyvänsä ongelman ratkaisu, missä tiedetään alkutila, sallitut seuraajatilat ja tavoitetila (mutta ei suoraan miten sinne päästään), voidaan ainakin periaatteessa tuottaa graafialgoritmeilla.
== Esimerkkejä ==
Rivi 30 ⟶ 31:
Graafista näkee esim. sen, että Helsingistä pääsee suoraan Turkuun, mutta että Jyväskylästä
ja Oulusta pitää mennä aina Turkuun Tampereen kautta.
== Graafeihin liittyviä ongelmia ==
Graafeihin liittyy monia suuria avoimia ongelmia, joiden ratkaiseminen toisi keksijälle mainetta ja kunniaa. Monet graafeissa esiintyvistä ongelmista luokitellaan tietojenkäsittelytieteessä ns. [[NP-täydellisyys|"NP" -täydellisiksi]]. Se tarkoittaa lyhyesti sanottuna sitä, että kyseinen ongelma on nykyisten tietokoneiden laskentakapasiteetin ulkopuolella, jos graafin solmujen tai kaarien joukko kasvaa riittävän isoksi. Emme siis tiedä menetelmää, jolla kyseinen ongelma voidaan ratkaista järkevässä ajassa.
Ehkä tunnetuin NP-täydellisestä ongelmasta on [[Kauppamatkustajan ongelma]], jossa on tavoitteena löytää lyhin mahdollinen reitti, joka kulkee kaikkien kauppamatkustajan listassa olevien kaupunkien kautta. Tietojenkäsittelytiede ei kuitenkaan ole varma siitä, ovatko NP-täydellisiksi luetellut ongelmat ratkaistavissa jollain menetelmällä polynomisessa ajassa.
{{tynkä/tietotekniikka}}
| |||