時(shí)變網(wǎng)絡(luò)最大流問題的新算法.pdf

1、在我們的日常生活中，網(wǎng)絡(luò)無處不在，它們以各種各樣應(yīng)用為背景的形式出現(xiàn)。通常，當(dāng)網(wǎng)絡(luò)中所有的參數(shù)，如點(diǎn)的容量和弧的容量都是常數(shù)，也不考慮流在運(yùn)輸過程中所需的時(shí)間，這樣的網(wǎng)絡(luò)就被看作靜態(tài)的。但是這些假設(shè)在現(xiàn)實(shí)生活中未必成立。例如，一支艦隊(duì)，從一個(gè)港口出發(fā)到達(dá)另一個(gè)港口，途中所需時(shí)間是需要考慮的，還有航道的容量和泊位的數(shù)量也都可能隨著時(shí)間的變化。若一個(gè)網(wǎng)絡(luò)的參數(shù)會(huì)隨著時(shí)間而變化，則稱這樣的網(wǎng)絡(luò)為時(shí)變網(wǎng)絡(luò)。與靜態(tài)網(wǎng)絡(luò)相反，目前只有少數(shù)幾種解決時(shí)

2、變網(wǎng)絡(luò)最優(yōu)化問題的方法。 文中考慮了時(shí)變網(wǎng)絡(luò)的最大流問題。G(N,A,b,l)表示一個(gè)時(shí)變網(wǎng)絡(luò)，N是點(diǎn)集，A是弧集，b(i,j,t)是流經(jīng)弧(i,j)((i,j,)∈A)所需的傳輸時(shí)間，l(i,j,t)是弧(i,j)的容量。b(i,j,t)和l(i,j,t)都是弧(i,j)第一個(gè)點(diǎn)上流的出發(fā)時(shí)間t的函數(shù)，t=0,1，2，...,T, T(T >0)是一個(gè)給定的數(shù)。時(shí)變網(wǎng)絡(luò)最優(yōu)化問題就是在時(shí)間限制T內(nèi)，從發(fā)點(diǎn)送盡可能多的流到達(dá)收點(diǎn)

3、，這個(gè)問題已被證明是NP-完備問題。 本文的結(jié)構(gòu)如下：1.基于偽流我們提出一個(gè)解決時(shí)變最大流問題的算法，剩余容量收縮算法。2.給出時(shí)間標(biāo)號(hào)算法，使得所求最大流的每個(gè)子流到達(dá)終點(diǎn)的時(shí)間都是最早(或最晚)的。用同樣的算法解決了最短間隔路問題，即所求解中每個(gè)子流出發(fā)時(shí)間和到達(dá)時(shí)間之間的間隔是最短的。3.考慮了兩種等待條件，它們分別是零等待時(shí)間和任意等待時(shí)間，證明算法正確性的同時(shí)也列舉算例闡明算法如何進(jìn)行運(yùn)算，每一種算法都能在偽多項(xiàng)式時(shí)