Эффективное представление графа
Давайте рассмотрим традиционное 'обобщенное' представление графа. Каждая ячейка имеет восемь направленных граней идущих от нее к восьми соседним ячейкам. Для каждой грани мы нуждались бы по крайней мере в 4 байтах, чтобы явно сохранить стоимость грани и по крайней мере 2 байта, чтобы сохранить индекс к ячейке адресата.
Из этого следует что надо минимум 48 байт на ячейку. Мы хотим применить наш алгоритм на картах с количеством ячеек порядка миллиона. Это потребует по крайней мере 48Мбайт только для сохранения графа. Под это уйдет вся память, необходимая для фактического пути, найденного алгоритмом, не говоря уже о памяти для приложении для этой работы, являющегося частью намного большей программы. Ясно, что традиционное обобщенное представление графа просто требует в десять раз больше памяти, чем возможно для нашего алгоритма, выполняющегося на стандартном PC сегодня. Только для построения такого (относительно) огромного графа будет тратиться значительное вычислительное время. Конечно, в с течением лет, память и компьютерная технология, доступная сейчас на стандартном PC, очень вероятно, будем прогрессировать. Однако, мы не имеем роскоши, чтобы ждать, когда этот день придет, мы будем способны решать даже более большие проблемы, если мы сможем найти способ делать это практически сегодня! Таким образом, я здесь буду представлять способ неявного представления специального графа, необходимого для нашей проблемы при затратах 3 байта на ячейку.Примеры кода, представленные здесь используют синтаксис C++, но должны быть понятны для большинства людей с элементарными знаниями языков программирования.
5.2.1
Еще по теме Эффективное представление графа:
-
Автоматизация -
Гидрология -
Документоведение, делопроизводство -
Информационные системы -
Коммуникации -
Криптография -
Машиностроение -
Метрология -
Механика -
Микроэлектроника -
Нефтегазовое дело -
Пищевая промышленность -
Приборостроение -
Программирование -
Системный анализ, управление и обработка информации -
Строительство -
Технология и оборудование механической и физико-технической обработки -
Электрическая энергия -
Энергетика -
-
Архитектура и строительство -
Безопасность жизнедеятельности -
Библиотечное дело -
Бизнес -
Биология -
Военные дисциплины -
География -
Геология -
Демография -
Диссертации России -
Естествознание -
Журналистика и СМИ -
Информатика, вычислительная техника и управление -
Искусствоведение -
История -
Культурология -
Литература -
Маркетинг -
Математика -
Медицина -
Менеджмент -
Педагогика -
Политология -
Право России -
Право України -
Промышленность -
Психология -
Реклама -
Религиоведение -
Социология -
Страхование -
Технические науки -
Учебный процесс -
Физика -
Философия -
Финансы -
Химия -
Художественные науки -
Экология -
Экономика -
Энергетика -
Юриспруденция -
Языкознание -