Эффективное представление графа
Давайте рассмотрим традиционное 'обобщенное' представление графа. Каждая ячейка имеет восемь направленных граней идущих от нее к восьми соседним ячейкам. Для каждой грани мы нуждались бы по крайней мере в 4 байтах, чтобы явно сохранить стоимость грани и по крайней мере 2 байта, чтобы сохранить индекс к ячейке адресата.
Из этого следует что надо минимум 48 байт на ячейку. Мы хотим применить наш алгоритм на картах с количеством ячеек порядка миллиона. Это потребует по крайней мере 48Мбайт только для сохранения графа. Под это уйдет вся память, необходимая для фактического пути, найденного алгоритмом, не говоря уже о памяти для приложении для этой работы, являющегося частью намного большей программы. Ясно, что традиционное обобщенное представление графа просто требует в десять раз больше памяти, чем возможно для нашего алгоритма, выполняющегося на стандартном PC сегодня. Только для построения такого (относительно) огромного графа будет тратиться значительное вычислительное время. Конечно, в с течением лет, память и компьютерная технология, доступная сейчас на стандартном PC, очень вероятно, будем прогрессировать. Однако, мы не имеем роскоши, чтобы ждать, когда этот день придет, мы будем способны решать даже более большие проблемы, если мы сможем найти способ делать это практически сегодня! Таким образом, я здесь буду представлять способ неявного представления специального графа, необходимого для нашей проблемы при затратах 3 байта на ячейку.Примеры кода, представленные здесь используют синтаксис C++, но должны быть понятны для большинства людей с элементарными знаниями языков программирования.
5.2.1
Еще по теме Эффективное представление графа:
- Неявное представление графа
- Чернышевский Н. Г Детство и отрочество Сочинение графа Л. Н. Толстого Военные рассказы графа Л. Н. Толстого
- Построение графа
- 3.3.2. Остовное дерево связного графа
- Метрические характеристики графа
- 3.2.2. Расстояния в графе. Диаметр, центр, радиус графа
- 45). Понятие о воображении. Воображение - это процесс преобразования представлений, отражающих реальную действительность, и создание на этой основе новых представлений.
- §32. Двойственный смысл слова «представление» и мнимая очевидность положения о фундировании каждого акта посредством акта представления
- Кольцо взаимодействия онлайнового социального графа
- Старьте вопросы (учение графа Л. Н. Толстого)
- Изучение социального графа в Aster Data Systems
- (Учение графа Л. Н. Толстого) 1885 — 1886 I. ВВЕДЕНИЕ
- ГЛАВА 2. «ИЗОБРЕТЕНИЕ ВСЕОБЩЕГО ДОБРА»: ИДЕОЛОГИЧЕСКИЕ ОСНОВАНИЯ ДЕЯТЕЛЬНОСТИ ГРАФА П.И. ШУВАЛОВА
- 5. Оценка эффективности методов управления риском. Оценка эффективности страхования
- 536. Какое юридическое значение для получения выплаты по аккредитиву имеет представление исполняющему банку так называемого реестра счетов? Является ли представление данного документа обязательным в том случае, когда оно не предусмотрено условиями аккредитива?
- 75. Собственников предприятия, акционеров, поставщиков, покупателей, кредиторов, налоговые органы интересует информация об изменении доли собственного капитала, о доходах, об эффективности инвестиций и эффективности использования ресурсов и др.
-
Автоматизация -
Гидрология -
Документоведение, делопроизводство -
Информационные системы -
Коммуникации -
Криптография -
Машиностроение -
Метрология -
Механика -
Микроэлектроника -
Нефтегазовое дело -
Пищевая промышленность -
Приборостроение -
Программирование -
Системный анализ, управление и обработка информации -
Строительство -
Технология и оборудование механической и физико-технической обработки -
Электрическая энергия -
Энергетика -
-
Архитектура и строительство -
Безопасность жизнедеятельности -
Библиотечное дело -
Бизнес -
Биология -
Военные дисциплины -
География -
Геология -
Демография -
Диссертации России -
Естествознание -
Журналистика и СМИ -
Информатика, вычислительная техника и управление -
Искусствоведение -
История -
Конфликтология -
Культурология -
Литература -
Маркетинг -
Математика -
Медицина -
Менеджмент -
Педагогика -
Политология -
Право России -
Право України -
Промышленность -
Психология -
Реклама -
Религиоведение -
Социология -
Страхование -
Технические науки -
Учебный процесс -
Физика -
Философия -
Финансы -
Химия -
Художественные науки -
Экология -
Экономика -
Энергетика -
Юриспруденция -
Языкознание -