Pemrograman dinamis dengan sejumlah besar masalah

Pemrograman dinamis dengan sejumlah besar masalah. Jadi saya mencoba menyelesaikan masalah ini dari Interview Street:

Grid Walking (Nilai 50 poin)
Anda berada di grid $N$ dimensi pada posisi $(x_1,x_2,\dots,x_N)$ . Dimensi grid adalah $(D_1,D_2,\dots,D_N$ ). Dalam satu langkah, Anda dapat berjalan satu langkah di depan atau di belakang di salah satu dari dimensi $N$(Jadi selalu ada $2N$ gerakan yang mungkin berbeda). Berapa banyak cara yang bisa Anda ambil $M$langkah-langkah sedemikian rupa sehingga Anda tidak meninggalkan grid di titik mana pun? Anda meninggalkan kotak jika untuk $x_i$ , baik $x_i \leq 0$ atau $x_i > D_i$ .

Percobaan pertama saya adalah solusi rekursif memoised ini:

def number_of_ways(steps, starting_point):
    global n, dimensions, mem
    #print steps, starting_point
    if (steps, tuple(starting_point)) in mem:
        return mem[(steps, tuple(starting_point))]
    val = 0
    if steps == 0:
        val = 1
    else:
        for i in range(0, n):
            tuple_copy = starting_point[:]
            tuple_copy[i] += 1
            if tuple_copy[i] <= dimensions[i]:
                val += number_of_ways(steps - 1, tuple_copy)
            tuple_copy = starting_point[:]
            tuple_copy[i] -= 1
            if tuple_copy[i] > 0:
                val += number_of_ways(steps - 1, tuple_copy)
    mem[(steps, tuple(starting_point))] = val
    return val

Kejutan besar: gagal untuk sejumlah besar langkah dan / atau dimensi karena kurangnya memori.

Jadi langkah selanjutnya adalah meningkatkan solusi saya dengan menggunakan pemrograman dinamis. Tetapi sebelum memulai, saya melihat masalah besar dengan pendekatan tersebut. Argumennya starting_pointadalah $n$ -tuple, di mana $n$ sebesar $10$ . Jadi sebenarnya, fungsinya bisa number_of_ways(steps, x1, x2, x3, ... x10)dengan $1 \leq x_i \leq 100$ .

Masalah pemrograman dinamis yang saya lihat di buku pelajaran hampir semuanya memiliki variabel twp, sehingga hanya diperlukan matriks dua dimensi. Dalam hal ini, matriks sepuluh dimensi akan diperlukan. Jadi sel total.$100^{10}$

Dengan matriks 2-D dalam pemrograman dinamis, biasanya hanya baris perhitungan sebelumnya yang diperlukan untuk perhitungan selanjutnya, sehingga mengurangi kompleksitas spasial dari ke min ( m , n ) . Saya tidak yakin bagaimana saya akan melakukan hal yang sama dalam kasus ini. Memvisualisasikan tabel tidak layak, jadi jawabannya harus datang langsung dari rekursi di atas.$mn$$\min(m,n)$

MEMPERBARUI

Menggunakan saran Peter Shor, dan membuat beberapa koreksi kecil, terutama kebutuhan untuk melacak posisi dalam fungsi , dan bukannya hanya membelah dimensi menjadi dua set A dan B, melakukan pemisahan secara rekursif, secara efektif menggunakan metode divide-and-conquer, hingga base case tercapai di mana hanya satu dimensi berada di set.$W(i, t_i)$

Saya datang dengan implementasi berikut, yang lulus semua tes di bawah waktu eksekusi maksimum:

def ways(di, offset, steps):
    global mem, dimensions
    if steps in mem[di] and offset in mem[di][steps]:
        return mem[di][steps][offset]
    val = 0
    if steps == 0:
        val = 1
    else:
        if offset - 1 >= 1:
            val += ways(di, offset - 1, steps - 1)
        if offset + 1 <= dimensions[di]:
            val += ways(di, offset + 1, steps - 1)
    mem[di][steps][offset] = val
    return val


def set_ways(left, right, steps):
    # must create t1, t2, t3 .. ti for steps
    global mem_set, mem, starting_point
    #print left, right
    #sleep(2)
    if (left, right) in mem_set and steps in mem_set[(left, right)]:
        return mem_set[(left, right)][steps]
    if right - left == 1:
        #print 'getting steps for', left, steps, starting_point[left]
        #print 'got ', mem[left][steps][starting_point[left]], 'steps'
        return mem[left][steps][starting_point[left]]
        #return ways(left, starting_point[left], steps)
    val = 0
    split_point =  left + (right - left) / 2 
    for i in xrange(steps + 1):
        t1 = i
        t2 = steps - i
        mix_factor = fact[steps] / (fact[t1] * fact[t2])
        #print "mix_factor = %d, dimension: %d - %d steps, dimension %d - %d steps" % (mix_factor, left, t1, split_point, t2)
        val += mix_factor * set_ways(left, split_point, t1) * set_ways(split_point, right, t2)
    mem_set[(left, right)][steps] = val
    return val

import sys
from time import sleep, time

fact = {}
fact[0] = 1
start = time()
accum = 1
for k in xrange(1, 300+1):
    accum *= k
    fact[k] = accum
#print 'fact_time', time() - start

data = sys.stdin.readlines()
num_tests = int(data.pop(0))
for ignore in xrange(0, num_tests):
    n_and_steps = data.pop(0)
    n, steps = map(lambda x: int(x), n_and_steps.split())
    starting_point = map(lambda x: int(x), data.pop(0).split())
    dimensions = map(lambda x: int(x), data.pop(0).split())
    mem = {}
    for di in xrange(n):
        mem[di] = {}
        for i in xrange(steps + 1):
            mem[di][i] = {}
            ways(di, starting_point[di], i)
    start = time()
    #print 'mem vector is done'
    mem_set = {}
    for i in xrange(n + 1):
        for j in xrange(n + 1):
            mem_set[(i, j)] = {}
    answer = set_ways(0, n, steps)
    #print answer
    print answer % 1000000007
    #print time() - start

$t$$W(j,t)$

$t_i$$i$$N \choose t_1,t_2, \ldots, t_M$$i$$t_i$$\Pi_1^N W(i,t_i)$

Anda dapat melakukan yang lebih baik lagi. Secara rekursif membagi dimensi menjadi dua himpunan bagian, dan , dan menghitung berapa banyak berjalan ada hanya menggunakan dimensi di bagian , dan hanya orang-orang di . Sebut angka-angka ini dan , masing-masing. Anda mendapatkan jumlah total jalan kaki dengan$A$$B$$A$$B$$W_A(t)$$W_B(t)$

Mari kita ekstrak formula untuk dari kode Anda (untuk sel dalam, yang mengabaikan kasus perbatasan):$\newcommand{\now}{\operatorname{now}}\now(s,x_1,\dots,x_n)$

$\qquad \begin{align} \now(s,x_1,\dots,x_n) = \phantom{+} &\sum_{i=0}^n \now(s-1,x_1,\dots,x_{i-1},x_i + 1, x_{i+1},\dots,x_n) \\ + &\sum_{i=0}^n\now(s-1,x_1,\dots,x_{i-1},x_i - 1, x_{i+1},\dots,x_n) \end{align}$

Berikut ini beberapa ide.

• Kami melihat bahwa setelah Anda menghitung semua nilai untuk , Anda dapat menghapus semua nilai yang dihitung untuk .$s=k$$s<k$
• Untuk tetap , Anda harus menghitung entri tabel di urutan leksikografis (hanya karena itu sederhana). Kemudian, perhatikan bahwa setiap sel hanya membutuhkan sel-sel tersebut di dalam "jari-jari satu", yang tidak ada koordinat dapat lebih jauh dari satu. Karenanya, setelah iterasi Anda mencapai , Anda dapat memberikan semua nilai untuk . Jika itu tidak cukup, lakukan hal yang sama untuk - untuk tetap , drop nilai dengan dan ketika tercapai - dan seterusnya.$s$$x_1=i$$x_1\leq i-2$$x_2$$x_1=i$$x_1 = i$$x_2 \leq j-2$$x_2=j$
• Perhatikan bahwa "jadi selalu ada gerakan yang mungkin berbeda" hanya berlaku di tengah kisi, yaitu jika dan untuk semua . Tapi itu juga berarti bahwa jawabannya mudah di tengah-tengah: itu hanya . Jika Anda memiliki pengulangan pemrograman dinamis yang berfungsi, itu saja akan memungkinkan Anda mencukur habis sebagian besar tabel (jika ).$2N$$x_i - M > 0$$x_i + M < D_i$$i$$(2N)^M$$M\ll N$
• Hal lain yang perlu diperhatikan adalah Anda tidak perlu menghitung seluruh tabel; sebagian besar nilai akan diisi dengan pula (jika ). Anda dapat membatasi diri pada kubus (hiper) dengan panjang sekitar (perhatikan bahwa itu akan berubah karena jalur yang meninggalkan kisi).$0$$M\ll N$$2M$$x$

Itu harus cukup untuk menjaga penggunaan memori cukup rendah.