Pertanyaan Menemukan jalan dengan batasan panjang terberat di Pohon Biner tertimbang


MEMPERBARUI

Saya bekerja di algoritma yang saya pikir berjalan dalam O (n * k) waktu berjalan. Di bawah ini adalah pseudo-code:

routine heaviestKPath( T, k )

    // create 2D matrix with n rows and k columns with each element = -∞
    // we make it size k+1 because the 0th column must be all 0s for a later 
    // function to work properly and simplicity in our algorithm
    matrix = new array[ T.getVertexCount() ][ k + 1 ] (-∞);

    // set all elements in the first column of this matrix = 0
    matrix[ n ][ 0 ] = 0;

    // fill our matrix by traversing the tree
    traverseToFillMatrix( T.root, k );

    // consider a path that would arc over a node
    globalMaxWeight = -∞;
    findArcs( T.root, k );

    return globalMaxWeight
end routine


// node = the current node; k = the path length; node.lc = node’s left child; 
// node.rc = node’s right child; node.idx = node’s index (row) in the matrix; 
// node.lc.wt/node.rc.wt = weight of the edge to left/right child;
routine traverseToFillMatrix( node, k )

   if (node == null) return;

   traverseToFillMatrix(node.lc, k ); // recurse left
   traverseToFillMatrix(node.rc, k ); // recurse right

   // in the case that a left/right child doesn’t exist, or both,
   // let’s assume the code is smart enough to handle these cases
   matrix[ node.idx ][ 1 ] = max( node.lc.wt, node.rc.wt );


   for i = 2 to k {
       // max returns the heavier of the 2 paths
       matrix[node.idx][i] = max( matrix[node.lc.idx][i-1] + node.lc.wt, 
                                  matrix[node.rc.idx][i-1] + node.rc.wt);
   }

end routine



// node = the current node, k = the path length
routine findArcs( node, k ) 

    if (node == null) return;

    nodeMax = matrix[node.idx][k];
    longPath = path[node.idx][k];

    i = 1;
    j = k-1;
    while ( i+j == k AND i < k ) {

        left = node.lc.wt + matrix[node.lc.idx][i-1];
        right = node.rc.wt + matrix[node.rc.idx][j-1];

        if ( left + right > nodeMax ) {
            nodeMax = left + right;
        }
        i++; j--;
    }

    // if this node’s max weight is larger than the global max weight, update
    if ( globalMaxWeight < nodeMax ) {
        globalMaxWeight = nodeMax;
    }

    findArcs( node.lc, k ); // recurse left
    findArcs( node.rc, k ); // recurse right

end routine

Biarkan aku tahu apa yang Anda pikirkan. Umpan balik diterima.


saya berpikir telah muncul dengan dua algoritma naif yang menemukan jalur dengan panjang terberat terberat dalam Pohon Biner tertimbang. Pertama, uraian algoritma adalah sebagai berikut: diberikan n-vertex Binary Tree dengan tepi tertimbang dan beberapa nilai k, temukan lintasan terberat dari panjang k.

Untuk kedua algoritma, saya akan membutuhkan referensi untuk semua simpul jadi saya hanya akan melakukan traversal sederhana dari Pohon untuk memiliki referensi ke semua simpul, dengan setiap titik memiliki referensi ke kiri, kanan, dan simpul induknya di pohon.

Algoritme 1  Untuk algoritma ini, saya pada dasarnya berencana menjalankan DFS dari setiap node di Tree, dengan mempertimbangkan panjang jalur tetap. Selain itu, karena jalur yang saya cari memiliki potensi untuk pergi dari subtree kiri ke root ke subtree kanan, saya harus mempertimbangkan 3 pilihan pada setiap node. Tapi ini akan menghasilkan algoritma O (n * 3 ^ k) dan saya tidak suka itu.

Algoritme 2 Saya pada dasarnya berpikir tentang menggunakan versi modifikasi Algoritma Dijkstra untuk mempertimbangkan panjang jalur tetap. Karena saya mencari Alvarithm terberat dan Dijkstra menemukan yang paling ringan, saya berencana meniadakan semua bobot tepi sebelum memulai traversal. Sebenarnya ... ini tidak masuk akal karena saya harus menjalankan Dijkstra pada setiap node dan itu tidak tampak sangat efisien jauh lebih baik daripada algoritma di atas.

Jadi saya kira pertanyaan utama saya adalah beberapa. Pertama, apakah algoritme yang telah saya jelaskan di atas memecahkan masalah yang dihadapi? Saya tidak yakin versi Dijkstra akan bekerja karena Dijkstra dimaksudkan untuk nilai tepi positif.

Sekarang, saya yakin ada lebih banyak algoritma pintar / efisien untuk ini ... apa itu algoritma yang lebih baik? Saya pernah membaca tentang "Menggunakan dekomposisi tulang belakang untuk memecahkan masalah jalan berat yang terbatasi paling panjang untuk pohon" tapi itu benar-benar rumit dan saya tidak mengerti sama sekali. Adakah algoritma lain yang mengatasi masalah ini, mungkin tidak seefisien dekomposisi tulang belakang tetapi lebih mudah dimengerti?


5
2018-02-21 02:20


asal


Jawaban:


Inilah solusi saya. Umpan balik diterima.

Mari kita memperlakukan pohon biner sebagai grafik berarah, dengan tepi dari induk ke anak-anak. Mari mendefinisikan dua konsep untuk setiap vertex v:

a) busur: yang merupakan jalur terarah, yaitu dimulai dari verteks v, dan semua simpul di jalur adalah anak-anak dari titik awal v.

b) jalur turunan: yang merupakan jalur yang diarahkan atau tidak terarah yang mengandung v, artinya, bisa dimulai di mana saja, berakhir di mana saja, dan pergi dari anak v ke v, dan kemudian, katakan kepada anak lainnya. Set busur adalah bagian dari set anak-jalan.

Kami juga mendefinisikan fungsi HeaviestArc (v, j), yang memberikan, untuk titik j, arc terberat, di sisi kiri atau kanan, panjang j, dimulai dari v. Kita juga mendefinisikan LeftHeaviest (v, j), dan RightHeaviest (v, j) sebagai busur kiri dan kanan terberat dari panjang j masing-masing.

Dengan ini, kita dapat mendefinisikan kekambuhan berikut untuk setiap verteks v, berdasarkan pada anak-anaknya:

LeftHeaviest(v,j) = weight(LeftEdge(v)) + HeaviestArc(LeftChild(v)),j-1);
RightHeaviest(v,j) = weight(RightEdge(v)) + HeaviestArc(RightChild(v)),j-1);
HeaviestArc(v,j) = max(LeftHeaviest(v,j),RightHeaviest(v,j));

Di sini j sini pergi dari 1 ke k, dan HeaviestArc (v, 0) = LeftHeaviest (v, 0), RightHeaviest (v, 0) = 0 untuk semua. Untuk node daun, HeaviestArc (v, 0) = 0, dan HeaviestArc (v, j) = - inf untuk semua j lainnya (saya perlu memikirkan kasus sudut lebih teliti).

Dan kemudian HeaviestChildPath (v), jalan turunan terberat yang mengandung v, dapat dihitung sebagai:

HeaviestChildPath(v) = max{ for j = 0 to k LeftHeaviest(j) + RightHeaviest(k-j)}

Jalan terberat harus menjadi yang terberat dari semua jalur anak.

Perkiraan runtime dari algoritma harus urutan O (kn).


2
2018-02-21 20:44



Anda bisa menggunakan DFS ke bawah dari setiap node yang berhenti setelahnya k tepi untuk mencari jalur, tetapi perhatikan bahwa ini akan melakukan 2 ^ k bekerja di setiap node untuk total pekerjaan O (n * 2 ^ k), karena jumlah jalur berlipat ganda pada setiap level yang Anda turunkan dari simpul awal.

Seperti DasBoot mengatakan dalam komentar, tidak ada keuntungan menggunakan algoritme Dijkstra di sini karena jumlah kecerdasannya adalah memilih cara terpendek (atau terlama) untuk mendapatkan antara 2 poin ketika beberapa rute dimungkinkan. Dengan pohon selalu ada 1 cara.

Saya memiliki algoritma pemrograman dinamis dalam pikiran yang akan membutuhkan O (nk) waktu. Berikut beberapa petunjuk:

  • Jika Anda memilih beberapa simpul daun menjadi akar r dan mengarahkan semua simpul lainnya ke bawah, menjauh dari akarnya, perhatikan bahwa setiap jalur dalam pohon terarah ini memiliki simpul tertinggi - yaitu, simpul unik yang paling dekat r.
  • Anda dapat menghitung panjang-terberatk jalan secara keseluruhan dengan melalui setiap simpul v dan menghitung panjang paling berat-k jalan yang simpul tertingginya v, akhirnya mengambil maksimal semua node.
  • A length-k jalan yang simpul tertingginya v harus memiliki panjang-saya jalan menurun menuju satu anak dan panjang- (k-i) jalur menurun ke arah yang lain.

Itu seharusnya cukup untuk membuat Anda berpikir ke arah yang benar; beri tahu saya jika Anda membutuhkan bantuan lebih lanjut.


3
2018-02-21 04:35



def traverse(node, running_weight, level):
  if level == 0: 
    if max_weight < running_weight:
        max_weight = running_weight
    return
  traverse(node->left,running_weight+node.weight,level-1)
  traverse(node->right,running_weight+node.weight,level-1)
  traverse(node->parent,running_weight+node.weight,level-1)


max_weight = 0
for node in tree:
  traverse(node,0,N)

0
2018-02-21 02:41