Связь между DAG и поиском пути между двумя узлами в сетке

В руководстве автостопщика по алгоритмам обсуждаются следующие указатели:

1.6 Counting or Optimizing Good Paths
In an n × m grid, we want to go from the left bottom corner to the upper right corner. Each 
time we can only take a step to the right, or a step up. The number of ways we can do this 
is exactly (n+m)!/(n! * m!).  But what if we forbid some points on the grid? For example, if we   
forbid all the points above the line y = x. Some of the problems has answer in closed formula. 
But all of them can be solved quickly by dynamic programming.

Problem 1.6 Given a directed acyclic graph, how many paths are there from u to v? What is the longest one if there are weights on the edges?

Мой вопрос: как связаны эти две проблемы? Какая связь между сеткой здесь и DAG. В самом stackoverflow я прочитал, что если мы движемся только в двух направлениях в сетке, мы можем предположить, что это DAG. Вопрос может показаться очень наивным, но я новичок, и любая помощь будет очень признательна.


graph directed-acyclic-graphs algorithm
person user1071840    schedule 16.10.2012    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Каждая точка сетки является вершиной. У вас есть m * n вершин. Существует ребро, идущее от каждой вершины к вершине, представляющей точку слева от нее, и от каждой вершины к вершине, представляющей точку на ее вершине.

Таким образом, DAG представляет сетку.

person leo    schedule 16.10.2012
comment
[Пример] (google.com/). выглядеть, если каждая точка пересечения в сетке является узлом, а узлы имеют более двух соседей? [Я хочу расширить его график с левыми и верхними соседями до графика с двумя соседями] - person user1071840; 17.10.2012
comment
Не знаю, понимаю ли я ваш вопрос, но в этом графе каждое пересечение является узлом, и между каждым узлом и верхней, левой, правой и нижней точками есть ребро. Дело в том, что вы хотите ограничить движение на графике только вправо и вверх, поэтому я сказал, что вы используете только эти ребра. - person leo; 17.10.2012
comment
Я понял твой ответ. Я просто хотел расширить его, извините, что не ясно. - person user1071840; 17.10.2012