Tanker scheduling problem


Informatikos kursinis darbas. Duota problema - tanker scheduling problem. Greedy algoritmai. Tanker scheduling problem = greedy algoritmas activity-selection(darbų pasirinkimo) problemai. Požiūris į problemą. Problemos sprendimo realizavimas. Algoritmo sudėtingumas. Programos bandymas – duomenys ir rezultatai. Naudota literatūra.


Rodo pilnų laivų su siuntiniais laikus tarp uostų(įskaitant ir laikus krovinių pakrovimui ir iškrovimui) ir tuščių laivų sugrįžimo laivus(be siuntinių).

Optimizacijos problemoms spręsti naudojami algoritmai, paprastai turi tam tikrą aibę žingsnių, su daug pasirinkimų kiekviename jų. Daugeliui optimizacijos problemų, geriausiam pasirinkimui rasti naudoti dinaminį programavimą yra bereikalingas galingo algoritmo pasirinimas, paprastai tai galima padaryti su daug efektyvesniais algoritmais.

Greedy algoritmas visada padaro sprendimą, kuris atrodo geriausias tam momentui. T.y. jis padaro lokaliai optimalų sprendimą, su ta viltim, kad šis pasirinkimas prives prie globaliai optimalaus sprendimo.

Greedy metodu bandoma sukonstruoti optimalų sprendimą pakopomis. Kiekvienoje pakopoje pagal keletą kriterijų priimame tą sprendimą, kuris atrodo geriausias tuo momentu. Sprendimas priimtas vienoje pakopoje nekeičiamas vėlesnėse pakopose, taigi kiekvienas sprendimas turi garantuoti tinkamumą. Kriterijus naudojamas priimti greedy metodu sprendimus kiekvienoje pakopoje vadinamas greedy kriterijumi.

Greedy algoritmai ne visada duota optimalius sprendimus, bet su daugeliu problemu jis kuo puikiausiai veikia.

Greedy metodas yra pakankamai galingas ir gerai dirba su daugelio sričių problemomis. Minimalios trukmės medžio (minimum-spanning-tree) algoritmai, Dijkstra‘s algoritmas rasti trumpiausiems keliams, išeinantiems iš vieno šaltinio, ir Chvatal‘s algoritmas, kuriam greedy paslepia heuristiką, gali būti puikūs greedy metodo pritaikymo pavyzdžiai..

Tanker scheduling problem. (2010 m. Kovo 03 d.). http://www.mokslobaze.lt/tanker-scheduling-problem-kursinis.html Peržiūrėta 2016 m. Gruodžio 06 d. 18:08