Доброго времени суток!

Пишу свой доморощенный аналог Excel таблицы. Каждая ячейка в таблице может содержать формулу, в составе которой могут быть другие ячейки (её зависимости). Получается система уравнений, зависимости между переменными в ней представлены в виде ориентированного ациклического графа (у меня хранится в матрице смежности). При изменении пользователем значения в ячейке по графу должна быть найдена последовательность пересчета зависимых значений.
Собственно на этой задачей и маюсь. Сначала думал начать поиск от изменяемой вершины, но не смог придумать что делать с зависимостями. Сейчас склоняюсь, что надо начинать поиск от каждой не пройденной вершины, запоминать путь до измененной ячейки и класть его в очередь с приоритетами, где приоритет это расстояние. Последовательность пересчета будет получена из очереди.

Посоветуйте, есть ли более оптимальный алгоритм, ведь наверняка уже все давно придумано?

UPDATE: Схема c ошибкой. Смотрите ниже!


Это сообщение отредактировал(а) Ch0bits - 20.4.2012, 21:15

у вас граф не соответствует формулам!!!

если по формулам, то при изменении C нужно делать одно из
Y->X->Z->X
Z->X->Y->X
Y->Z->X
Z->Y->X

и скорее всего проще не думать о том, какой именно из пересчётов выполнять, и тогда достаточно помнить для каждой ячейки, кто от нее зависит и обойтись без графов

1) Пусть у нас есть изменившийся ячейка или ячейки. Иначе прекращаем алгоритм.
2) Надо найти все ячейки которые имеют связи с нашими изменившимися ячейками. 
3) Затем удалить дубликата.
4) Посчитать изменения в этих ячейках.
5) переходим к пункту 1.

Для быстрого поиска просто хранить в графе обратные дуги, т.е не ориентированный граф.

Приоритеты не нужны если не боитесь лишних вычислений.
А вот если хотите снизить вычислительные затраты то можно с приоритетами.
Тогда в два прохода.  Первый рассчитываем приоритеты второй вычисляем.

Первый проход. Вместо вычисления увеличиваем приоритет на 1.
Затем второй проход вычисляем только те изменившиеся у которых приоритет равен 0. Затем для этих по обратным связям уменьшаем на 1 приоритет.

Если аналог Excel, то есть еще один эффект, о котром следует подумать заранее - функции типа случайное число, которые не имеют аргументов, но в Excel фактически зависят от ВСЕХ ячеек. То есть при любом изменении в любой ячейке производится пересчет случайных величин.

Премного изменяюсь. Нарисовал новую схему, более показательную.



Mirkes, у меня нет рандома, но есть IF - вот засада! Ничего, прорвемся!   

Pavia, эээ... ща подумаю.

Это сообщение отредактировал(а) Ch0bits - 20.4.2012, 21:21

Вы не смотрели в сторону топологической сортировки?

Смотрел, тоже интересная идея, но решений топологической сортировки может быть несколько, а значит будут лишние пересчеты. С другой стороны, преимуществом будет то, можно единожды отсортировать граф для листа, пока неизменны формулы. И не пересчитывать зависимости каждый раз.

До сих пор думаю вот. В понедельник несколько реализаций испробую на реальных данных и выберу менее затратную.

Ну, тогда развернуть стрелочки и хранить граф зависимостей? Тогда просто идти по графу зависимостей от измененной ячейки поиском в ширину и пересчитывать все, на пути попадающееся?

Всему виной моя неграмотность. Графы не пригодились ни разу за 7 лет после института  Спокойно почитал книжку на выходных. 
disputant получи +1, ты абсолютно прав, сегодня реализовал топологическую сортировку, все отлично.

Большое спасибо всем.

Это сообщение отредактировал(а) Ch0bits - 22.4.2012, 13:21