An ant performs a uniform random walk on a \(5\times5\) grid. Initially the five bottom-row cells each contain one seed, the five top-row cells are empty, and the ant starts at the center \((2,2)\). If the ant is not carrying a seed and reaches a bottom cell that still contains one, it picks it up immediately. If it is carrying a seed and reaches an empty top cell, it drops the seed immediately. We want the expected number of steps until all five seeds have been transported to the top row.
A naive Markov state would record the ant position together with the exact locations of all five seeds. That is far more detailed than necessary, because seeds only matter when they sit in the bottom row waiting to be picked up, or in the top row after being delivered.
So a state is completely described by:
$$B\subseteq\{0,1,2,3,4\}\quad\text{: columns whose bottom seed is still present},$$
$$T\subseteq\{0,1,2,3,4\}\quad\text{: columns already occupied in the top row},$$
the ant position \(p\in\{0,\dots,24\}\), and a carrying flag.
The code stores \(B\) and \(T\) as 5-bit masks. This is already a major reduction: there are only \(25\) possible positions and \(32\) masks per row.
When the ant is not carrying, every undelivered seed is still sitting at the bottom, and every delivered seed already occupies one top slot. Therefore
$$|B|+|T|=5.$$
When the ant is carrying, one seed has already been removed from the bottom but has not yet been placed on the top, so
$$|B|+|T|=4.$$
This gives the exact set of valid compressed states. Their counts are
$$25\sum_{t=0}^{5}\binom{5}{t}\binom{5}{5-t}=25\binom{10}{5}=6300$$
for non-carrying states, and
$$25\sum_{t=0}^{4}\binom{5}{t}\binom{5}{4-t}=25\binom{10}{4}=5250$$
for carrying states, for a total of
$$6300+5250=11550$$
compressed Markov states. The code does not solve one giant \(11550\times11550\) linear system. It uses a better decomposition.
Suppose the current state is \((B,T,p,\text{not carrying})\). Then the next meaningful event is:
the first time the random walk hits one of the active bottom cells
$$bot(B)=\{b_j:\ j\in B\},$$
where \(b_j\) is the bottom cell in column \(j\).
Similarly, in a carrying state \((B,T,p,\text{carrying})\), the next meaningful event is the first time the walk hits one of the still-empty top cells
$$top(\overline T)=\{t_j:\ j\notin T\},$$
where \(t_j\) is the top cell in column \(j\).
This jump is exact, not heuristic. Let \(\tau\) be that first hitting time. By the strong Markov property of the random walk, once the process reaches the event cell, the future depends only on the new compressed state, not on the detailed path used to get there. So we may split the expectation into:
expected travel time to the next event
plus
expected continuation value from the event state.
Fix any target set \(S\) contained in the top row or bottom row. For each start cell \(u\), define
$$H_u^{S}=\mathbb E_u[\tau_S],$$
where \(\tau_S\) is the first time the walk hits \(S\). Also define, for each target column \(j\),
$$P_{u\to j}^{S}=\Pr_u(\text{the first hit in }S\text{ occurs at the target cell in column }j).$$
These are determined by first-step decomposition. If \(u\in S\), then the hitting time is already zero. If \(u\notin S\), the first move consumes one step and then averages over neighbors:
$$H_u^{S}=\begin{cases} 0,&u\in S,\\ 1+\dfrac1{\deg(u)}\sum_{v\sim u}H_v^{S},&u\notin S. \end{cases}$$
Likewise, the first-hit-column probabilities satisfy
$$P_{u\to j}^{S}=\begin{cases} 1,&u\text{ is the target cell of column }j,\\ 0,&u\in S\text{ but in a different target column},\\ \dfrac1{\deg(u)}\sum_{v\sim u}P_{v\to j}^{S},&u\notin S. \end{cases}$$
The important structural point is that the coefficient matrix is the same for all right-hand sides. So for each mask the code solves one \(25\times25\) system with 6 right-hand sides: one for the expected time and five for the first-hit probabilities of the five columns.
Let \(E_{nc}(B,T,p)\) be the expected remaining number of steps from a non-carrying state, and \(E_c(B,T,p)\) the corresponding quantity from a carrying state.
If the ant is not carrying, the next event is the first hit of \(bot(B)\). Therefore
$$E_{nc}(B,T,p)=H_p^{bot(B)}+\sum_{j\in B}P_{p\to j}^{bot(B)}\,E_c(B\setminus\{j\},T,b_j).$$
The term \(H_p^{bot(B)}\) counts the expected number of ordinary walk steps until pickup. The sum averages over which bottom seed is picked up first. After reaching \(b_j\), the seed is removed from the bottom immediately, so the next state is carrying with bottom mask \(B\setminus\{j\}\).
If the ant is carrying, the next event is the first hit of an empty top slot. Hence
$$E_c(B,T,p)=H_p^{top(\overline T)}+\sum_{j\notin T}P_{p\to j}^{top(\overline T)}\,E_{nc}(B,T\cup\{j\},t_j).$$
Again, the first term is the expected travel time until drop, and the sum averages over which empty top column is reached first. Once \(t_j\) is reached, that top slot becomes occupied immediately.
The carrying recurrence increases \(|T|\) by one:
$$E_c(\cdots,T,\cdots)\longrightarrow E_{nc}(\cdots,T\cup\{j\},\cdots).$$
The non-carrying recurrence keeps \(|T|\) unchanged:
$$E_{nc}(\cdots,T,\cdots)\longrightarrow E_c(\cdots,T,\cdots).$$
So if we process states by
$$top\_count=|T|$$
from \(4\) down to \(0\), then:
carrying states at level \(top\_count\) depend only on non-carrying states at level \(top\_count+1\), which are already known;
non-carrying states at level \(top\_count\) depend only on carrying states at the same level, which have just been computed.
That is why the code has a simple layer-by-layer order and never needs iterative relaxation.
When all five seeds have already been delivered, we must be in a non-carrying state with
$$B=\varnothing,\qquad T=\{0,1,2,3,4\}.$$
No further steps are needed, so
$$E_{nc}(\varnothing,\text{full},p)=0$$
for every position \(p\).
The initial state is
$$B=\text{full},\qquad T=0,\qquad p=\text{center},\qquad \text{not carrying},$$
so the answer is
$$E_{nc}(\text{full},0,\text{center}).$$
Suppose only one bottom seed remains, in column \(s\), and only one top slot is still empty, in column \(t\). Then there is no branching left.
If the ant is non-carrying at position \(p\), it must first hit \(b_s\), pick up the seed, and then hit \(t_t\). Therefore
$$E_{nc}(\{s\},\text{full}\setminus\{t\},p)=H_p^{\{b_s\}}+H_{b_s}^{\{t_t\}}.$$
If the ant is already carrying, then only the second part remains:
$$E_c(\varnothing,\text{full}\setminus\{t\},p)=H_p^{\{t_t\}}.$$
The program checks exactly these identities numerically for every choice of \(s\), \(t\), and \(p\). This is a strong checkpoint because it tests both the hitting systems and the event-level DP.
1) Grid construction. build_grid() stores the neighbors and degrees of the 25 cells.
2) Linear algebra core. solve_hitting_data() builds the common coefficient matrix for a target mask on the top or bottom row. solve_linear_system() performs Gaussian elimination with partial pivoting.
3) Precomputation. For every nonempty mask, the code stores hitting-time and first-hit-column data for top targets and bottom targets separately.
4) DP tables. expected_nc[bottom_mask][top_mask][pos] and expected_c[...] implement the two recurrences above.
5) Layer order. The loop over top_count runs from 4 down to 0. For each layer the carrying table is filled first, then the non-carrying table.
6) Checkpoints. The code verifies two invariants: the hit probabilities for an active target mask always sum to \(1\), and the one-seed formulas above agree with the DP tables.
There are only \(31\) nonempty masks per row that need hitting data. Each one solves a \(25\times25\) linear system with 6 right-hand sides, which is tiny. After that, the dynamic program visits only the valid \((B,T,p)\) states described above. So the computation is exact enough for floating-point arithmetic and dramatically smaller than solving a single giant Markov-chain system on the full state space.
Eine Ameise läuft gleichverteilt zufällig auf einem \(5\times5\)-Gitter. Anfangs liegt in jeder Zelle der unteren Zeile ein Samen, die obere Zeile ist leer, und die Ameise startet im Zentrum \((2,2)\). Ohne Last nimmt sie beim Erreichen einer unteren Zelle mit vorhandenem Samen diesen sofort auf; mit Last legt sie ihn beim Erreichen einer noch freien oberen Zelle sofort ab. Gesucht ist der Erwartungswert der Schrittzahl, bis alle fünf Samen nach oben transportiert wurden.
Ein naiver Markov-Zustand würde die Ameisenposition und die genaue Lage aller fünf Samen verfolgen. Das ist viel zu fein. Relevant sind Samen nur dann, wenn sie noch unten liegen und abgeholt werden können, oder wenn sie oben bereits abgeliefert wurden.
Ein Zustand wird daher vollständig beschrieben durch:
$$B\subseteq\{0,1,2,3,4\}\quad\text{: Spalten, in deren unterer Zelle noch ein Samen liegt},$$
$$T\subseteq\{0,1,2,3,4\}\quad\text{: Spalten, deren obere Zelle bereits gefüllt ist},$$
zusätzlich zur Ameisenposition \(p\in\{0,\dots,24\}\) und einem Tragestatus.
Im Code werden \(B\) und \(T\) als 5-Bit-Masken gespeichert.
Im nichttragenden Zustand gilt:
$$|B|+|T|=5,$$
denn jeder noch nicht abgelieferte Samen liegt unten, und jeder bereits abgelieferte Samen belegt genau einen oberen Platz.
Im tragenden Zustand gilt:
$$|B|+|T|=4,$$
weil ein Samen bereits unten entfernt, aber oben noch nicht abgelegt wurde.
Damit erhält man genau die gültigen komprimierten Zustände. Ihre Anzahl ist
$$25\sum_{t=0}^{5}\binom{5}{t}\binom{5}{5-t}=25\binom{10}{5}=6300$$
für nichttragende Zustände und
$$25\sum_{t=0}^{4}\binom{5}{t}\binom{5}{4-t}=25\binom{10}{4}=5250$$
für tragende Zustände, also insgesamt
$$6300+5250=11550.$$
Der Code löst aber nicht ein einziges riesiges \(11550\times11550\)-System, sondern zerlegt die Aufgabe besser.
Im Zustand \((B,T,p,\text{nicht tragend})\) ist das nächste relevante Ereignis der erste Treffer einer noch aktiven unteren Zielzelle
$$bot(B)=\{b_j:\ j\in B\},$$
wobei \(b_j\) die untere Zelle der Spalte \(j\) ist.
Im tragenden Zustand \((B,T,p,\text{tragend})\) ist das nächste relevante Ereignis entsprechend der erste Treffer einer noch freien oberen Zielzelle
$$top(\overline T)=\{t_j:\ j\notin T\},$$
wobei \(t_j\) die obere Zelle der Spalte \(j\) ist.
Dieser Sprung ist exakt und keine Näherung. Sei \(\tau\) die erste Treffzeit des jeweiligen Zielsets. Wegen der starken Markov-Eigenschaft hängt die Zukunft nach dem Treffer nur vom neuen komprimierten Zustand ab, nicht vom benutzten Pfad. Deshalb lässt sich der Erwartungswert exakt zerlegen in:
erwartete Laufzeit bis zum nächsten Ereignis
plus
Erwartungswert der Fortsetzung ab dem Ereigniszustand.
Für ein Zielset \(S\) in der oberen oder unteren Zeile definieren wir
$$H_u^{S}=\mathbb E_u[\tau_S]$$
und für jede Zielspalte \(j\)
$$P_{u\to j}^{S}=\Pr_u(\text{erster Treffer in }S\text{ liegt in Spalte }j).$$
Diese Größen ergeben sich aus der First-Step-Zerlegung. Liegt \(u\) schon in \(S\), ist die Treffzeit null. Sonst kostet der erste Schritt eine Zeiteinheit und mittelt über alle Nachbarn:
$$H_u^{S}=\begin{cases} 0,&u\in S,\\ 1+\dfrac1{\deg(u)}\sum_{v\sim u}H_v^{S},&u\notin S. \end{cases}$$
Für die Ersttrefferwahrscheinlichkeiten gilt analog
$$P_{u\to j}^{S}=\begin{cases} 1,&u\text{ ist genau die Zielzelle der Spalte }j,\\ 0,&u\in S\text{, aber in einer anderen Zielspalte},\\ \dfrac1{\deg(u)}\sum_{v\sim u}P_{v\to j}^{S},&u\notin S. \end{cases}$$
Wichtig ist: die Koeffizientenmatrix ist für alle rechten Seiten dieselbe. Darum löst der Code pro Maske ein einziges \(25\times25\)-System mit 6 rechten Seiten: eine für die Erwartungszeit und fünf für die Spaltenwahrscheinlichkeiten.
Sei \(E_{nc}(B,T,p)\) der verbleibende Erwartungswert im nichttragenden Zustand und \(E_c(B,T,p)\) der entsprechende Wert im tragenden Zustand.
Ist die Ameise nicht tragend, muss sie als Nächstes \(bot(B)\) zum ersten Mal treffen. Also
$$E_{nc}(B,T,p)=H_p^{bot(B)}+\sum_{j\in B}P_{p\to j}^{bot(B)}\,E_c(B\setminus\{j\},T,b_j).$$
Der erste Summand ist die erwartete Laufzeit bis zur Aufnahme. Die Summe mittelt darüber, welche Spalte zuerst getroffen wird. Nach dem Erreichen von \(b_j\) wird der Samen sofort unten entfernt, also geht der Zustand in \((B\setminus\{j\},T,b_j,\text{tragend})\) über.
Ist die Ameise tragend, so lautet die exakte Formel
$$E_c(B,T,p)=H_p^{top(\overline T)}+\sum_{j\notin T}P_{p\to j}^{top(\overline T)}\,E_{nc}(B,T\cup\{j\},t_j).$$
Hier ist der erste Summand die erwartete Zeit bis zum Abliefern, und die Summe mittelt über die zuerst erreichte freie obere Spalte.
Die tragende Rekursion erhöht \(|T|\) um eins:
$$E_c(\cdots,T,\cdots)\longrightarrow E_{nc}(\cdots,T\cup\{j\},\cdots).$$
Die nichttragende Rekursion lässt \(|T|\) unverändert:
$$E_{nc}(\cdots,T,\cdots)\longrightarrow E_c(\cdots,T,\cdots).$$
Deshalb kann man nach
$$top\_count=|T|$$
von \(4\) abwärts iterieren. Dann hängen tragende Zustände auf Ebene \(top\_count\) nur von bereits bekannten nichttragenden Zuständen auf Ebene \(top\_count+1\) ab. Anschließend berechnet man die nichttragenden Zustände derselben Ebene aus den gerade bestimmten tragenden Zuständen. Es entsteht also ein gerichteter Schichtgraph ohne zyklische Relaxation.
Wenn alle fünf Samen bereits oben liegen, sind wir in einem nichttragenden Zustand mit
$$B=\varnothing,\qquad T=\{0,1,2,3,4\}.$$
Dann gilt für jede Position \(p\)
$$E_{nc}(\varnothing,\text{full},p)=0.$$
Der gesuchte Anfangszustand ist
$$B=\text{full},\qquad T=0,\qquad p=\text{center},\qquad \text{nicht tragend},$$
also die Größe
$$E_{nc}(\text{full},0,\text{center}).$$
Angenommen, unten ist nur noch der Samen in Spalte \(s\) vorhanden und oben ist nur noch Spalte \(t\) frei. Dann gibt es keine Verzweigung mehr.
Ist die Ameise nicht tragend und startet in \(p\), muss sie zuerst \(b_s\) treffen und anschließend \(t_t\). Daher
$$E_{nc}(\{s\},\text{full}\setminus\{t\},p)=H_p^{\{b_s\}}+H_{b_s}^{\{t_t\}}.$$
Ist sie bereits tragend, bleibt nur der zweite Abschnitt:
$$E_c(\varnothing,\text{full}\setminus\{t\},p)=H_p^{\{t_t\}}.$$
Genau diese Identitäten verifiziert der Code für alle \(s\), \(t\) und \(p\). Das ist ein starker Test, weil dabei sowohl die Treffersysteme als auch die Ereignis-DP geprüft werden.
1) Gitteraufbau. build_grid() speichert Nachbarn und Knotengrade der 25 Zellen.
2) Linearkern. solve_hitting_data() baut pro Zielmaske die gemeinsame Koeffizientenmatrix für obere oder untere Zielreihen auf. solve_linear_system() löst sie per Gauß-Elimination mit Pivotwahl.
3) Vorberechnung. Für jede nichtleere Maske werden Trefferzeit- und Ersttreffer-Spaltendaten für obere und untere Ziele separat gespeichert.
4) DP-Tabellen. expected_nc[bottom_mask][top_mask][pos] und expected_c[...] implementieren direkt die beiden Rekursionen.
5) Schichtreihenfolge. Die Schleife über top_count läuft von \(4\) nach \(0\). Pro Schicht werden zuerst die tragenden, dann die nichttragenden Zustände berechnet.
6) Checkpoints. Verifiziert wird: die Ersttrefferwahrscheinlichkeiten eines aktiven Zielsets summieren sich stets zu \(1\), und die Formeln für den Fall „genau ein Samen übrig“ stimmen mit den DP-Tabellen überein.
Es gibt nur \(31\) nichtleere Masken pro Zeile, für die Trefferdaten gebraucht werden. Jedes Problem ist ein \(25\times25\)-System mit 6 rechten Seiten und damit sehr klein. Danach besucht die DP nur die gültigen \((B,T,p)\)-Zustände. Das ist für Gleitkommaarithmetik numerisch völlig beherrschbar und erheblich kleiner als ein einziges riesiges Markov-Kettensystem über den gesamten Zustandsraum.
Bir karınca \(5\times5\) ızgarada eş olasılıklı rastgele yürüyüş yapıyor. Başlangıçta alt satırın beş hücresinde birer tohum var, üst satır tamamen boş ve karınca merkezde \((2,2)\) başlıyor. Karınca taşımıyorsa, tohumu hâlâ duran bir alt hücreye geldiğinde onu hemen alıyor; taşıyorsa, boş bir üst hücreye geldiğinde tohumu hemen bırakıyor. Amaç, beş tohumun tamamı üst satıra taşınana kadar geçen adım sayısının beklenen değerini bulmaktır.
Naif bir Markov durumu, karıncanın konumuyla birlikte beş tohumun tam yerleşimini izlerdi. Bu gereksiz ayrıntıdır. Tohumlar sadece iki durumda önemlidir: hâlâ altta duruyorlarsa veya yukarı bırakılmışlarsa.
Bu yüzden bir durum şu verilerle tamamen belirlenir:
$$B\subseteq\{0,1,2,3,4\}\quad\text{: altta tohumu hâlâ duran sütunlar},$$
$$T\subseteq\{0,1,2,3,4\}\quad\text{: üstte dolmuş sütunlar},$$
ayrıca karıncanın konumu \(p\in\{0,\dots,24\}\) ve bir taşıma bayrağı.
Kod, \(B\) ve \(T\)’yi 5 bitlik maskeler olarak saklar.
Karınca taşımıyorken, henüz teslim edilmemiş her tohum altta durur ve teslim edilmiş her tohum üstte bir yeri doldurur. Bu yüzden
$$|B|+|T|=5.$$
Karınca taşıyorken, bir tohum alttan alınmış ama henüz üste bırakılmamıştır. O halde
$$|B|+|T|=4.$$
Böylece geçerli sıkıştırılmış durumlar tam olarak belirlenir. Sayıları şöyledir:
$$25\sum_{t=0}^{5}\binom{5}{t}\binom{5}{5-t}=25\binom{10}{5}=6300$$
taşımasız durum için,
$$25\sum_{t=0}^{4}\binom{5}{t}\binom{5}{4-t}=25\binom{10}{4}=5250$$
taşımalı durum için. Toplam:
$$6300+5250=11550.$$
Fakat kod, tek bir dev \(11550\times11550\) lineer sistem çözmüyor; daha iyi bir ayrıştırma kullanıyor.
Durum \((B,T,p,\text{taşımıyor})\) olsun. Bir sonraki anlamlı olay, aktif alt hedeflerden birine ilk vuruştur:
$$bot(B)=\{b_j:\ j\in B\},$$
burada \(b_j\), \(j\) sütununun alt hücresidir.
Benzer şekilde durum \((B,T,p,\text{taşıyor})\) ise sıradaki anlamlı olay, henüz boş bir üst hücreye ilk vuruştur:
$$top(\overline T)=\{t_j:\ j\notin T\},$$
burada \(t_j\), \(j\) sütununun üst hücresidir.
Bu sıçrama yaklaşık değil, tamdır. İlgili ilk-vuruş zamanına \(\tau\) dersek, rastgele yürüyüşün strong Markov özelliği sayesinde olay hücresine ulaşıldıktan sonraki gelecek sadece yeni sıkıştırılmış duruma bağlıdır; oraya hangi yoldan gelindiğine bağlı değildir. Bu yüzden beklentiyi tam olarak
bir sonraki olaya kadar beklenen yürüyüş süresi
artı
olaydan sonraki devam beklentisi
şeklinde ayırabiliriz.
Üst veya alt satırda bulunan bir hedef küme \(S\) için, her başlangıç hücresi \(u\) adına
$$H_u^{S}=\mathbb E_u[\tau_S]$$
tanımlayalım; burada \(\tau_S\), \(S\)’ye ilk vuruş zamanıdır. Ayrıca her hedef sütun \(j\) için
$$P_{u\to j}^{S}=\Pr_u(\text{\(S\) içindeki ilk vuruşun sütun }j\text{’de olması})$$
olsun.
Bunlar first-step decomposition ile bulunur. Eğer \(u\in S\) ise vurma zamanı zaten sıfırdır. Eğer \(u\notin S\) ise ilk adım bir zaman birimi harcar ve komşular arasında ortalama alınır:
$$H_u^{S}=\begin{cases} 0,&u\in S,\\ 1+\dfrac1{\deg(u)}\sum_{v\sim u}H_v^{S},&u\notin S. \end{cases}$$
İlk-vuruş sütun olasılıkları için de benzer biçimde
$$P_{u\to j}^{S}=\begin{cases} 1,&u\text{ tam olarak sütun }j\text{’nin hedef hücresi ise},\\ 0,&u\in S\text{ ama başka bir hedef sütundaysa},\\ \dfrac1{\deg(u)}\sum_{v\sim u}P_{v\to j}^{S},&u\notin S. \end{cases}$$
Buradaki kritik nokta şudur: tüm sağ taraflar için katsayı matrisi aynıdır. Bu nedenle kod, her maske için 6 sağ taraflı tek bir \(25\times25\) sistem çözer: biri beklenen zaman, beşi sütun bazlı ilk-vuruş olasılıkları için.
\(E_{nc}(B,T,p)\), taşımasız bir durumdan itibaren kalan beklenen adım sayısı; \(E_c(B,T,p)\) ise taşımalı durumdan itibaren kalan beklenen adım sayısı olsun.
Karınca taşımıyorsa sıradaki olay \(bot(B)\)’ye ilk vuruştur. Bu yüzden
$$E_{nc}(B,T,p)=H_p^{bot(B)}+\sum_{j\in B}P_{p\to j}^{bot(B)}\,E_c(B\setminus\{j\},T,b_j).$$
İlk terim, alma olayına kadar geçen beklenen yürüyüş süresidir. Toplam terimi ise hangi alt sütuna önce ulaşıldığı üzerinde ortalama alır. \(b_j\)’ye varıldığında tohum hemen alttan kaldırıldığı için yeni durum \(B\setminus\{j\}\) maskeli taşımalı durum olur.
Karınca taşıyorsa benzer şekilde
$$E_c(B,T,p)=H_p^{top(\overline T)}+\sum_{j\notin T}P_{p\to j}^{top(\overline T)}\,E_{nc}(B,T\cup\{j\},t_j).$$
Burada ilk terim bırakma olayına kadar geçen beklenen süredir; toplam ise ilk hangi boş üst sütuna varıldığını ortalar.
Taşımalı bağıntı \(|T|\)’yi bir artırır:
$$E_c(\cdots,T,\cdots)\longrightarrow E_{nc}(\cdots,T\cup\{j\},\cdots).$$
Taşımasız bağıntı ise \(|T|\)’yi değiştirmez:
$$E_{nc}(\cdots,T,\cdots)\longrightarrow E_c(\cdots,T,\cdots).$$
Dolayısıyla
$$top\_count=|T|$$
değerine göre \(4\)’ten \(0\)’a inerek hesap yapabiliriz. Böylece:
\(top\_count\) katmanındaki taşımalı durumlar yalnızca \(top\_count+1\) katmanındaki, önceden hesaplanmış taşımasız durumlara bağlı olur;
sonra aynı katmandaki taşımasız durumlar, az önce hesaplanan taşımalı durumlarla bulunur.
Bu nedenle iteratif gevşetme gerekmeyen katmanlı bir DAG yapısı ortaya çıkar.
Tüm beş tohum yukarı taşınmışsa, taşımasız bir durumdayız ve
$$B=\varnothing,\qquad T=\{0,1,2,3,4\}.$$
Artık ek adım gerekmediğinden her \(p\) için
$$E_{nc}(\varnothing,\text{full},p)=0$$
olur.
Başlangıç durumu ise
$$B=\text{full},\qquad T=0,\qquad p=\text{center},\qquad \text{taşımıyor}$$
olduğundan aranan değer
$$E_{nc}(\text{full},0,\text{center})$$
şeklindedir.
Diyelim altta yalnızca \(s\) sütunundaki tohum kaldı ve üstte yalnızca \(t\) sütunu boş. O zaman dallanma kalmaz.
Karınca \(p\) konumunda ve taşımasızsa, önce \(b_s\)’ye, sonra \(t_t\)’ye vurmak zorundadır. Bu yüzden
$$E_{nc}(\{s\},\text{full}\setminus\{t\},p)=H_p^{\{b_s\}}+H_{b_s}^{\{t_t\}}.$$
Karınca zaten taşıyorsa yalnızca ikinci parça kalır:
$$E_c(\varnothing,\text{full}\setminus\{t\},p)=H_p^{\{t_t\}}.$$
Program tüm \(s\), \(t\) ve \(p\) seçimleri için bu özdeşlikleri sayısal olarak kontrol eder. Bu güçlü bir checkpoint’tir; çünkü hem hitting sistemlerini hem de olay-DP’sini aynı anda sınar.
1) Izgara kurulumu. build_grid() 25 hücrenin komşularını ve derecelerini çıkarır.
2) Lineer cebir çekirdeği. solve_hitting_data(), üst veya alt satırdaki bir hedef maskesi için ortak katsayı matrisini kurar. solve_linear_system() kısmi pivotlamalı Gauss eliminasyonu uygular.
3) Ön hesap. Her boş olmayan maske için üst hedefler ve alt hedefler adına hitting-time ve ilk-vuruş sütunu verisi önceden saklanır.
4) DP tabloları. expected_nc[bottom_mask][top_mask][pos] ve expected_c[...] tabloları yukarıdaki iki bağıntıyı doğrudan uygular.
5) Katman sırası. top_count döngüsü \(4\)’ten \(0\)’a iner. Her katmanda önce taşımalı, sonra taşımasız tablo doldurulur.
6) Checkpoint’ler. Kod iki invarianti doğrular: aktif hedef kümesi için ilk-vuruş olasılıklarının toplamı her zaman \(1\)’dir, ve yukarıdaki tek-tohum formülleri DP tablolarıyla birebir uyuşur.
Hitting verisi gereken boş olmayan maske sayısı satır başına yalnızca \(31\)’dir. Her biri 6 sağ taraflı \(25\times25\) lineer sistemdir; bu çok küçüktür. Sonrasında DP sadece yukarıda tanımlanan geçerli \((B,T,p)\) durumlarını gezer. Böylece hesap, kayan nokta açısından yeterince stabildir ve tüm durumu tek bir dev Markov sistemi olarak çözmeye göre çok daha küçüktür.
Una hormiga realiza un paseo aleatorio uniforme sobre una rejilla \(5\times5\). Al principio hay una semilla en cada celda de la fila inferior, la fila superior está vacía y la hormiga empieza en el centro \((2,2)\). Si no lleva carga y alcanza una celda inferior cuyo grano sigue presente, lo recoge inmediatamente. Si lleva carga y alcanza una celda superior vacía, lo deposita inmediatamente. Queremos el número esperado de pasos hasta que las cinco semillas hayan sido transportadas a la fila superior.
Un estado de Markov ingenuo seguiría la posición de la hormiga junto con la localización exacta de las cinco semillas. Eso es demasiado detallado. Las semillas solo importan cuando siguen abajo esperando ser recogidas o cuando ya han sido entregadas arriba.
Por tanto, un estado queda completamente descrito por:
$$B\subseteq\{0,1,2,3,4\}\quad\text{: columnas cuya semilla inferior sigue presente},$$
$$T\subseteq\{0,1,2,3,4\}\quad\text{: columnas ya ocupadas en la fila superior},$$
la posición \(p\in\{0,\dots,24\}\) y un indicador de carga.
En el código, \(B\) y \(T\) se guardan como máscaras de 5 bits.
Cuando la hormiga no lleva semilla, toda semilla no entregada sigue abajo y toda semilla entregada ocupa un hueco superior. Luego
$$|B|+|T|=5.$$
Cuando la hormiga sí lleva semilla, una semilla ya fue retirada de abajo pero aún no se ha depositado arriba, así que
$$|B|+|T|=4.$$
Esto determina exactamente los estados comprimidos válidos. Sus cantidades son
$$25\sum_{t=0}^{5}\binom{5}{t}\binom{5}{5-t}=25\binom{10}{5}=6300$$
para estados sin carga, y
$$25\sum_{t=0}^{4}\binom{5}{t}\binom{5}{4-t}=25\binom{10}{4}=5250$$
para estados con carga, en total
$$6300+5250=11550.$$
El programa no resuelve un único sistema gigante de tamaño \(11550\times11550\). Usa una descomposición más inteligente.
En un estado \((B,T,p,\text{sin carga})\), el siguiente evento relevante es el primer impacto en una celda activa de la fila inferior:
$$bot(B)=\{b_j:\ j\in B\},$$
donde \(b_j\) es la celda inferior de la columna \(j\).
En un estado \((B,T,p,\text{con carga})\), el siguiente evento relevante es el primer impacto en una celda superior aún vacía:
$$top(\overline T)=\{t_j:\ j\notin T\},$$
donde \(t_j\) es la celda superior de la columna \(j\).
Este salto es exacto, no heurístico. Si \(\tau\) es ese tiempo de primer impacto, la propiedad fuerte de Markov garantiza que, tras alcanzar la celda del evento, el futuro depende solo del nuevo estado comprimido y no del camino seguido. Por eso la esperanza se descompone exactamente como:
tiempo esperado hasta el próximo evento
más
valor esperado de continuación desde el estado posterior al evento.
Fijemos un conjunto objetivo \(S\) contenido en la fila superior o inferior. Para cada celda inicial \(u\), definimos
$$H_u^{S}=\mathbb E_u[\tau_S],$$
donde \(\tau_S\) es el tiempo del primer impacto en \(S\). También, para cada columna objetivo \(j\), definimos
$$P_{u\to j}^{S}=\Pr_u(\text{que el primer impacto en }S\text{ ocurra en la columna }j).$$
Estas cantidades salen de la descomposición por primer paso. Si \(u\in S\), el tiempo ya es cero. Si \(u\notin S\), el primer movimiento consume un paso y luego se promedia sobre los vecinos:
$$H_u^{S}=\begin{cases} 0,&u\in S,\\ 1+\dfrac1{\deg(u)}\sum_{v\sim u}H_v^{S},&u\notin S. \end{cases}$$
Del mismo modo, las probabilidades satisfacen
$$P_{u\to j}^{S}=\begin{cases} 1,&u\text{ es exactamente la celda objetivo de la columna }j,\\ 0,&u\in S\text{ pero pertenece a otra columna objetivo},\\ \dfrac1{\deg(u)}\sum_{v\sim u}P_{v\to j}^{S},&u\notin S. \end{cases}$$
Lo importante es que la matriz de coeficientes es la misma para todas las partes derechas. Por eso el código resuelve, para cada máscara, un único sistema \(25\times25\) con 6 términos independientes: uno para el tiempo esperado y cinco para las probabilidades por columna.
Sea \(E_{nc}(B,T,p)\) la esperanza restante en un estado sin carga, y \(E_c(B,T,p)\) la correspondiente esperanza en un estado con carga.
Si la hormiga no lleva semilla, el siguiente evento es el primer impacto en \(bot(B)\). Por tanto
$$E_{nc}(B,T,p)=H_p^{bot(B)}+\sum_{j\in B}P_{p\to j}^{bot(B)}\,E_c(B\setminus\{j\},T,b_j).$$
El primer término mide el tiempo esperado hasta recoger una semilla. La suma promedia qué columna inferior se alcanza primero. Al llegar a \(b_j\), la semilla se retira inmediatamente de abajo, así que el nuevo estado es de carga con máscara \(B\setminus\{j\}\).
Si la hormiga lleva una semilla, entonces
$$E_c(B,T,p)=H_p^{top(\overline T)}+\sum_{j\notin T}P_{p\to j}^{top(\overline T)}\,E_{nc}(B,T\cup\{j\},t_j).$$
Aquí el primer término es el tiempo esperado hasta dejar la semilla, y la suma promedia la primera columna superior vacía alcanzada.
La recurrencia con carga incrementa \(|T|\) en una unidad:
$$E_c(\cdots,T,\cdots)\longrightarrow E_{nc}(\cdots,T\cup\{j\},\cdots).$$
La recurrencia sin carga deja \(|T|\) fijo:
$$E_{nc}(\cdots,T,\cdots)\longrightarrow E_c(\cdots,T,\cdots).$$
Así, si procesamos por
$$top\_count=|T|$$
desde \(4\) hasta \(0\), los estados con carga del nivel \(top\_count\) solo dependen de estados sin carga del nivel \(top\_count+1\), ya conocidos. Después, los estados sin carga del mismo nivel dependen solo de los estados con carga recién calculados. No hace falta relajación iterativa.
Cuando las cinco semillas ya fueron entregadas, estamos en un estado sin carga con
$$B=\varnothing,\qquad T=\{0,1,2,3,4\}.$$
Entonces, para cualquier posición \(p\),
$$E_{nc}(\varnothing,\text{full},p)=0.$$
El estado inicial es
$$B=\text{full},\qquad T=0,\qquad p=\text{center},\qquad \text{sin carga},$$
de modo que la respuesta buscada es
$$E_{nc}(\text{full},0,\text{center}).$$
Supongamos que solo queda una semilla abajo, en la columna \(s\), y solo queda un hueco libre arriba, en la columna \(t\). Entonces ya no queda ramificación.
Si la hormiga está en \(p\) y no lleva carga, debe primero alcanzar \(b_s\) y luego \(t_t\). Por tanto
$$E_{nc}(\{s\},\text{full}\setminus\{t\},p)=H_p^{\{b_s\}}+H_{b_s}^{\{t_t\}}.$$
Si ya lleva semilla, solo queda la segunda parte:
$$E_c(\varnothing,\text{full}\setminus\{t\},p)=H_p^{\{t_t\}}.$$
El programa comprueba exactamente estas identidades para todas las elecciones de \(s\), \(t\) y \(p\). Es un checkpoint fuerte, porque prueba a la vez los sistemas de hitting y la DP de eventos.
1) Construcción de la rejilla. build_grid() almacena vecinos y grados de las 25 celdas.
2) Núcleo lineal. solve_hitting_data() construye la matriz común para una máscara objetivo en la fila superior o inferior. solve_linear_system() aplica eliminación gaussiana con pivoteo parcial.
3) Precálculo. Para cada máscara no vacía, el programa guarda datos de tiempo de impacto y de primera columna alcanzada, por separado para objetivos superiores e inferiores.
4) Tablas DP. expected_nc[bottom_mask][top_mask][pos] y expected_c[...] implementan directamente las dos recurrencias anteriores.
5) Orden por capas. El bucle sobre top_count baja de 4 a 0. En cada capa se rellenan primero los estados con carga y después los estados sin carga.
6) Checkpoints. Se verifican dos invariantes: las probabilidades de primer impacto sobre un conjunto objetivo activo siempre suman \(1\), y las fórmulas del caso con una sola semilla coinciden con las tablas DP.
Solo hay \(31\) máscaras no vacías por fila que requieren datos de hitting. Cada una resuelve un sistema \(25\times25\) con 6 partes derechas, algo muy pequeño. Después, la DP visita únicamente los estados válidos \((B,T,p)\) descritos arriba. Por eso el cálculo es manejable numéricamente y mucho más pequeño que resolver una única cadena de Markov gigante sobre todo el espacio de estados.
一只蚂蚁在 \(5\times5\) 网格上做均匀随机游走。开始时，底行五个格子各有一粒种子，顶行五个格子全空，蚂蚁从中心 \((2,2)\) 出发。如果蚂蚁没有携带种子，并且到达了一个仍有种子的底行格子，它会立刻拾取该种子；如果它正携带种子，并且到达了一个空的顶行格子，它会立刻放下种子。我们要求把五粒种子全部搬到顶行所需步数的期望值。
如果直接做马尔可夫链，似乎要同时记录蚂蚁位置和五粒种子的精确位置。但这比实际需要的细得多。种子只在两种情况下重要：还在底行等待被拿走，或者已经在顶行被安置好。
因此一个状态可由下列信息完全决定：
$$B\subseteq\{0,1,2,3,4\}\quad\text{: 底行中种子仍然存在的列},$$
$$T\subseteq\{0,1,2,3,4\}\quad\text{: 顶行已经被占据的列},$$
再加上蚂蚁的位置 \(p\in\{0,\dots,24\}\) 和一个“是否携带种子”的标志。
代码中 \(B\) 和 \(T\) 都用 5 位 bitmask 表示。
当蚂蚁不携带种子时，所有尚未送达的种子都还在底行，而所有已经送达的种子都占据了顶行位置，因此
$$|B|+|T|=5.$$
当蚂蚁正在携带种子时，有一粒种子已经从底行拿走、但还没放到顶行，所以
$$|B|+|T|=4.$$
这就准确刻画了所有有效的压缩状态。它们的数量分别是
$$25\sum_{t=0}^{5}\binom{5}{t}\binom{5}{5-t}=25\binom{10}{5}=6300$$
个不携带状态，以及
$$25\sum_{t=0}^{4}\binom{5}{t}\binom{5}{4-t}=25\binom{10}{4}=5250$$
个携带状态，总计
$$6300+5250=11550.$$
但代码并没有去解一个巨大的 \(11550\times11550\) 线性系统，而是做了更巧妙的分解。
设当前状态为 \((B,T,p,\text{未携带})\)。下一个真正有意义的事件是：随机游走第一次碰到某个仍然活跃的底行目标格
$$bot(B)=\{b_j:\ j\in B\},$$
其中 \(b_j\) 表示第 \(j\) 列的底行格子。
类似地，在状态 \((B,T,p,\text{携带})\) 下，下一个有意义事件是第一次碰到某个仍然空着的顶行目标格
$$top(\overline T)=\{t_j:\ j\notin T\},$$
其中 \(t_j\) 是第 \(j\) 列的顶行格子。
这种跳跃是精确的，不是近似。设 \(\tau\) 为相应的首次击中时间。由随机游走的强马尔可夫性质可知，一旦到达事件格，之后的演化只依赖于新的压缩状态，而与此前走过的具体路径无关。因此总期望可以严格分解为：
到下一个事件为止的期望步数
加上
从事件后状态继续下去的期望值。
固定一个位于顶行或底行的目标集合 \(S\)。对每个起点格子 \(u\)，定义
$$H_u^{S}=\mathbb E_u[\tau_S],$$
其中 \(\tau_S\) 是首次击中 \(S\) 的时间。再对每一个目标列 \(j\)，定义
$$P_{u\to j}^{S}=\Pr_u(\text{在 }S\text{ 中的第一次命中发生在第 }j\text{ 列}).$$
这些量由 first-step decomposition 得出。如果 \(u\in S\)，击中时间已经是 0；如果 \(u\notin S\)，第一步消耗 1 个时间单位，然后对所有相邻格子取平均：
$$H_u^{S}=\begin{cases} 0,&u\in S,\\ 1+\dfrac1{\deg(u)}\sum_{v\sim u}H_v^{S},&u\notin S. \end{cases}$$
同理，首次击中列概率满足
$$P_{u\to j}^{S}=\begin{cases} 1,&u\text{ 正好是第 }j\text{ 列对应的目标格},\\ 0,&u\in S\text{ 但属于另一目标列},\\ \dfrac1{\deg(u)}\sum_{v\sim u}P_{v\to j}^{S},&u\notin S. \end{cases}$$
关键结构是：所有这些方程的系数矩阵完全相同。因此代码对每个 mask 只解一个 \(25\times25\) 线性系统，但带有 6 个右端项：一个用于期望时间，五个用于五列的首次击中概率。
记 \(E_{nc}(B,T,p)\) 为不携带状态下剩余步数的期望，\(E_c(B,T,p)\) 为携带状态下剩余步数的期望。
如果蚂蚁当前未携带种子，那么下一个事件一定是首次击中 \(bot(B)\)。因此
$$E_{nc}(B,T,p)=H_p^{bot(B)}+\sum_{j\in B}P_{p\to j}^{bot(B)}\,E_c(B\setminus\{j\},T,b_j).$$
第一项是到“拾取事件”为止的期望步数；求和项则对“最先碰到哪一列的底部种子”做平均。到达 \(b_j\) 后，这粒种子会立刻从底行消失，所以新状态是携带状态，底部 mask 变成 \(B\setminus\{j\}\)。
如果蚂蚁当前正携带种子，则有
$$E_c(B,T,p)=H_p^{top(\overline T)}+\sum_{j\notin T}P_{p\to j}^{top(\overline T)}\,E_{nc}(B,T\cup\{j\},t_j).$$
这里第一项是到“放下事件”为止的期望步数；求和项对“先到达哪一个空的顶行列”取平均。
携带状态的递推会让 \(|T|\) 增加 1：
$$E_c(\cdots,T,\cdots)\longrightarrow E_{nc}(\cdots,T\cup\{j\},\cdots).$$
不携带状态的递推则保持 \(|T|\) 不变：
$$E_{nc}(\cdots,T,\cdots)\longrightarrow E_c(\cdots,T,\cdots).$$
因此按
$$top\_count=|T|$$
从 \(4\) 递减到 \(0\) 计算即可。这样，某一层的携带状态只依赖于上一层已知的不携带状态；然后同一层的不携带状态再依赖于刚算出的携带状态。整个依赖图是分层 DAG，不需要迭代松弛。
当五粒种子都已经送到顶行时，我们处在不携带状态，并且
$$B=\varnothing,\qquad T=\{0,1,2,3,4\}.$$
此时对任意位置 \(p\) 都有
$$E_{nc}(\varnothing,\text{full},p)=0.$$
初始状态则是
$$B=\text{full},\qquad T=0,\qquad p=\text{center},\qquad \text{未携带},$$
因此所求答案是
$$E_{nc}(\text{full},0,\text{center}).$$
假设底行只剩第 \(s\) 列的一粒种子，而顶行只剩第 \(t\) 列一个空位。那么此时已经没有分支了。
若蚂蚁在位置 \(p\) 且未携带种子，它必须先到达 \(b_s\)，再到达 \(t_t\)。因此
$$E_{nc}(\{s\},\text{full}\setminus\{t\},p)=H_p^{\{b_s\}}+H_{b_s}^{\{t_t\}}.$$
若蚂蚁已经携带种子，则只剩第二段：
$$E_c(\varnothing,\text{full}\setminus\{t\},p)=H_p^{\{t_t\}}.$$
程序对所有 \(s\)、\(t\)、\(p\) 都检查这两个公式。这是很强的 checkpoint，因为它同时验证了 hitting 线性系统和事件级 DP。
1) 网格构造。 build_grid() 记录 25 个格子的邻接关系与度数。
2) 线性代数核心。 solve_hitting_data() 为顶行或底行的某个目标 mask 构造公共系数矩阵；solve_linear_system() 用带部分主元的高斯消元求解。
3) 预计算。 对每个非空 mask，程序分别保存顶行目标与底行目标的击中时间和首次击中列概率。
4) DP 表。 expected_nc[bottom_mask][top_mask][pos] 和 expected_c[...] 直接实现上述两条递推。
5) 分层顺序。 top_count 从 4 下降到 0。每一层先算携带表，再算不携带表。
6) 检查点。 程序验证两个不变量： 对活跃目标集合，首次击中各列的概率和始终为 \(1\)； 上面的“一粒种子”公式与 DP 表完全一致。
每一行只有 \(31\) 个非空 mask 需要预计算 hitting 数据。每个问题只是一个带 6 个右端项的 \(25\times25\) 线性系统，非常小。之后 DP 只访问上面描述的有效 \((B,T,p)\) 状态。因此整个计算在浮点精度下完全可控，也远小于把整个过程作为一个巨大马尔可夫链一次性求解。
Муравей совершает равновероятное случайное блуждание по сетке \(5\times5\). Изначально в каждой клетке нижней строки лежит по одному семени, верхняя строка пуста, а муравей стартует из центра \((2,2)\). Если муравей ничего не несет и попадает в нижнюю клетку, где семя еще есть, он немедленно подбирает его. Если он несет семя и попадает в пустую верхнюю клетку, он немедленно его оставляет. Нужно найти математическое ожидание числа шагов до переноса всех пяти семян в верхнюю строку.
Наивное состояние Марковской цепи хранило бы позицию муравья и точное расположение всех пяти семян. Это гораздо подробнее, чем нужно. Семена важны лишь в двух ситуациях: когда они еще лежат внизу и ждут подбора, и когда они уже доставлены наверх.
Поэтому состояние полностью определяется:
$$B\subseteq\{0,1,2,3,4\}\quad\text{: столбцы, где нижнее семя еще не убрано},$$
$$T\subseteq\{0,1,2,3,4\}\quad\text{: столбцы, чья верхняя клетка уже занята},$$
позицией муравья \(p\in\{0,\dots,24\}\) и флагом «несет / не несет».
В коде \(B\) и \(T\) хранятся как 5-битовые маски.
Если муравей не несет семя, то каждое еще не доставленное семя все еще лежит внизу, а каждое уже доставленное занимает одну верхнюю позицию. Значит,
$$|B|+|T|=5.$$
Если муравей несет семя, одна семечка уже снята снизу, но еще не положена сверху, поэтому
$$|B|+|T|=4.$$
Это точно описывает множество допустимых сжатых состояний. Их число равно
$$25\sum_{t=0}^{5}\binom{5}{t}\binom{5}{5-t}=25\binom{10}{5}=6300$$
для состояний без груза и
$$25\sum_{t=0}^{4}\binom{5}{t}\binom{5}{4-t}=25\binom{10}{4}=5250$$
для состояний с грузом, всего
$$6300+5250=11550.$$
Но программа не решает одно огромное уравнение размера \(11550\times11550\); она использует гораздо более удачное разложение.
Рассмотрим состояние \((B,T,p,\text{не несет})\). Следующее содержательное событие — первое попадание в одну из активных нижних клеток
$$bot(B)=\{b_j:\ j\in B\},$$
где \(b_j\) — нижняя клетка столбца \(j\).
Аналогично, в состоянии \((B,T,p,\text{несет})\) следующим содержательным событием будет первое попадание в одну из еще свободных верхних клеток
$$top(\overline T)=\{t_j:\ j\notin T\},$$
где \(t_j\) — верхняя клетка столбца \(j\).
Такой прыжок является точным, а не эвристическим. Если \(\tau\) — соответствующее время первого попадания, то по сильному марковскому свойству после попадания дальнейшее поведение зависит только от нового сжатого состояния, а не от конкретного пути. Поэтому ожидание раскладывается точно как:
ожидаемое время до следующего события
плюс
ожидаемое продолжение из состояния после события.
Зафиксируем целевое множество \(S\), лежащее в верхней или нижней строке. Для каждой стартовой клетки \(u\) определим
$$H_u^{S}=\mathbb E_u[\tau_S],$$
где \(\tau_S\) — время первого попадания в \(S\). Также для каждой целевой колонки \(j\) положим
$$P_{u\to j}^{S}=\Pr_u(\text{что первое попадание в }S\text{ произойдет в колонке }j).$$
Эти величины находятся по разложению по первому шагу. Если \(u\in S\), время уже равно нулю. Если \(u\notin S\), первый шаг тратит одну единицу времени, а затем идет усреднение по соседям:
$$H_u^{S}=\begin{cases} 0,&u\in S,\\ 1+\dfrac1{\deg(u)}\sum_{v\sim u}H_v^{S},&u\notin S. \end{cases}$$
Аналогично для вероятностей:
$$P_{u\to j}^{S}=\begin{cases} 1,&u\text{ является целевой клеткой колонки }j,\\ 0,&u\in S\text{, но принадлежит другой целевой колонке},\\ \dfrac1{\deg(u)}\sum_{v\sim u}P_{v\to j}^{S},&u\notin S. \end{cases}$$
Ключевая структурная деталь: матрица коэффициентов одинакова для всех правых частей. Поэтому для каждой маски код решает одно уравнение размера \(25\times25\), но сразу с 6 правыми частями: одна для времени ожидания и пять для вероятностей по колонкам.
Пусть \(E_{nc}(B,T,p)\) — ожидаемое число оставшихся шагов в состоянии без груза, а \(E_c(B,T,p)\) — в состоянии с грузом.
Если муравей ничего не несет, следующее событие — первое попадание в \(bot(B)\). Следовательно,
$$E_{nc}(B,T,p)=H_p^{bot(B)}+\sum_{j\in B}P_{p\to j}^{bot(B)}\,E_c(B\setminus\{j\},T,b_j).$$
Первый член — ожидаемое число шагов до подбора. Сумма усредняет по тому, в какой нижний столбец попадание произойдет раньше. После попадания в \(b_j\) семя немедленно снимается снизу, поэтому новый carrying-state имеет маску \(B\setminus\{j\}\).
Если муравей несет семя, то
$$E_c(B,T,p)=H_p^{top(\overline T)}+\sum_{j\notin T}P_{p\to j}^{top(\overline T)}\,E_{nc}(B,T\cup\{j\},t_j).$$
Здесь первый член — ожидаемое время до оставления семени, а сумма усредняет по первой достигнутой пустой верхней колонке.
Рекурсия для состояний с грузом увеличивает \(|T|\) на единицу:
$$E_c(\cdots,T,\cdots)\longrightarrow E_{nc}(\cdots,T\cup\{j\},\cdots).$$
Рекурсия для состояний без груза сохраняет \(|T|\):
$$E_{nc}(\cdots,T,\cdots)\longrightarrow E_c(\cdots,T,\cdots).$$
Поэтому можно вычислять по
$$top\_count=|T|$$
от \(4\) вниз к \(0\). Тогда carrying-состояния на уровне \(top\_count\) зависят только от уже известных non-carrying-состояний уровня \(top\_count+1\). После этого non-carrying-состояния того же уровня зависят только от только что вычисленных carrying-состояний. Получается слоистый DAG, а не система, требующая итеративной релаксации.
Когда все пять семян уже доставлены вверх, мы находимся в состоянии без груза с
$$B=\varnothing,\qquad T=\{0,1,2,3,4\}.$$
Тогда для любой позиции \(p\)
$$E_{nc}(\varnothing,\text{full},p)=0.$$
Начальное состояние есть
$$B=\text{full},\qquad T=0,\qquad p=\text{center},\qquad \text{не несет},$$
поэтому искомая величина равна
$$E_{nc}(\text{full},0,\text{center}).$$
Пусть внизу осталась только одна семечка, в столбце \(s\), а наверху свободно только место в столбце \(t\). Тогда ветвлений больше нет.
Если муравей в позиции \(p\) и без груза, он обязан сначала прийти в \(b_s\), а затем в \(t_t\). Значит,
$$E_{nc}(\{s\},\text{full}\setminus\{t\},p)=H_p^{\{b_s\}}+H_{b_s}^{\{t_t\}}.$$
Если он уже несет семя, остается только второй участок:
$$E_c(\varnothing,\text{full}\setminus\{t\},p)=H_p^{\{t_t\}}.$$
Код проверяет именно эти формулы для всех \(s\), \(t\) и \(p\). Это сильный checkpoint: он одновременно тестирует и hitting-системы, и событийный DP.
1) Построение сетки. build_grid() сохраняет соседей и степени 25 клеток.
2) Линейное ядро. solve_hitting_data() строит общую матрицу коэффициентов для целевой маски в верхней или нижней строке. solve_linear_system() выполняет метод Гаусса с частичным выбором главного элемента.
3) Предвычисление. Для каждой непустой маски отдельно сохраняются времена попадания и вероятности первой достигнутой колонки для верхних и нижних целей.
4) DP-таблицы. expected_nc[bottom_mask][top_mask][pos] и expected_c[...] напрямую реализуют две рекуррентные формулы выше.
5) Порядок слоев. Цикл по top_count идет от \(4\) к \(0\). На каждом уровне сначала считаются состояния с грузом, затем состояния без груза.
6) Checkpoints. Проверяются два инварианта: вероятности первого попадания по активному целевому множеству всегда суммируются в \(1\), а формулы для случая с одной оставшейся семечкой совпадают с DP-таблицами.
Для каждой строки нужно предвычислить данные только для \(31\) непустой маски. Каждая такая задача — это система \(25\times25\) с 6 правыми частями, то есть очень маленькая. После этого DP посещает только допустимые состояния \((B,T,p)\). Поэтому вычисление вполне устойчиво в плавающей точке и намного меньше, чем решение одной гигантской марковской системы на всем пространстве состояний.
تقوم نملة بمشي عشوائي منتظم على شبكة \(5\times5\). في البداية توجد بذرة واحدة في كل خلية من الصف السفلي، والصف العلوي فارغ، وتبدأ النملة من المركز \((2,2)\). إذا كانت النملة لا تحمل بذرة ووصلت إلى خلية سفلية ما زالت تحتوي بذرة فإنها تلتقطها فورًا. وإذا كانت تحمل بذرة ووصلت إلى خلية علوية فارغة فإنها تضعها فورًا. المطلوب هو القيمة المتوقعة لعدد الخطوات حتى تُنقل البذور الخمس كلها إلى الصف العلوي.
الحالة الماركوفيّة الساذجة كانت ستتبع موضع النملة مع التوزيع الدقيق للبذور الخمس. لكن هذا تفصيل أكثر مما نحتاج. فالبذور لا تهم إلا في حالتين: إما أنها ما زالت في الصف السفلي تنتظر الالتقاط، أو أنها وُضعت بالفعل في الصف العلوي.
لذلك تُوصف الحالة بالكامل بواسطة:
$$B\subseteq\{0,1,2,3,4\}\quad\text{: الأعمدة التي ما زالت بذرتها السفلية موجودة},$$
$$T\subseteq\{0,1,2,3,4\}\quad\text{: الأعمدة التي امتلأت خاناتها العلوية بالفعل},$$
إضافة إلى موضع النملة \(p\in\{0,\dots,24\}\) وراية تبيّن هل تحمل بذرة أم لا.
في الكود تُخزن \(B\) و\(T\) على شكل أقنعة من 5 بتات.
عندما تكون النملة غير حاملة، فإن كل بذرة لم تُسلَّم بعد ما زالت في الأسفل، وكل بذرة سُلّمت بالفعل تشغل خانة علوية. لذلك
$$|B|+|T|=5.$$
وعندما تكون النملة حاملة، تكون هناك بذرة واحدة قد أُزيلت من الأسفل لكنها لم تُوضَع بعد في الأعلى، ومن ثم
$$|B|+|T|=4.$$
وهذا يحدد تمامًا الحالات المضغوطة الصالحة. عددها هو
$$25\sum_{t=0}^{5}\binom{5}{t}\binom{5}{5-t}=25\binom{10}{5}=6300$$
للحالات غير الحاملة، و
$$25\sum_{t=0}^{4}\binom{5}{t}\binom{5}{4-t}=25\binom{10}{4}=5250$$
للحالات الحاملة، أي ما مجموعه
$$6300+5250=11550.$$
لكن البرنامج لا يحل نظامًا خطيًا واحدًا ضخمًا بحجم \(11550\times11550\)، بل يستخدم تفكيكًا أذكى بكثير.
لننظر إلى الحالة \((B,T,p,\text{غير حاملة})\). الحدث المهم التالي هو أول مرة يصل فيها المشي العشوائي إلى إحدى الخلايا السفلية الفعالة
$$bot(B)=\{b_j:\ j\in B\},$$
حيث \(b_j\) هي الخلية السفلية في العمود \(j\).
وبالمثل، في الحالة \((B,T,p,\text{حاملة})\)، يكون الحدث المهم التالي هو أول وصول إلى إحدى الخلايا العلوية التي ما زالت فارغة
$$top(\overline T)=\{t_j:\ j\notin T\},$$
حيث \(t_j\) هي الخلية العلوية في العمود \(j\).
هذه القفزة دقيقة تمامًا وليست تقريبًا. إذا رمزنا بزمن أول وصول إلى هذا الحدث بالرمز \(\tau\)، فإن خاصية ماركوف القوية تعني أن المستقبل بعد بلوغ خلية الحدث يعتمد فقط على الحالة المضغوطة الجديدة، لا على المسار الذي أوصلنا إليها. ولذلك يمكن تفكيك التوقع بدقة إلى:
الزمن المتوقع حتى الحدث التالي
زائد
القيمة المتوقعة للاستمرار من الحالة التي تلي الحدث.
ثبّت مجموعة أهداف \(S\) ضمن الصف العلوي أو الصف السفلي. لكل خلية بداية \(u\) نعرّف
$$H_u^{S}=\mathbb E_u[\tau_S],$$
حيث \(\tau_S\) هو زمن أول وصول إلى \(S\). كما نعرّف لكل عمود هدف \(j\)
$$P_{u\to j}^{S}=\Pr_u(\text{أن يكون أول وصول داخل }S\text{ في العمود }j).$$
تأتي هذه القيم من تفكيك الخطوة الأولى. إذا كان \(u\in S\) فزمن الوصول يساوي صفرًا. وإذا كان \(u\notin S\) فإن الخطوة الأولى تكلف وحدة زمن ثم نأخذ المتوسط على الجيران:
$$H_u^{S}=\begin{cases} 0,&u\in S,\\ 1+\dfrac1{\deg(u)}\sum_{v\sim u}H_v^{S},&u\notin S. \end{cases}$$
وبالمثل تحقق احتمالات العمود الأول المعادلات
$$P_{u\to j}^{S}=\begin{cases} 1,&u\text{ هو بالضبط خلية الهدف الخاصة بالعمود }j,\\ 0,&u\in S\text{ لكنه يقع في عمود هدف آخر},\\ \dfrac1{\deg(u)}\sum_{v\sim u}P_{v\to j}^{S},&u\notin S. \end{cases}$$
والنقطة البنيوية المهمة هي أن مصفوفة المعاملات واحدة في جميع المعادلات. لذلك يحل الكود لكل قناع mask نظامًا واحدًا من الحجم \(25\times25\) لكن مع 6 أطراف يمنى: واحد للزمن المتوقع، وخمسة لاحتمالات الأعمدة الخمسة.
لتكن \(E_{nc}(B,T,p)\) هي القيمة المتوقعة لعدد الخطوات المتبقية في حالة غير حاملة، ولتكن \(E_c(B,T,p)\) القيمة المناظرة في حالة حاملة.
إذا كانت النملة غير حاملة، فإن الحدث التالي هو أول وصول إلى \(bot(B)\). ومن ثم
$$E_{nc}(B,T,p)=H_p^{bot(B)}+\sum_{j\in B}P_{p\to j}^{bot(B)}\,E_c(B\setminus\{j\},T,b_j).$$
الحد الأول هو الزمن المتوقع حتى الالتقاط. أما المجموع فيأخذ المتوسط على العمود السفلي الذي سيُصادف أولًا. وعند الوصول إلى \(b_j\) تُزال البذرة فورًا من الأسفل، ولذلك تصبح الحالة التالية حاملة مع القناع \(B\setminus\{j\}\).
وإذا كانت النملة حاملة، فنحصل على
$$E_c(B,T,p)=H_p^{top(\overline T)}+\sum_{j\notin T}P_{p\to j}^{top(\overline T)}\,E_{nc}(B,T\cup\{j\},t_j).$$
الحد الأول هنا هو الزمن المتوقع حتى الإسقاط، والمجموع يأخذ المتوسط على العمود العلوي الفارغ الذي يُصادَف أولًا.
علاقة الحالة الحاملة تزيد \(|T|\) بمقدار واحد:
$$E_c(\cdots,T,\cdots)\longrightarrow E_{nc}(\cdots,T\cup\{j\},\cdots).$$
أما علاقة الحالة غير الحاملة فتبقي \(|T|\) كما هو:
$$E_{nc}(\cdots,T,\cdots)\longrightarrow E_c(\cdots,T,\cdots).$$
لذلك يمكن الحساب حسب
$$top\_count=|T|$$
من \(4\) نزولًا إلى \(0\). وبهذا فإن الحالات الحاملة في طبقة \(top\_count\) تعتمد فقط على حالات غير حاملة في الطبقة \(top\_count+1\) والتي تكون محسوبة سلفًا. وبعد ذلك تُحسب الحالات غير الحاملة في الطبقة نفسها من الحالات الحاملة التي حُسبت للتو. إذن لدينا DAG طبقي واضح، ولا حاجة إلى استرخاء تكراري.
عندما تكون البذور الخمس كلها قد وُضعت في الأعلى، نكون في حالة غير حاملة مع
$$B=\varnothing,\qquad T=\{0,1,2,3,4\}.$$
وعندها، لأي موضع \(p\)، يكون
$$E_{nc}(\varnothing,\text{full},p)=0.$$
أما الحالة الابتدائية فهي
$$B=\text{full},\qquad T=0,\qquad p=\text{center},\qquad \text{غير حاملة},$$
ومن ثم فالجواب المطلوب هو
$$E_{nc}(\text{full},0,\text{center}).$$
افترض أن بذرة واحدة فقط بقيت في الأسفل في العمود \(s\)، وأن خانة علوية واحدة فقط ما زالت فارغة في العمود \(t\). عندئذ لا يبقى أي تفرع.
إذا كانت النملة عند الموضع \(p\) وغير حاملة، فعليها أولًا الوصول إلى \(b_s\) ثم إلى \(t_t\). لذلك
$$E_{nc}(\{s\},\text{full}\setminus\{t\},p)=H_p^{\{b_s\}}+H_{b_s}^{\{t_t\}}.$$
أما إذا كانت حاملة بالفعل، فلا يبقى إلا الجزء الثاني:
$$E_c(\varnothing,\text{full}\setminus\{t\},p)=H_p^{\{t_t\}}.$$
ويفحص البرنامج هاتين العلاقتين عدديًا لكل اختيار ممكن لـ \(s\) و\(t\) و\(p\). وهذا checkpoint قوي لأنه يختبر أنظمة الوصول والـ DP معًا.
1) بناء الشبكة. تخزن الدالة build_grid() الجيران ودرجات العقد لجميع الخلايا الـ 25.
2) النواة الخطية. تبني solve_hitting_data() مصفوفة المعاملات المشتركة لقناع هدف في الصف العلوي أو السفلي. وتقوم solve_linear_system() بحلها بطريقة جاوس مع اختيار محور جزئي.
3) الحساب المسبق. لكل قناع غير فارغ تُخزن بيانات أزمنة الوصول واحتمالات أول عمود مصاب، وذلك بصورة منفصلة لأهداف الصف العلوي وأهداف الصف السفلي.
4) جداول DP. المصفوفتان expected_nc[bottom_mask][top_mask][pos] وexpected_c[...] تطبقان العلاقتين السابقتين مباشرة.
5) ترتيب الطبقات. تدور الحلقة على top_count من \(4\) إلى \(0\). وفي كل طبقة تُحسب أولًا الحالات الحاملة ثم الحالات غير الحاملة.
6) نقاط التحقق. يتحقق البرنامج من ثابتين: مجموع احتمالات أول وصول على مجموعة هدف فعالة يساوي دائمًا \(1\)، وصيغ حالة “بذرة واحدة متبقية” تطابق جداول DP تمامًا.
يوجد فقط \(31\) قناعًا غير فارغ في كل صف يحتاج إلى بيانات hitting. وكل واحد منها مجرد نظام \(25\times25\) مع 6 أطراف يمنى، وهو صغير جدًا. وبعد ذلك تزور الـ DP فقط الحالات الصالحة \((B,T,p)\) الموصوفة أعلاه. لذلك يبقى الحساب مستقرًا عدديًا في الحساب العشري، وأصغر بكثير من حل سلسلة ماركوف واحدة ضخمة على فضاء الحالات الكامل.