среда, 19 сентября 2012 г.

bug in "The Algorithm Design Manual", Second Edition ?

Сitation from subchapter 8.7.2 When are Dynamic Programming Algorithms Efficient? on page 315:
Let LP' [i, j, S] denote the longest simple path from i to j, where the intermediate vertices on this path are exactly those in the subset S. Thus, if S = {a, b, c}, there are exactly six paths
consistent with S: iabcj, iacbj, ibacj, ibcaj, icabj, and icbaj. This state space is at most 2**n, and thus smaller than enumerating the paths
Wait, if this is exponent we must have 2 ** 3 = 8 paths. But actually this is factorial ! Why Skiena claims that this is exponent ?

Комментариев нет:

Отправить комментарий