Сүлжээний хамгийн их урсгал. Хамгийн их урсгалыг олох алгоритм

Ус зайлуулах суваг тэмдэглэгдэх хүртэл бид энэ үйлдлийг давтана. Хэрэв урсгал нь шошгогүй хэвээр байвал олсон урсгал нь хамгийн их байх ба тэмдэглэгдсэн оройг тэмдэглэгээгүй цэгүүдтэй холбосон нумуудын багц нь хамгийн бага зүсэлт үүсгэдэг.

3. Хувьцааг шошготой болго (j+, ε(t)), Дараа нь f(j,t)-ээр солино f(j,t)+ε(t). Хэрэв хувьцаа тэмдэглэгдсэн бол (j-, ε(t)), Тэр f(j,t)-ээр солино f(j,t)-ε(t). Оргил руугаа явцгаая j. Хэрэв jтэмдэгтэй (i+, ε(j)), дараа нь бид солино f(i,j)дээр f(i,j)+ε(t), мөн хэрэв (i-, ε(j)), f(j,i)-ээр солино f(j,i)-ε(t). Оргил руугаа явцгаая би. Бид эх сурвалжид хүрэх хүртэл энэ үйлдлийг давтана с.Урсгалын өөрчлөлт зогсч, бүх тэмдэг арилж, 2-р алхам руу орно

ЖИШЭЭ 3.14.

М 4 К

ДААЛГАВАР. Сүлжээний хамгийн их урсгалыг ол

АЛГОРИТМ

Оройг тэмдэглэе s = x 0. Бусад нь бүгд x i.

1-р шат.

1. Бүх нумууд нь ханаагүй ямар ч замыг сонго.

2. Бид ханасан нум байхгүй болтол энэ замын дагуух урсгалын хэмжээг нэгээр нэмэгдүүлнэ.

Бид бүрэн урсгалыг барих хүртэл урсгалыг нэмэгдүүлэх үйл явцыг үргэлжлүүлнэ, i.e. ямар ч зам дор хаяж нэг ханасан нум агуулна.

2-р шат.

2. Хэрвээ х i нь аль хэдийн тэмдэглэгдсэн орой бол (+i) ханаагүй нумууд х i-ээс очдог бүх тэмдэглэгээгүй оройг, (–i) индексээр тэгээс өөр урсгалтай нумууд гардаг бүх тэмдэглэгдээгүй оройг тэмдэглэнэ. х i.

3. Хэрэв энэ үйл явцын үр дүнд орой тэмдэглэгдсэн бол т, дараа нь хооронд сТэгээд тБүх оройг нь өмнөх оройнуудын тоогоор тэмдэглэсэн зам байдаг. Бид энэ замын бүх нуман дахь урсгалыг нэгээр нэмэгдүүлнэ сруу тнумын чиглэл нь хөдөлгөөний чиглэлтэй давхцаж байгаа бөгөөд хэрэв нум нь эсрэг чиглэлтэй байвал нэгээр багасна. 1-р алхам руу шилжье.

4. Дээд талд байх үед түйл явц дууссан гэж тэмдэглэх боломжгүй бөгөөд үүнээс үүдэн гарсан урсгал нь сүлжээний хамгийн том урсгал юм.

ЖИЧ. Та эхний шатыг дуусгахгүйгээр 2-р шат руу явж болно (жишээ 3.16-г үзнэ үү).

ЖИШЭЭ 3.15.

9

ШИЙДЭЛ:

Өгөгдсөн тээврийн сүлжээнд бүрэн урсгал олдсон. Ханасан нумуудыг тодруулсан

Энэ сүлжээнд та мөн төгсгөлийн оройг тэмдэглэж болох бөгөөд тэмдэглэгээний үр дүн ижил байх болно. Урсгалыг өөрчилснөөр бид эцсийн оройг тэмдэглэх боломжгүй сүлжээг олж авдаг тул доторх урсгал нь хамгийн том бөгөөд 10-тай тэнцүү байна.

ЖИШЭЭ 3.16.

8 2 1

Өгөгдсөн тээврийн сүлжээнд бүрэн бус урсгал илэрсэн

Сүлжээг тэмдэглэж, алгоритмын дагуу урсгалыг нэмэгдүүлье. Бид авдаг

Энэ сүлжээнд та мөн төгсгөлийн оройг тэмдэглэж болох бөгөөд тэмдэглэгээний үр дүн ижил байх болно. Урсгалыг өөрчилснөөр бид эцсийн оройг тэмдэглэх боломжгүй сүлжээг олж авдаг тул доторх урсгал нь хамгийн том бөгөөд 6-тай тэнцүү байна.

IV хэсэг. Динамик програмчлал.

Динамик програмчлалыг олон үе шаттай оновчтой шийдлүүдийг олоход ашигладаг. Тухайлбал, тоног төхөөрөмжийг солих урт хугацааны төлөвлөлт; салбарын үйл ажиллагаа хэдэн жилийн . Энэ нь оновчтой байх зарчмыг ашигладаг бөгөөд үүний дагуу аливаа шинэ хэсэгчилсэн шийдэл нь хүрсэн төлөвтэй харьцуулахад оновчтой байх ёстой.

Нэгийг олон удаа шийдсэн нь дээр энгийн даалгаварнэгээс илүү төвөгтэй.

АСУУДАЛ 1. Хоёр цэгийн хоорондох хамгийн ашигтай замын тухай.

А ба В хоёр цэгийг холбосон замыг барих шаардлагатай бөгөөд хоёр дахь нь эхнийхээс зүүн хойд зүгт байрладаг. Энгийнээр хэлэхэд, зам тавих нь хэд хэдэн алхмуудаас бүрдэх бөгөөд алхам бүрт бид хойд эсвэл зүүн тийш шилжих боломжтой гэж үзье. Дараа нь аливаа зам нь шаталсан тасархай шугам бөгөөд сегментүүд нь координатын тэнхлэгүүдийн аль нэгэнд параллель байна. Эдгээр хэсэг тус бүрийг барих зардал нь мэдэгдэж байна.

ЖИШЭЭ 4.1. А-аас В хүртэлх хамгийн бага замыг ол.

Сүүлийн алхам бол T.V. Сүүлчийн алхамаас өмнө бид ТВ-д нэг алхамаар хүрч болох цэгүүд дээр байж болно. Ийм хоёр цэг байдаг (систем нь хоёр муж улсын аль нэгэнд байж болно). Тэд тус бүрийн хувьд t.V хүрэх ганц сонголт байдаг: нэг нь - зүүн тийш шилжих; нөгөөгийнх нь хувьд - хойд зүгт. Тохиолдол бүрт 4 ба 3-ын зардлыг бичье.

4

Одоо эцсийн өмнөх алхамыг оновчтой болгоё. Өмнөх алхмын дараа бид C 1, C 2, C 3 гэсэн гурван цэгийн аль нэгэнд хүрч болно.

C 1 цэгийн хувьд зөвхөн нэг удирдлага байна (үүнийг сумаар тэмдэглэе) - зүүн тийш шилжих бөгөөд зардал нь 2 (энэ алхамд) + 4 (дараагийн алхамд) = 6 болно. Үүний нэгэн адил С 3 зүйлийн хувьд зардал 2+3=5 болно. t.C 2-ийн хувьд зүүн эсвэл хойд зүг рүү явах хоёр удирдлага байдаг. Эхний тохиолдолд зардал 3+3=6, хоёр дахь тохиолдолд 1+4=5 байна. Энэ нь болзолт оновчтой хяналт нь хойшоо явах явдал юм. Үүнийг сумаар тэмдэглээд харгалзах зардлыг оруулъя.

Хариулт: x 1 =1; x 3 =0; x 3 =4; W=3.5

НЭГДСЭН АЛГОРИТМ

1. Системийг тайлбарлана уу. Өөрөөр хэлбэл, алхам бүрийн өмнө хяналттай системийн төлөв байдлыг ямар үзүүлэлтээр тодорхойлдог болохыг олж мэдээрэй. Хяналттай системийн тайлбарыг аль болох хялбаршуулж, шаардлагагүй нарийн ширийн зүйлээр хэт ачаалалгүйгээр даалгавраа зөв, "даруухан" тавьж чаддаг байх нь чухал юм.

2. Үйлдлийг үе шат (үе шат) болгон хуваах. Удирдлагад тавьсан бүх боломжийн хязгаарлалтыг энд харгалзан үзэх ёстой. Алхам нь хангалттай бага байх ёстой бөгөөд ингэснээр алхмын хяналтын оновчлолын процедур нь нэлээд энгийн байх ёстой; Үүний зэрэгцээ алхам нь хэтэрхий бага байх ёсгүй бөгөөд ингэснээр оновчтой шийдлийг олох процедурыг хүндрүүлдэг шаардлагагүй тооцоолол хийхгүй байх ёстой, гэхдээ оновчтой шийдэлд мэдэгдэхүйц өөрчлөлт оруулахгүй байх ёстой. зорилгын функц.

3. Алхам бүрийн хяналтын багц x i болон тэдгээрт тавигдах хязгаарлалтыг олж мэд.

4. Хэрэв өмнө нь систем S төлөвт байсан бол x i удирдлага нь i шатанд ямар ашиг авчрахыг тодорхойл. Төлбөрийн функцуудыг бичнэ үү:

w i =f i (S, x i)

5. Х i дээр удирдлагын нөлөөгөөр системийн төлөв байдал хэрхэн өөрчлөгдөхийг тодорхойлно 1-р алхам, өөрөөр хэлбэл төлөвийн өөрчлөлтийн функцийг бичих.

S / =φ i (S, x i)

6. Мэдэгдэж байгаа функцээр нөхцөлт оновчтой олзыг илэрхийлэх үндсэн давтагдах динамик програмчлалын тэгшитгэлийг бич.

W i (S)= max(f i (S, x i)+W i+1 (φ i (S, x i)))

7. Үйлдвэрлэх нөхцөлт оновчлолсүүлчийн алхам, эцсийн шат хэрхэн дууссан талаар янз бүрийн таамаглал дэвшүүлж, эдгээр таамаглал тус бүрийн хувьд хамгийн сүүлийн алхамд нөхцөлт (алхам ямар нэгэн зүйлээр дууссан гэсэн нөхцөл дээр үндэслэн сонгосон) оновчтой хяналтыг ол.

W m (S)= max(f m (S, x m))

8. Эцсийн өмнөх алхамаас эхлээд эхний алхам хүртэл (буцаж) нөхцөлт оновчлолыг гүйцэтгэнэ.

9. Үйлдвэрлэх болзолгүй оновчлолхяналт, алхам бүрт холбогдох зөвлөмжийг "унших": эхний алхамд олсон оновчтой хяналтыг авч, системийн төлөвийг өөрчлөх, хоёр дахь шатанд олсон төлөвийн оновчтой хяналтыг олох гэх мэт. сүүлчийн алхам хүртэл.

ОНОВЧТОЙ БАЙХ ЗАРЧИМ. Дараагийн алхамд хүрэхээс өмнө системийн төлөв байдал ямар ч байсан энэ үе шатанд хяналтыг сонгох шаардлагатай бөгөөд ингэснээр энэ алхамын үр өгөөж, дараагийн бүх үе шатуудын хамгийн оновчтой үр өгөөж хамгийн их байх болно.

Динамик програмчлалын зарчим нь алхам бүрийг бусдаас үл хамааран тусад нь оновчтой болгодог гэсэн үг биш юм. Хэрэв энэ алхам нь дараагийн алхамуудад сайн ялах боломжоо алдах юм бол тодорхой нэг алхам дээр үр дүнтэй байх хяналтыг сонгох нь ямар учиртай вэ?

Практикт үйл ажиллагааг тодорхой бус хугацаагаар төлөвлөх тохиолдол байдаг. Ийм тохиолдлын загвар нь бүх алхамууд тэнцүү байх хязгааргүй алхамт хяналттай процесс юм. Энд ялалтын функц болон төлөвийг өөрчлөх функц нь алхамын тооноос хамаардаггүй.

Бүлэг V. ЗУРАГЧЛАЛЫН ЗАГВАРЧИЛГАА

Энэхүү гарын авлага нь дискрет математик ба/эсвэл графикийн онолын чиглэлээр суралцаж буй оюутнуудад зориулагдсан болно. Түүний тусламжтайгаар та "Сүлжээний хамгийн их урсгал ба хамгийн бага зүсэлт" сэдвийг эзэмших болно. Энэ гарын авлагаас та өөрийн ID-аа компьютер дээрээ MATLAB-гүй байсан ч шууд тооцоолж болно. Хэрэв танд MATLAB байгаа бол энэ хуудас руу очно уу: Тэнд та тооцооллын скрипт (програм) -д хөндлөнгөөс оролцох боломжтой. Энд сүлжээн дэх хамгийн их урсгалын асуудлыг шугаман програмчлалын бодлого болгон багасгах замаар шийддэг.

Дараах тэмдэглэгээг танилцуулъя.

• n=|В| − графикийн хэмжээ (оройнуудын тоо);
• м=|Э| − графикийн үндсэн байдал (ирмэгийн тоо);
• А − Хэмжээний сүлжээний диграфын тохиолдлын матриц n× м; түүний элемент бүр a ik=1 бол би- топ гарч ирдэг к- би нум; a ik=−1, хэрэв байгаа бол бир орой орж байна к- би нум; Тэгээд a ik=0 бусад тохиолдолд; ийм матрицын багана бүрт яг нэг, нэг хасах нэг, үлдсэн нь тэг байна;
• с− сүлжээний эх үүсвэрийн оройн дугаар; Энэ оройноос зөвхөн нумууд гарч ирэх ба бусад оройд эх үүсвэрээс хүрэх боломжтой байх ёстой;
• т− сүлжээний шингээгч зангилааны дугаар; Энэ оройд зөвхөн нумууд орох ёстой бөгөөд бусад оройноос ус зайлуулах суваг гарах боломжтой байх ёстой;
• ас − с А ; энэ нь зөвхөн нэгийг агуулсан байх ёстой, учир нь эх үүсвэрээс зөвхөн нумууд гарч ирэх ёстой;
• ат − т-сүлжээний диграфын тохиолдлын матрицын-р эгнээ А ; Энэ нь зөвхөн хасахыг агуулсан байх ёстой, учир нь ус зайлуулах хоолойд зөвхөн нуманууд орох ёстой;
• А st− сүлжээний диграфын тохиолдлын матриц А тэндээс хаягдсан хүмүүстэй с th болон т th мөрүүд;
• д − уртын баганын вектор м; түүний элемент бүрт э корох урсгалын хэмжээ байх болно к th нум;
• в − уртын баганын вектор м; түүний элемент бүрт c k≥0 нь дамжуулах чадварыг тогтооно к-р нум.

Дараа нь сүлжээний хамгийн их урсгалын асуудлыг шугаман програмчлалын бодлого болгон томъёолж болно.

Эх үүсвэрээс гарах нийт урсгал (1) хамгийн их байна. Түүнчлэн, ямар ч завсрын орой дээр ирж буй урсгал нь гарч буй урсгалтай (2) тэнцүү бөгөөд нумын багтаамж хязгаарлагдмал (3) байна.

Хамгийн их урсгалтай холбоотой хоёр асуудал бол хамгийн бага зүсэлтийн асуудал юм. Хамгийн бага зүсэлтийг бий болгохын тулд та хоёрдмол байдлын теоремуудыг ашиглаж болно. Хэрэгтэй:

• сүлжээний диграфаас бүх хоосон зүйлийг арилгах ( э к= 0) ба ханасан ( э к = c k) нумууд;
• үлдсэн графикийн холбогдсон бүрэлдэхүүн хэсгүүдийг олох;
• хэрэв ийм хоёр бүрэлдэхүүн хэсэг байгаа бол хаясан нумууд нь хамгийн бага зүсэлтийг өгдөг;
• хэрэв хоёроос дээш холбогдсон бүрэлдэхүүн хэсэг гарч ирвэл сүлжээний диграф нь хэд хэдэн хамгийн бага зүсэлттэй байна (харгалзах шугаман програмчлалын асуудал нь доройтсон).

Муудсан асуудлын хувьд эх үүсвэрт хамгийн ойр байгаа эхний хамгийн бага зүсэлтийг энэ хуудсан дээр хийсэн болно.

Энэ хуудсыг зөв ашиглахын тулд таны хөтөч скриптийг дэмжих ёстой Java скрипт. Тэдгээрийг асаана уу.

Доорх оролтын талбарт анхны өгөгдлийг оруулна уу. Эхний хэсэгт сүлжээний диграфыг зурахын тулд оройнуудын координатыг оруулах шаардлагатай (илүү нарийвчлалтай, та боломжтой). Тэдгээр нь матриц хэлбэрээр тодорхойлогддог n×2: эхний баганад − x th координат, хоёрдугаарт - y-e. Тоонуудыг бүхэл тоо, аравтын бутархай эсвэл экспоненциал хэлбэрээр зааж өгч болно. Тоонуудыг зайгаар тусгаарла. НийтЭнэ оролтын талбар дахь шугамууд нь диграфын хэмжээг тодорхойлдог n- оройн тоо. Эдгээр анхны өгөгдөл (оройн координат) нь сонголттой: хэрэв тэдгээрийг заагаагүй бол сүлжээний диграфыг зөв байдлаар зурах болно. n-gon ба оройнуудын тоог дараагийн оролтын талбарт хамгийн их оройн тоогоор тодорхойлно.

Дараагийн оролтын хэсэгт зүүн тал- бөглөх шаардлагатай. Энэ нь сүлжээний диграфын бүтцийг тодорхойлдог. Диграф дахь нум бүр нь хоёр оройг холбодог. Эдгээр оройн тоог матриц хэлбэрээр зааж өгсөн болно м×2 хоёр дахь оролтын хэсгийн зүүн талд. Мөр бүр дээр эхлээд нумын 1-р оройг (сүүл, эх үүсвэр) зааж, дараа нь зайгаар дамжуулан нумын 2-р оройг (үзүүр, ус зайлуулах суваг) зааж өгнө. Эдгээр баганууд байх ёстой бүхэл тоо 1-ээс nбагтаасан. Тоонуудыг зайгаар тусгаарла. Баруун талд нумын хүчин чадлыг зааж өгсөн - эерэг бодит тоонууд. Хэрэв энэ баганыг заагаагүй бол бүх хүчин чадлыг ижил (нэг) гэж үзнэ. Эдгээр багана тус бүрийн тоонуудын нийт тоо нь диграфын хүчийг тодорхойлно м- нумын тоо.

Чиглүүлсэн график өгье G= , аль чиглэлд нуман тус бүрийн чиглэл vÎVурсгалын чиглэлийг хэлнэ (жишээлбэл, машины урсгал), нуман бүрийн багтаамж нь тэнцүү байна d(v).Олон оргил дээр Эхоёр оройг тодруулсан тТэгээд с. Орой турсгалын эх үүсвэр юм с- ус зайлуулах. Оройноос дамжуулж болох хамгийн их урсгалыг тодорхойлох шаардлагатай тВ с .

-ээр тэмдэглэе x(v)нумын дагуу хөдөлж буй урсгалын хэмжээ v. Энэ нь ойлгомжтой

0 £ x(v) £ d(v) , vÎV . (6. 1)

Оргил бүрт iÎE\(t,s)орж ирж буй урсгалын эзэлхүүн нь гарч буй урсгалын эзэлхүүнтэй тэнцүү, i.e. тэгш байдал үнэн

(х(v)|i О V + (i))= (x(v)| iО V - (i))

(x(v)| iÎV + (i)) - (x(v)| iÎV - (i))=0.(6.2)

Дээд талын хувьд т

(x(v)| iÎV + (i)) -(x(v)¦ iÎV - (i))=-Q,(6.3)

оройн хувьд s

(x(v)| iО V + (i)) -(x(v)¦ i О V - (i))= Q.(6.4)

Хэмжээ Qоройгоос гарах урсгалын хэмжээ тмөн дээд хэсэгт ордог с.

Тодорхойлох хэрэгтэй

Q ® хамгийн их(6.5)

хязгаарлалттай (6.1-6.4).

Тоо хэмжээ Q, x(v) , vÎV,хангасан хязгаарлалт (6.1-6.4) бид сүлжээн дэх урсгалыг дуудах бөгөөд хэрэв тэдгээр нь утгыг нэмэгдүүлэх юм бол Q, дараа нь хамгийн их урсгал. Үнэт зүйл гэдгийг харахад хялбар байдаг Q=0, x(v)=0, vÎV, сүлжээн дэх урсгал юм.

Бодлого (6.1-6.5) нь шугаман програмчлалын бодлого бөгөөд симплекс аргын алгоритмуудыг ашиглан шийдэж болно.

Е оройн олонлогийг ийм байдлаар Е1 ба Е2 салангид хоёр хэсэгт хуваацгаая tÎE1, sÎE2. Зүсэх замаар V(E1,E2), тусгаарлах тТэгээд сБид багцыг дуудах болно V(E1,E2)ÌVнуман тус бүрийн хувьд v О V(E1,E2)эсвэл h1(v)ОE1Тэгээд h2(v)ОE2, эсвэл h1(v)ОE2Тэгээд h2(v)ОE1.

Багцаа хувааж авцгаая V(E1,E2)хоёр хэсэгт хуваана V(E1,E2,+),V(E1,E2,-)дараах байдлаар:

V(E1,E2,+)=(vÎV(E1,E2)| h1(v)ÎE1Тэгээд h2(v)ОE2)

V(E1,E2,-)= ( vÎV(E1,E2)| h2(v)ÎE1Тэгээд h1(v)ОE2)

Бид зүсэлтийн нэвтрүүлэх чадварыг дуудах болно

Q(E1,E2) = (x(v)| vÎV(E1,E2,+))-(x(v)| vÎV(E1,E2,-))

Дараах нь үнэн юм

Теорем 1. (Хамгийн их урсгал ба хамгийн бага зүсэлтийн тухай).

Аливаа сүлжээнд эх үүсвэрээс гарах хамгийн их урсгал нь тнөөцлөх схамгийн бага дамжуулах чадвартай тэнцүү байна Q(E1,E2)бүх хасах дунд V(E1,E2), оройнуудыг тусгаарлах тТэгээд с.

Хамгийн их урсгалтай гэдгийг анхаарна уу

x(v)=d(v) , vÎV(E1,E2,+),

x(v)=0 , vÎV(E1,E2,-).

Болъё Q, x(v), vÎV, -зарим сүлжээний урсгал, дараалал

t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,

оройг холбосон гинж юм тТэгээд с. Энэ гинжин хэлхээнд оройноос хөдөлгөөний чиглэлийг тогтооцгооё труу с. Нуман v(j)энэ гинжнээс гарах чиглэл нь хөдөлгөөний чиглэлтэй давхцаж байвал шулуун шугам гэж нэрлэдэг труу с, мөн эсрэгээр. Бид энэ гинжийг зам гэж нэрлэх болно урсгал нэмэгдэж байна, хэрэв шулуун нумын хувьд vгинж x(v)< d(v) мөн урвуу x(v) > 0. Энэ хэлхээгээр нэмэлт урсгалыг дамжуулж болно q-аас труу схэмжээ q = мин(q1,q2),Хаана q1=мин (d(v) -x(v)), хамгийн бага нь гинжин хэлхээний бүх шулуун нуман дээр авсан, q1=мин (x(v)), хамгийн бага нь гинжин хэлхээний бүх урвуу нумыг авна.

Теорем 2.

Урсгал Q, x(v) , vÎV, урсгалыг нэмэгдүүлэх арга байхгүй тохиолдолд л хамгийн их байна.

Сүлжээний хамгийн их урсгалын асуудлыг шийдэх алгоритм нь сүлжээний урсгалыг нэмэгдүүлэх арга замыг олоход суурилдаг. тВ с, энэ нь эргээд оройн шошгыг цэгцлэх процесс дээр суурилдаг. Ингэж хэлье

орой битэмдгээр тэмдэглэсэн q(i)>0, мөн шулуун нуман нум нь мөн мэдэгдэж байна v(i), үүгээр дамжин энэ урсгал ирсэн, эсвэл тэмдэглэгдсэн байна , хэрвээ зарим нэмэлт урсгалын хэмжээ q(i)>0, мөн урвуу нум нь бас мэдэгдэж байна v(i), үүгээр дамжин энэ урсгал орж ирсэн;

Хэрэв хөрш зэргэлдээх бүх оройнууд нь тэмдэглэгдсэн бол i оройг харна.

Хэрэв оройн s тэмдэглэгдсэн бол урсгалыг хэмжээгээр нэмэгдүүлэх зам олдсон байна q, энэ замаар дамждаг. Алгоритмыг тайлбарлахын тулд бидэнд массив хэрэгтэй SPW, тэмдэглэгдсэн оройнуудын дугаарыг тэмдэглэсэн дарааллаар нь агуулна. C1- массив дахь дугаар SPWүзсэн оргил, C2- энэ массив дахь хамгийн сүүлд тэмдэглэгдсэн оройн дугаар.

Энэхүү алгоритмын санаа нь эх үүсвэрээс угаалтуур хүртэлх эерэг урсгал бүхий төгсгөл хүртэлх замыг олох явдал юм.

(Анхны) багтаамжтай ирмэгийг (i, j) авч үзье. Алгоритмыг гүйцэтгэх явцад энэ хүчин чадлын зарим хэсгийг өгөгдсөн ирмэгээр дамжин өнгөрөх урсгалаар "авдаг" бөгөөд үүний үр дүнд ирмэг бүр нь үлдэгдэл багтаамжтай байх болно. Бичих - үлдэгдэл зурвасын өргөн. Бүх ирмэгүүд нь үлдэгдэл багтаамжтай сүлжээг үлдэгдэл гэж нэрлэнэ.

i зангилаанаас урсгалыг хүлээн авч буй дурын j зангилааны хувьд бид тэмдэглэгээг тодорхойлно, үүнд j зангилаанаас i зангилаа руу урсах урсгалын утга байна. Хамгийн их урсгалыг олохын тулд бид дараах алхмуудыг гүйцэтгэдэг.

Бүх ирмэгийн хувьд бид үлдэгдэл хүчин чадлыг анхны хүчин чадалтай тэнцүү гэж тогтоосон, өөрөөр хэлбэл. = тэнцүү гэж үзье. 1-р зангилааг шошготойгоор оноож тэмдэглэе. Бид i=1 гэж таамаглаж байна.

Бүх j-д эерэг үлдэгдэл багтаамж >0 бүхий ирмэгийн дагуу I зангилаанаас очиж болох j зангилааны багц. Хэрэв бид 3-р үе шатыг хийвэл, үгүй ​​бол бид 4-т очно.

Бид k зангилаанаас ийм зүйлийг олдог. Бид k зангилааг шошготой байрлуулж тэмдэглэе. Хэрэв k=n бол төгсгөл хоорондын зам олдож, 5-р шат руу явна, үгүй ​​бол i=k гэж тохируулаад 2-р шат руу буцна.

Буцаах. Хэрэв i=1 бол төгсгөл хоорондын зам боломжгүй бөгөөд 6 руу очно уу. Хэрэв i зангилааны өмнөхөн хаяглагдсан r зангилаа олоод r зангилааны зэргэлдээх зангилааны багцаас хасна. Бид i=r гэж тохируулаад 2-р шат руу буцна.

Үлдэгдэл сүлжээний тодорхойлолт. Эх үүсвэрийн зангилаа (зангилаа 1) -ээс угаалтуур (зангилаа n) хүртэлх төгсгөлийн замыг олсон зангилааны багцаар тэмдэглэцгээе

Төгсгөл хүртэлх замыг бүрдүүлдэг ирмэгүүдийн үлдэгдэл багтаамж нь урсгалын чиглэлд тодорхой хэмжээгээр буурч, эсрэг чиглэлд ижил хэмжээгээр нэмэгддэг.

Тэр. Төгсгөлийн замд багтсан ирмэгийн (i, j) хувьд одоогийн үлдэгдэл хүчин чадал өөрчлөгдөнө.

1) хэрэв урсгал i зангилаанаас j хүртэл явбал,

2) хэрэв урсгал j зангилаанаас i хүртэл явбал.

a) m төгсгөл хоорондын зам олдвол хамгийн их урсгалыг дараах байдлаар илэрхийлнэ

б) Ирмэгийн эхний ба эцсийн хүчин чадлын утгыг (i, j) авч үзвэл бид энэ ирмэгээр дамжин өнгөрөх оновчтой урсгалыг дараах байдлаар тооцоолж болно. Үүнийг тавья. Хэрэв >0 бол ирмэгээр (i, j) дамжин өнгөрөх урсгал тэнцүү байна. Хэрэв >0 бол урсгал тэнцүү байна. (>0 ба >0 аль аль нь боломжгүй тохиолдолд).

Жишээ 1. Сүлжээний хамгийн их урсгалыг ол Зураг. 1

Давталт 1. =

3) k=3, учир нь. Бид 3-р зангилааг шошготойгоор оноож, тэмдэглэнэ. i=3 ба 2 руу буцах)

5) k=5 ба. Бид 5-р зангилааг шошгоор тэмдэглэнэ. Бид дамжин өнгөрөх замыг олж авдаг.

6) бид төгсгөл хүртэлх замыг 5-р зангилаанаас эхлээд 1-р зангилаагаар төгсөх шошгооор тодорхойлно: . Тэгээд. Бид зам дээрх үлдэгдэл хүчин чадлыг тооцоолно.

Давталт 2.

1) ба зангилаа 1-ийг шошгоор тэмдэглэнэ. i=1

2") (тиймээс 5-р зангилааг оруулаагүй болно

3") k=4 ба зангилаа 4-ийг шошгон дээр тэмдэглэнэ. i=4 ба 2 руу буцах)

2""") (1 ба 3-р зангилаа тэмдэглэгдсэн тул тэдгээрийг оруулаагүй болно)

3""") k=5 ба. Бид 5-р зангилааг шошгон дээр тэмдэглэнэ. Төгсгөл хүртэлх замыг олж авна. 5 руу очно уу)

Давталт 3.

1) ба зангилаа 1-ийг шошгоор тэмдэглэнэ. i=1

3) k=2, зангилаа 2-ыг шошгон дээр тэмдэглэнэ. i=2 ба 2 руу буцах)

3") k=3 ба. 3-р зангилааг шошготой тэмдэглэнэ. i=3 ба 2 руу буцна уу)

2") (үүнээс хойш) 4 рүү очно уу)

4) 3-р зангилааны шошго нь өмнөх зангилааны дугаарыг харуулна. Энэ давталт дээр 3-р зангилаа цаашид анхааралдаа авахгүй бөгөөд түүний шошгыг зурсан болно. 2 руу буцах)

2""") (3-р зангилаа төгсгөл хүртэлх замаас хасагдсан тул)

3""") ба. Бид 5-р цэгийг шошготойгоор тэмдэглэнэ. Төгсгөл хүртэлх замыг олж авна. 5 руу очно уу)

5) би. Бид зам дээрх үлдэгдэл хүчин чадлыг тооцоолно.

Давталт 4. Энэ давталт дээр зам нь

Давталт 5. Энэ давталт дээр зам нь

Давталт 6: 1-р зангилаанаас үүссэн бүх ирмэгүүд тэг үлдэгдэл багтаамжтай тул шинэ төгсгөл хоорондын зам боломжгүй. Шийдлийг тодорхойлохын тулд 6) руу очно уу

6) сүлжээн дэх урсгалын хамгийн их хэмжээ нь нэгжтэй тэнцүү байна.

Төрөл бүрийн ирмэгийн дагуух урсгалын утгыг анхны хүчин чадлын утгаас хамгийн сүүлийн үлдэгдэл хүчин чадлын утгыг хасч тооцдог.

Тооцооллын үр дүн: хүснэгт. 1

Хамгийн их урсгалыг олох алгоритмын график дараалсан гүйцэтгэл (жишээ 1)

e) е) Дамжуулах зам байхгүй

Цагаан будаа.

Тээврийн системийн талаархи анхны мэдээлэл, жишээлбэл, үйлдвэр доторх, Зураг дээр үзүүлэв. 2, мөн хүснэгтээр тодорхойлж болно (Хүснэгт 2).

Хүснэгт 2. Хамгийн их урсгалын асуудлын анхны өгөгдөл

Тээврийн системийн хамгийн дээд хүчин чадал нь 6-аас хэтрэхгүй, учир нь 0-р цэгээс 6-аас илүүгүй ачаа, тухайлбал 1-р цэг хүртэл 2 нэгж, 2-р цэг хүртэл 3 нэгж, 3-р цэг хүртэл 1 нэгж ачаа илгээх боломжтой. Дараа нь 0 цэгээс гарах 6 нэгж ачаа бүгд эцсийн цэг 4-т хүрсэн эсэхийг шалгах шаардлагатай. 1-р цэгт ирсэн 2 нэгж ачааг 4-р цэг рүү шууд илгээх боломжтой. 2-р цэгт ирсэн ачааг . хуваах шаардлагатай: 2 нэгжийг нэн даруй 4-р цэг рүү, 1 нэгжийг - 3-р завсрын цэг рүү (2 ба 4-р цэгүүдийн хоорондох хэсгийн багтаамж хязгаарлагдмал тул) илгээнэ. Дараах ачааг 3-р цэгт хүргэсэн: 0-р цэгээс 1 нэгж, 3-р цэгээс 1 нэгж. Бид тэдгээрийг 4-р цэг рүү илгээдэг. Тиймээс тээврийн системийн хамгийн их нэвтрүүлэх чадвар нь 6 нэгж ачаа юм. Энэ тохиолдолд 1-ээс 2-р цэгийн хоорондох дотоод хэсгүүдийг (салбарууд), түүнчлэн 1-ээс 3-р цэгүүдийн хоорондох салбарыг бүрэн ачаагүй - 2 нэгж ачааг түүнтэй хамт илгээдэг. дамжуулах чадвар 3 нэгж. Шийдлийг хүснэгт хэлбэрээр танилцуулж болно (Хүснэгт 3)

Хүснэгт 3. Хамгийн их урсгалын асуудлыг шийдэх

Урсгалыг нэмэгдүүлэх шугаман програмчлалын асуудал.Шугаман програмчлалын хувьд хамгийн их урсгалын бодлогыг томъёолъё. K цэгээс М цэг хүртэлх тээвэрлэлтийн эзэлхүүнийг X KM гэж үзье. Зураг. 2 K = 0,1,2,3, M = 1,2,3,4, тээвэрлэлт нь зөвхөн өндөр тоотой цэг хүртэл боломжтой. Энэ нь X KM нийт 9 хувьсагчтай гэсэн үг, тухайлбал X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, X 34. Шугаман програмчлалын бодлого нь хамгийн их байлгахад чиглэгдсэн. урсгал нь дараах хэлбэртэй байна.

X 01 + X 02 + X 03 = F (0)

X 01 + X 12 + X 13 + X 14 = 0 (1)

X 02 - X 12 + X 23 + X 24 = 0 (2)

X 03 - X 13 - X 23 + X 34 = 0 (3)

X 14 - X 24 - X 34 = - F (4)

X KM? 0, K, M = 0, 1, 2, 3, 4

Энд F нь зорилгын функц, нөхцөл (0) нь тээврийн системд бараа орохыг тодорхойлдог. Нөхцөл (1) - (3) системийн 1-3 дугаар зангилааны тэнцвэрийн харьцааг тогтооно. Өөрөөр хэлбэл, дотоод зангилаа бүрийн хувьд орж ирж буй барааны урсгал нь систем дотор хуримтлагддаггүй бөгөөд тэнд "төрдөггүй" байдаг. Нөхцөл (4) нь системээс ачааллыг "гарах" нөхцөл юм. Нөхцөл (0)-ын хамт энэ нь системийн бүхэлдээ тэнцвэрийн харьцааг бүрдүүлдэг ("оролт" нь "гаралт"-тай тэнцүү). Дараах есөн тэгш бус байдал нь тээврийн системийн бие даасан "салбар"-ын хүчин чадлыг хязгаарладаг. Дараа нь хөдөлгөөний хэмжээ, зорилгын функцийн сөрөг бус байдлыг харуулав. Сүүлчийн тэгш бус байдал нь зорилгын функцийн хэлбэр (харилцаа (0) эсвэл (4)) болон хөдөлгөөний эзлэхүүний сөрөг бус байдлаас үүдэлтэй нь тодорхой байна. Гэсэн хэдий ч сүүлчийн тэгш бус байдал нь зарим зүйлийг агуулдаг ерөнхий мэдээлэл- ачааны эерэг эзэлхүүнийг системээр дамжуулж болно, эсвэл тэг (жишээлбэл, систем дотор тойрог хөдөлгөөн байгаа бол) сөрөг биш (энэ нь эдийн засгийн утгагүй, гэхдээ албан ёсны) математик загварЭнэ талаар "мэдэхгүй").

Нуман дамжих урсгалын нийлбэр v, нь нуман дамжих урсгалын нийлбэртэй тэнцүү байна w; энэ нийлбэрийг урсгалын утга гэж нэрлэдэг. Бид юуны түрүүнд хамгийн их урсгал гэж нэрлэгддэг хамгийн их утгатай урсгалыг сонирхох болно. IN ерөнхий тохиолдолсүлжээ нь хэд хэдэн өөр өөр хамгийн их урсгалтай байж болох ч тэдгээрийн утга нь ижил байх ёстой. (4)

N = (V,D,a) сүлжээгээр дамжих хамгийн их урсгалын судалгаа нь огтлолын тухай ойлголттой нягт холбоотой, i.e. ямар ч энгийн гинжин хэлхээний шинж чанарыг агуулсан диграф D нумын ийм А олонлог vВ А-д хамаарах нумыг дайран өнгөрнө.Зүсэлтийн багтаамж нь түүнд хамаарах нумын багтаамжийн нийлбэр юм. Боломжит хамгийн бага дамжуулалттай зүсэлтийг хамгийн бага зүсэлт гэж нэрлэдэг.

Аливаа урсгалын хэмжээ нь ямар ч зүсэлтийн дамжуулах чадвараас хэтрэхгүй, тиймээс хамгийн их урсгалын хэмжээ нь хамгийн бага зүсэлтийн дамжуулах чадвараас хэтрэхгүй. Гэсэн хэдий ч энэ хоёр нь тодорхойгүй байна сүүлийн тоонуудүргэлж бие биетэйгээ тэнцүү байх; Энэ үр дүнг Америкийн математикч Форд, Фулкерсон нар 1955 онд гаргаж, хамгийн их урсгал ба хамгийн бага зүсэлтийн теорем гэж нэрлэжээ.

Теорем (хамгийн их урсгал ба хамгийн бага зүсэлтийн тухай). Аливаа сүлжээнд хамгийн их урсгалын хэмжээ нь хамгийн бага зүсэлтийн хүчин чадалтай тэнцүү байна.

Хамгийн их урсгал ба хамгийн бага зүсэлтийн теорем нь өгөгдсөн урсгал нь хамгийн их эсвэл үгүй ​​эсэхийг шалгах боломжийг олгодог, гэхдээ зөвхөн маш энгийн сүлжээнүүдийн хувьд. Мэдээжийн хэрэг, бодит байдал дээр бид том, нарийн төвөгтэй сүлжээнүүдтэй харьцах ёстой бөгөөд ерөнхийдөө энгийн сонголтоор хамгийн их урсгалыг олоход хэцүү байдаг. Бүхэл тоо дамжуулах чадвартай аль ч сүлжээнд хамгийн их урсгалыг олох нэг алгоритмыг тайлбарлая.

1-р алхам. Эхлээд тэгээс өөр утгатай урсгалыг сонгоё (хэрэв ийм урсгал байгаа бол). Жишээлбэл, хэрэв N нь зурагт үзүүлсэн сүлжээ юм. 29.3, дараа нь зурагт үзүүлсэн урсгал. 29.4. Бидний сонгосон анхны урсгалын утга их байх тусам дараагийн алхамууд хялбар байх болно гэдгийг тэмдэглэх нь зүйтэй.

Алхам 2. N дээр үндэслэн бид урсгалын чиглэлийг эсрэгээр нь өөрчилснөөр N’ шинэ сүлжээг байгуулна. Нарийвчилж хэлэхэд (a) = 0 байх аливаа а нум нь N'-д анхны хүчин чадлаараа үлдэж, ямар ч а нум нь багтаамжтай a нумаар, (a) багтаамжтай эсрэг талын нумаар солигдоно. Бидний жишээн дээрх N сүлжээг Зураг дээр үзүүлэв. 29.5. Орой vэх үүсвэр байхаа больж, угаалтуур болжээ.

Алхам 3. Хэрэв N' сүлжээнд бид тэгээс ялгаатай урсгалыг олж чадна vв, дараа нь энэ нь анхны урсгалд нэмж, N-д илүү том утгатай шинэ урсгалыг авч болно. Одоо та сүлжээг байгуулахдаа N'-ийн оронд N' шинэ утсыг ашиглан 2-р алхамыг давтаж болно. Энэ процедурыг давтснаар бид эцэст нь тэгээс өөр урсгалгүй N' сүлжээнд хүрэх болно; дараа нь харгалзах урсгал нь хамгийн их урсгал байх болно. Жишээлбэл, Зураг дээр. 29.5 нуман дундуур урсдаг тэгээс өөр урсгал байдаг ( v, u), (у,з), (z,x), (x,y) ба ( у,) нь нэгтэй тэнцүү бөгөөд үлдсэн нумуудаар дамжин өнгөрөх урсгалууд нь тэгтэй тэнцүү байна. Зураг дээрх урсгалд энэ урсгалыг нэмбэл. 29.4, бид зурагт үзүүлсэн урсгалыг олж авна. 29.6; 2-р алхамыг давтах нь энэ нь хамгийн их урсгал гэдгийг харуулахад хялбар юм.

Ашигласан номууд:

(1) http://pgap.chat.ru/zap/zap264.htm#0

(2) Асанов М.О., Баранский В.А., Расин В.В. Дискрет математик: матроид график, алгоритм

(3) Басакер Р., Саати Т. Төгсгөлийн график ба сүлжээ.

(4) Вилсон Р. Графикийн онолын танилцуулга