Interactive Knapsacks: Theory and Applications
Aho, Isto (2002)
Aho, Isto
Tampere University Press Tampereen yliopisto
2002
Tietojenkäsittelyoppi - Computer Science
Informaatiotieteiden tiedekunta - Faculty of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Väitöspäivä
2002-11-22
Julkaisun pysyvä osoite on
https://urn.fi/urn:isbn:951-44-5516-9
https://urn.fi/urn:isbn:951-44-5516-9
Tiivistelmä
Reppuongelmassa on kyse tavaroiden pakkaamisesta annettuun tilaan mahdollisimman tehokkaasti. Interaktiivisessa reppuongelmassa tutkitaan, kuinka yhden tilan täyttäminen vaikuttaa viereisiin tiloihin.
Interaktiivinen reppuongelma on reppuongelman yleistys ja moniulotteisen reppuongelman sukulaisongelma. Näitä yhteyksiä käyttäen voidaan interaktiivisen reppuongelman ratkaisumenetelmiä hyödyntää moniulotteisen reppuongelman ratkaisemisessa.
Interaktiivisen reppuongelman ratkaisualgoritmien avulla voidaan esimerkiksi optimoida sähkönjakelua sähkölaitoksen kannalta tai laskea, kuinka tielinjaa vedettäessä ja maastoa tasoitettaessa joudutaan siirtämään vähin mahdollinen määrä maa-ainesta.
Ahon tutkimuksessa tutustutaan myös interaktiivisen reppuongelman laskennalliseen monimutkaisuuteen ja muodostetaan sähkönjakelusovellukselle erilaisia ratkaisumenetelmiä. Lisäksi ratkaisumenetelmiä arvioidaan kokeellisesti.
Interaktiivinen reppuongelma on reppuongelman yleistys ja moniulotteisen reppuongelman sukulaisongelma. Näitä yhteyksiä käyttäen voidaan interaktiivisen reppuongelman ratkaisumenetelmiä hyödyntää moniulotteisen reppuongelman ratkaisemisessa.
Interaktiivisen reppuongelman ratkaisualgoritmien avulla voidaan esimerkiksi optimoida sähkönjakelua sähkölaitoksen kannalta tai laskea, kuinka tielinjaa vedettäessä ja maastoa tasoitettaessa joudutaan siirtämään vähin mahdollinen määrä maa-ainesta.
Ahon tutkimuksessa tutustutaan myös interaktiivisen reppuongelman laskennalliseen monimutkaisuuteen ja muodostetaan sähkönjakelusovellukselle erilaisia ratkaisumenetelmiä. Lisäksi ratkaisumenetelmiä arvioidaan kokeellisesti.
Kokoelmat
- Väitöskirjat [4778]