Bidecision algorithm

In this section we constitute an algorithm which solves the associative shortest and longest path problem (ASP). We generate a sequence

{(J/k)' ^Fi(k))ii

^E

^V},

^k

= ^0,

1,

2,

... , which converges to the solution

{(ji,Fi)li

E V} of the system of eqs.

(8), (9)

^with

^(10).

^The

desired minimal and maximal path lengths form one solution of the system. Moreover, the uniqueness of the solution of the system was shown in Theorem

2.

Therefore, using the sequence which converges to the solution, we can find the desired Ininiinal and n1aximaJ path lengths.

Bidecision algorithm Step 1. Initialization. Set

nun

ti1·, i = ^1,

^2,

.

^.

. , N- 1, f fJ ⁾ = R(o),

jED(i)

Max

ti1·, i =

1, 2,

... , N- 1, F�) = R(o).

jED(i)

Step 2. Iteration. Set

. [ f(k-1)]

^.

[ p(k-1)]

.1111n.

tij

^o

i

!\

.

^min.

^tij o

^j

,

JED+(t) JED-(t)

[ ^(k-1)] [ (k-1)]

Max

tij o Fi

V Max

tij o fi ,

jED+(i) jED-(i)

pJ:)=R(o).

Step 3. Stopping rule. If

then stop. Otherwise, set k ⁼ k +

1

and go to step 2.

i =IN,

(32) (33)

(34) (35) (36)

Theorem 3.

The bidecision algorithm terminates in at most N - 1 iterations. Then we obtain the solution of the system of eqs. (8), (9) with (10).

Proof.

Let

i =I N

be a given but arbitrary node. Then from (34), (35) and Lemma 1, it follows that there exists j E

D(i)

satisfying that

IJ}N-1)- ^{f i} (N-2)i

^v

i.F:(N-1)- .F:(N-2)1

<

i ^t _t] .. o _{f(N-2)- J} ^t-. _t) o ^f _] � N

^-

3 ) i

V

it

^.

_t)

^.

o _{p(N-2)- J} ^t _t)

^{. .}

o _{p(N-3)i J .}

Hence, in the same way as in the proof of Theorem

2,

we obtain

f _t (N

^-1)

= _{j(N -2) t ' F.(N-l) t} = _{p.(N-2) t} ,z= , ,

^.

^{1 2}

^..

.

^,

^N

^-

¹

^{, (37)}

Furthermore,

f (N-1) N _ - N j(N-2)

^_

- N p(N-1)

^_

- N p(N-2)

^·

Therefore, the bidecision algorithm terminates in at most N- 1 iterations.

Moreover, fro1n (34), (35), (37) and (38) we have

p.(N-1)

_t

. nun.

[tij

^o

! } N -2)]

^1\

.

min.

[tij

^o

F j N -2)]

JED+(t) JED-(t)

·

[ j(N-1)] . [ p(N-1)]

1run

tiJ.

^o

J.

^1\ min

tiJ.

^o

J. ,

jED+(i) jED-(i)

Max

[tiJ.

^o

FJ(N-2)]

^V Max

[tiJ .

^o

JJ(N-2)]

jED+(i) jED-(i)

Max

[tiJ.

^o

FJ�N-1)]

^V Max

[tiJ.

^o

JJ(N-1)],

jED+(i) jED-(i)

F t' ^-1)

^{= R( o ).}

(38)

Consequently, {

(fi(N-1), �(N-I))

li E V} is the solution of the system of eqs. (8),

(9)

_with

(1 0).

Remark 3. Meanings of

fi(k), Fi(k)

generated above are as follows:

fi(k)

= the length (3) of the shortest path from node i to reachable node or to N when k + 1 or fewer arcs are used, respectively.

Fi(k)

the length (3) of the longest path from node i to reachable node or to N w hen k + 1 or fewer arcs are used, respectively,

i=1 ,2,

..

_. ,N-l.

0

Since these can be proved in the same way in remark 3 of Maruyama

(1996),

we omit the demonstration.

Let

the node j E V whkh attains the n1inimum

of r.h.s. of (34), (39)

(J(k)

( i) the node j E V which attains the maximum

of r.h.s. of (35). ( 40)

Then in the same method as in Section 2 both optimal decision functions

1r(k)

( ^·

)

_and

a(k)

( ^·

)

generate both the shortest and the longest path from node i to reachable node or N when k + 1 or fewer arcs used, respectively.

Remark 4. In order to solve the problern

(

_ASP

)

which admits the singl recursive equation

( 4),

we can use the following algorithm

(

Ford's Algorithm

)

_:

Step 1. Initialization. Set

f(O)-

t. - jED(i) rrun

.

ti1·, i ⁼ 1,

2, ... , N -1, J�)

⁼

^R(

o

)

_.

Step 2. Iteration. Set

f(k)

t . ^-- m1n

. [t..

^t] 0

f(k-1)]

.

jED(i) ^J

Step 3. Stopping rule. If

i

-I N, J1k)

⁼

^R(

o

)

_.

f_(k)

t ⁼

f(k-1)

t ' z = ^.

^{1 2}

' , . ^. . '

^N

'

then stop. Otherwise, set k ⁼ k

+ 1

and go to step

2.

(41)

( 42)

Remark 5. Let us compute the number of operations required by the bidecision algorithn1 for each type of problen1.

The maximum problem can be solved by the Ford's algorithtn. So, each iteration of the algorithm requires

(N- 1)2

maximization

(V)

_and

(N- 1) (N- 2)

comparisons. Since

N -1

iterations are required, for all iterations

2N3-7N2+8N -3

operations are required;

the number of operations is the same ^as that in the additive problem.

In the multiplicative problem, each iteration of the bidecision algorithm requires

2(N-1)2

multiplications and

2(N-1) (N-2)

comparisons. Since

N-1

iterations are required, for all iterations

4N3-14N2 + 16N- 6

operations are required; the number is two times that in the additive problem.

In the multiplicative-additive problem, each iterabon of the bidecision algorith1n re­

quires

6(N- 1)2

operations

(2(N- 1)2

additions,

2(N - 1)2

subtractions and

2(N- 1)2

multiplications

)

_and

2(N -1)(N- 2)

comparisons. Since

N

-

1

iterations are required, for all iterations

8N3-26N2 + 28N-10

operations are required; the nu1nber is approxi1nately four times that in the additive problem.

In the fractional problem I, each iteration of the bidecision algorithrn requires

8(N -1)2

operations

(4(N- 1)2

additions,

2(N- 1)2

multiplications and

2(N -1)2

_fractions

)

_and

2( N - 1) ( N - 2)

comparisons. Since

N - 1

iterations are required, for all iterations

10N3- 32N2 + 34N- 12

operations are required; th number is approximately five tirnes that in the additive problem.

40

In the fractional problem II, each iteration of the bidecision algorithm requires 12(N-1)2 operations (2(N- 1)2 additions, 4(N-1) 2 multiplications and 4(N- 1) 2 subtractions and 2(N- 1) 2 fractions) and 2(N- 1)(N- 2) cornparisons. Since N -

¹

iterations are required, for all iterations 14N3 - 44N2 + _46N-

16

operations are required; the nun1ber is approximately seven times that in the additive problem.

Consequently, in all problems above, we obtain the running time of O(N3) for all iterations.

Example 5.

We reconsider the n1ultiplicative-additive problem (a

o

b =a+ b- ab) _{on a}

network given in Fig.2. By applying the bidecision algorith1n, the sequence { (Ji(k), F/k))},

^k

=

0, 1, 2, . .. can be computed successively as shown in Table 1. Fro1n this table, we can see that the shortest path length and the longest one fron1

¹

to 6 are

^-

1i and 10, respectively.

The pairs of the node 1r(k)(i) and the node O"(k)(i) which are defined by (3.8) _and (3.9),

respectively are given in Table 2. Using the optimal decision functions 1r(k) (

^-

) ,

O"(k)

(

^-

)

^,

we can find the shortest path ( 1, 3,

5,

4, 6) and the longest path ( 1, 3, 4, 6), simultaneously.

We remark that since this problem does not admit the single recursive equation, it can not be solved by the Ford's algorithm.

Table 1: Sequence in the multiplicative-additive problem (a

o

b =a+ b- ab)

Node (ji(O)' pi(O)) (!?)' _{pi( 1))} (!?)' _pi(2)) (Ji(3)' pi(3)) (Ji( 4), pi( 4)) = _{(Ji, Fi)}

1 (3,4) ( -2, %) (-11,2) ( -lf, 10) ( -¥, 10)

2 ( �' ^{1) (�,�) (1, � ) (1) � ) (1' �)}

3 (2, ₂₎ (4,5) (-2, � _{7) (-2,1} ; _{) (-2,187)}

4 (4,4) (4,4) ( 4, 4) ( 4, 4) ( 4, 4)

5

(±, 3) (3, _�3) (3, ₁₄₃₎ (3, _�3) (3 ₁₄₃₎

6 (0,0) (0,0) (0, 0) (0,0) (0,0)

Table 2: Sequence of optimal decision function in the multiplicative-additive problem

Node (1r(1)(i), a(l>(i)) ( 7r(2) ( i)' 0"(2) ( i)) ( 7r(3) ( i)' 0"(3) ( i)) (7r(4)(i), 0"(4)(i))

1

(3,3) (3,2) (3,3) (3,3)

2 (5,5) (4,5) (4,5) (4,5)

3 (4,5) (4,5) (4,5) (4,5)

4 (6,6) (6,6) (6,6) (6,6)

5 (6,4) (6,4) (6,4) (6,4)

Example 6.

Let us reconsider the fractional problen1

I

(a

^o

b

⁼

(a + b)/ ( 1 + ab)) on a network given in Fig.3. Since this proble111 does not admit the single recursive equa­

tion, we must use the bidecision algorithm. The sequence { (fi(k), Fi(k))} can be com­

puted successively

as

shown in Table 3. From Table 4, we can find the shortest paths ( 1,3,5,6), ( 1,2,5,6) and the longest path ( 1,3,4 6) whose lengths are 191 and �� ' respec­

tively.

Table 3: Sequence in the fractional problem

I

(a

^o

b

⁼

(a+ b)/(1 + ab))

Node (ji(O)' pi(O)) (!?)' F:(1)) (!?)' pi(2)) (fi(3)' F:(3)) (fi(4), pi(4))

⁼

(ji, Fi)

1

(2,3) (� I) (� �) ( __!L 12) (JL 12)

r�

^11'

j

^{1 11' 17}

11 ' 1

⁷

2 ( �' ¹⁾ _(7,2) ^{( 1'} 2) ( 1, 183) (1, �3)

3 ( �' 3) ( � li)

^{5' 7}

(§_ li)

_{7 ' 7}

( � 13)

_{7 ' 7}

( � li)

_{7 ' 7}

4 (2,2) (2,2) (2, 2) (2,2) (2, 2)

5 (�, 4) ( i' ⁴⁾ ( � ,4) ( �' ⁴⁾ ( �

^'

⁴⁾

6 (0,0) (0,0) (0, 0) (0,0) (0,0)

Table 4: Sequence of optimal decision function in the fracrional problem

I

Node (7r(l) (i)' 0"(1) (i)) ( 7r(2) ( i)' 0"(2) ( i)) (7r(3)(i), 0"(3)(i)) (7r(4)(i), 0"(4)(i))

1

(3, 2)' (3, 3) (2,2), (2,3) , (3,2), (3,3) (2, 3)' (3, 3) (2, 3)' (3, 3)

2 (5,5) (4,5) (4,5) (4,5)

3 (3,5) (4,5) (4,5) ( 4, 5)

4 (6,6) (6,6) (6, 6) (6, 6)

5 (4,6) (4,6) (4,6) (4,6)

Example 7. We review the fractional problen1 II

(

a _o

b

₌ a

b

_/

₍

₁

+ (1 -

a

) ( 1 ^-b)))

on a network given in Fig.4. The single recursive equation does not hold for this proble1n;

hence we can not use the Ford's algorith1n. So, by applying the bidecision algorithm, ^we can compute the sequence

{ (Ji(k), Fi(k))}

successively as shown in Table 5. From Table 6, we can find both the shortest path (1, 3, 2, 5, 6) and the longest path (1, 3, 4, 6) whose lengths are

-t

^and

_2�,

respectively.

Table 5: Sequence in the fractional problem II

(a

_o

b

₌

ab

_{/ ( 1 +}

₍

₁

-

a

) ₍ 1 - ^b)))

Node

(ji(O)' F:(O)) (JP)) F?)) (JF), pi(2)) (fi(3)' pi(3)) (fie 4J, Fie 4J)

⁼

(fi, Fi)

1

_{( -4,}

1) (-�,�) ₍

-

j

^,

t ⁾ (-t,�) ( -�, $)

2 ( -3, -2)

( -�' _{lp) (} -�, _�3) (-�, _{�3) (} -�' _�3)

3

(-1,�) ^{( -4} '

¹⁸

⁾ (

^-

⁴

^,

¹¹⁾ ( -4, 11) (-4,11)

4

(�) �) (�,�) (�' �) ( �' �) ( �' �)

5 ( -2,

�)

^{( -2,}

1\)

^{( -2,}

1\)

^(-2,1

\

) ( -2,

1\)

6

( 1' 1) ( 1' 1) (1'

1)

( 1' 1)

_{( 1' 1)}

Table 6: Sequence of optimal decision function in the fractional pro ble1n ^II Node

(7r(l)(i), O"(l)(i)) ( 7r(2) ( i)' 0"(2) ( i)) (7r(3)(i), 0"(3)(i)) (7r(4)(i), 0"(4)(i))

1

^(3,3) (2,3) (3,3) (3,3)

2 (4,5) (4,5) (4,5) (4,5)

3 (4,5) (4,2) (4,2)

(4,2)

4 (6,6) (6,6) (6,6) (6,6)

5 (6,4) (6,

4) (6,4)

_(6,4)

References

Bellman, R., Esogbue, A.O. and Nabeshi1na, I., (1982), Mathematical Aspects of Schedul­

ing and Applications, Pergamon Press, New York.

Butnariu, D. and Klement, E.P., (1993), Triangular norm-based n1 asures and games with fuzzy coalitions, Kluwer Academic Publishers.

Dreyfus, S.E., (1969), An appraisal of some shortest-path algorithn1s, Oper. Res.,

17,

pp. 395-412.

Frieze, A., (1977), Minimum paths in directed graphs, Oper. Res. Quart., 28, pp.

339-346.

Iwamoto, S., (1987), Theory of Dyna1nic Programs (in Japanese), Kyushu University Press.

Iwamoto, S., (1993), From dynamic programming to bynamic program1ning, J. Math.

Anal. Appl., 177, pp. 56-74.

Maruyama, Y., (1996), Shortest and longest path problems, Optimization, 38, pp. 287-299.

Maruyama, Y., (1997), On associative shortest path problems, Bull. Inform. Cybernet., 29, pp. 67-81.

Smith, D.K., (1991), Dynamic Programming, Ellis Horwood Limited.

Sniedovich, M., (1992), Dynamic Progranm1ing, Marcel Dekker.

ドキュメント内 結合法則をみたす2項演算で経路の長さが定義された 最適経路問題 (ページ 43-50)