Память или скорость

Программисты хорошо знают проблему оптимизации работы программы в случае когда алгоритм требует огромных вычислительных затрат. В качестве примера можно привести программное обеспечение , разрабатываемое для навигационных приборов и для карт GPS-навигаторов. Проблема в том, что карта расстояний представляет собой граф, вершинами в котором являются населенные пункты, а ребра графа - дороги их соединяющие. Например, если это карта России, то число населенных пунктов будет фантастически огромным.

Если надо решать задачу поиска кратчайшего пути, то можно применяя алгоритм Дейкстры этот лучший путь определить на графе с нагруженными дугами (ребрами). Но, если граф имеет большое число вершин и ребер, алгоритм будет работать медленно. Выкрутиться можно, выполнив все расчеты предварительно и затем только в нужный момент выбирать подходящий оптимальный вариант. Результат получается почти мгновенно. Но для хранения огромного объема информации требуется память, которая стоит совсем не дешево. Получается проблема: увеличиваем скорость за счет памяти и тем самым увеличиваем стоимость устройства. Вот тут и приходится решать оптимизационную задачу, ограничивая время для вычислений и затраты на оперативную память. для каждого типа устройства задача решается по разному в зависимости от технических требований по быстродействию, стоимости, весу устройства и в соответствии с предельными размерам.

Решение такой оптимизационной задачи для конкретного устройства может быть отличной дипломной работой. Более того, студент сумеет не только доказать ее актуальность, но и легко получить акт о внедрении в какой-то компании занимающейся написание программного обеспечения для систем навигации.