Неявное представление графа
Вначале, мы хотели бы обработатывать все ячейки в одинаковой степени. Следовательно, надо что-то сделать с 'отсутствующими' гранями на границах карты. Их удобно обработать при помощи, добавления отсутствующих граней в направлении за карту и установке издержки этих грани в ¥.
Специальный модификатор можно реализовать в функции стоимости, чтобы учесть это.Все ячейки/вершины теперь имеют точно ту же самую структуру, если обеспечено, что никогда не совершается 'переход' по грани с бесконечной стоимостью грани. Мы знаем то, какие грани имеются, без необходимости явно кодировать это для каждой ячейки (см. рисунок 5). Ячейки сами по себе не представляют никакого интереса; они представлены только стоимостью грани, о которой мы заботимся при определении общей стоимости пути. Однако, мы видели в предыдущих разделах, что все модификаторы стоимости грани - функции свойств грани ячеек источника и адресата. Давайте называть эти свойства для ячейки 'атрибутами', сохранять их в структуре CellAttr и определим массив, где мы сохраняем все атрибуты ячейки, по одному атрибуту для каждой вершины ячейки.
На каждую ячейку ссылаются двумерным индексом, CellRef, в этом массиве. Все, что необходимо знать для того чтобы пройти по грани от любой ячейки до другой - то, как этот как (двумерный) индекс должен быть изменен. Давайте определим номер грани по направлению по часовой стрелке от 0 до 7 (0 - Север, 1 - Северо-Восток, 2 - Восток, 3 - Юго-Восток, и так далее). Затем просто вычислим изменение индекса и сохраним это в справочной таблице, crWalkEdgeDelta[8]. Для прохода по грани, с направлением ed, все, что мы должны cделать затем 'добавлять' crWalkEdgeDelta[ed] к CellRef исходной ячейки.
5.2.2
Еще по теме Неявное представление графа:
- Эффективное представление графа
- Чернышевский Н. Г Детство и отрочество Сочинение графа Л. Н. Толстого Военные рассказы графа Л. Н. Толстого
- Построение графа
- 5. Часто используемые неявные конечно-разностные формулы.
- 3.3.2. Остовное дерево связного графа
- Метрические характеристики графа
- Дифференцирование неявных функций.
- Остерегайтесь неявных опровержений.
- Неявное уклонение от ответов.
- § 22. Производная функции, заданной неявно
- 3.2.2. Расстояния в графе. Диаметр, центр, радиус графа
- Неявная входная информация и правила
- Явное и неявное принуждение.
- 45). Понятие о воображении. Воображение - это процесс преобразования представлений, отражающих реальную действительность, и создание на этой основе новых представлений.
- 7. Реализация неявных разностных схем.
- §32. Двойственный смысл слова «представление» и мнимая очевидность положения о фундировании каждого акта посредством акта представления
- Метод неявного перебора по векторной решетке
- Кольцо взаимодействия онлайнового социального графа