Тогтмол урттай замын тоо / Тогтмол урттай хамгийн богино зам¶

Дараах өгүүлэлд ижил санаан дээр суурилсан эдгээр хоёр бодлогын шийдийг тайлбарлана: бодлогыг матриц байгуулах болтол хураагаад шийдийг ердийн матрицын үржвэр эсвэл өөрчилсөн үржвэрээр тооцоолно.

Тогтмол урттай замын тоо¶

Бидэнд $n$ оройтой чиглэлтэй, жингүй граф $G$ ба бүхэл тоо $k$ өгөгдсөн. Даалгавар нь дараах байдалтай: оройн хос $(i, j)$ бүрийн хувьд бид эдгээр оройн хоорондох $k$ урттай замын тоог олох ёстой. Замууд энгийн байх албагүй, өөрөөр хэлбэл нэг зам дотор орой ба ирмэгүүдэд дурын тоогоор зочилж болно.

Бид графыг adjacency matrix буюу $n \times n$ хэмжээтэй $G[][]$ матрицаар өгсөн гэж үзнэ, энд элемент бүр $G[i][j]$ нь $i$ орой $j$-тэй ирмэгээр холбогдсон бол $1$, ирмэгээр холбогдоогүй бол $0$ байна. Дараах алгоритм олон ирмэгийн тохиолдолд ч ажиллана: хэрэв оройн ямар нэг хос $(i, j)$ нь $m$ ирмэгээр холбогдсон бол бид үүнийг adjacency matrix-д $G[i][j] = m$ гэж тохируулан тэмдэглэж болно. Мөн граф гогцоо (гогцоо гэдэг нь оройг өөртэй нь холбох ирмэг) агуулж байвал алгоритм ажиллана.

Байгуулсан adjacency matrix нь $k = 1$ тохиолдлын хувьд бодлогын хариулт болох нь илэрхий. Энэ нь оройн хос бүрийн хоорондох $1$ урттай замын тоог агуулна.

Бид шийдийг итерацаар байгуулна: Бид ямар нэг $k$-ийн хувьд хариултыг мэдэж байна гэж үзье. Энд бид $k + 1$-ийн хувьд хариултыг хэрхэн байгуулж болох аргыг тайлбарлана. $k$ тохиолдлын матрицыг $C_k$, бидний байгуулахыг хүсэж буй матрицыг $C_{k+1}$ гэж тэмдэглэе. Дараах томьёогоор бид $C_{k+1}$-ийн элемент бүрийг тооцоолж болно:

$$C_{k+1}[i][j] = \sum_{p = 1}^{n} C_k[i][p] \cdot G[p][j]$$

Энэ томьёо $C_k$ ба $G$ матрицуудын үржвэрээс өөр юу ч тооцоолохгүйг харахад амархан:

$$C_{k+1} = C_k \cdot G$$

Ингэснээр бодлогын шийдийг дараах байдлаар илэрхийлж болно:

$$C_k = \underbrace{G \cdot G \cdots G}_{k \text{ times}} = G^k$$

Матрицын үржвэрийг Хоёртын зэрэгт дэвшүүлэлт ашиглан өндөр зэрэгт үр ашигтай дэвшүүлж болохыг тэмдэглэх нь үлдэж байна. Энэ нь $O(n^3 \log k)$ complexity-тэй шийд өгнө.

Тогтмол урттай хамгийн богино зам¶

Бидэнд $n$ оройтой чиглэлтэй жинтэй граф $G$ ба бүхэл тоо $k$ өгөгдсөн. Оройн хос $(i, j)$ бүрийн хувьд бид яг $k$ ирмэгээс бүрдэх $i$ ба $j$-ийн хоорондох хамгийн богино замын уртыг олох ёстой.

Бид графыг adjacency matrix буюу $n \times n$ хэмжээтэй $G[][]$ матрицаар өгсөн гэж үзнэ, энд элемент бүр $G[i][j]$ нь $i$ оройноос $j$ орой хүртэлх ирмэгийн уртыг агуулна. Хэрэв хоёр оройн хооронд ирмэг байхгүй бол матрицын харгалзах элементэд төгсгөлгүй $\infty$ оногдоно.

Энэ хэлбэрээр adjacency matrix нь $k = 1$-ийн хувьд бодлогын хариулт болох нь илэрхий. Энэ нь оройн хос бүрийн хоорондох хамгийн богино замын уртыг, эсвэл нэг ирмэгээс бүрдэх зам байхгүй бол $\infty$-г агуулна.

Дахин бид бодлогын шийдийг итерацаар байгуулж болно: Бид ямар нэг $k$-ийн хувьд хариултыг мэдэж байна гэж үзье. Бид $k+1$-ийн хувьд хариултыг хэрхэн тооцоолохыг үзүүлнэ. $k$-ийн матрицыг $L_k$, бидний байгуулахыг хүсэж буй матрицыг $L_{k+1}$ гэж тэмдэглэе. Тэгвэл дараах томьёо $L_{k+1}$-ийн элемент бүрийг тооцоолно:

$$L_{k+1}[i][j] = \min_{p = 1 \ldots n} \left(L_k[i][p] + G[p][j]\right)$$

Энэ томьёог нарийн харвал бид матрицын үржвэртэй ижил төстэй байдлыг гаргаж болно: үнэндээ $L_k$ матрицыг $G$ матрицаар үржүүлж байна, цорын ганц ялгаа нь үржих үйлдэлд бид нийлбэрийн оронд хамгийн багыг, дотоод үйлдэл болгон үржүүлэхийн оронд нийлбэрийг авдагт оршино.

$$L_{k+1} = L_k \odot G,$$

энд $\odot$ үйлдлийг дараах байдлаар тодорхойлно:

$$A \odot B = C~~\Longleftrightarrow~~C_{i j} = \min_{p = 1 \ldots n}\left(A_{i p} + B_{p j}\right)$$

Ингэснээр даалгаврын шийдийг өөрчилсөн үржвэр ашиглан илэрхийлж болно:

$$L_k = \underbrace{G \odot \ldots \odot G}_{k~\text{times}} = G^{\odot k}$$

Өөрчилсөн үржвэр нь илэрхий associativity-тэй тул бид энэ зэрэгт дэвшүүлэлтийг мөн Хоёртын зэрэгт дэвшүүлэлтээр үр ашигтай тооцоолж болохыг тэмдэглэх нь үлдэж байна. Тиймээс энэ шийд ч мөн $O(n^3 \log k)$ complexity-тэй.

Урт нь $k$ хүртэл байх замуудын хувьд бодлогуудыг ерөнхийлөх¶

Дээрх шийдүүд тогтмол $k$-ийн хувьд бодлогуудыг бодно. Гэвч шийдүүдийг замууд $k$-аас илүүгүй ирмэг агуулахыг зөвшөөрдөг бодлогуудыг бодоход тохируулж болно.

Үүнийг оролтын графыг бага зэрэг өөрчлөх замаар хийж болно.

Бид орой бүрийг хуулбарлана: орой $v$ бүрийн хувьд бид өөр нэг орой $v'$ үүсгээд $(v, v')$ ирмэг ба $(v', v')$ гогцоог нэмнэ. Хамгийн ихдээ $k$ ирмэгтэй $i$ ба $j$-ийн хоорондох замын тоо нь яг $k + 1$ ирмэгтэй $i$ ба $j'$-ийн хоорондох замын тоотой ижил тоо байна, учир нь $m \le k$ урттай зам бүр $[p_0 = i,~p_1,~\ldots,~p_{m-1},~p_m = j]$-г $k + 1$ урттай зам $[p_0 = i,~p_1,~\ldots,~p_{m-1},~p_m = j, j', \ldots, j']$-д буулгах биекц байдаг.

Хамгийн ихдээ $k$ ирмэгтэй хамгийн богино замыг тооцоолоход ижил заль мэхийг хэрэглэж болно. Бид дахин орой бүрийг хуулбарлаж, дурдсан хоёр ирмэгийг $0$ жинтэйгээр нэмнэ.