Dato un albero che calcola Max Sum da cima a fondo facendo causa a DFS? ottimizzazione?

Question

Dato un albero che calcola Max Sum da cima a fondo facendo causa a DFS? ottimizzazione?

#1 da (1 voti)
#2 da (0 voti)

0

dato un albero voglio calcolare la somma massima di ogni percorso dall'alto al basso. Ho usato DFS per l'operazione. Ecco la funzione che prende radice come input e fornisce la somma massima del percorso da cima a fondo:

   private int DFS_max(TreeNode root) {
    // TODO Auto-generated method stub
    if(root == null){
        //System.out.println(root.value);
        //System.out.println();
        return 0;
    }

    int lvalue = DFS_max(root.getLeftNode());
    int rvalue = DFS_max(root.getRightNode());

    //System.out.print(root.value+" ");

    return (Math.max(lvalue, rvalue)+root.value );
}

tuttavia richiede molto tempo per eseguire il seguente input:

9235 
9096 637 
973 3269 7039 
3399 3350 4788 7546 
1739 8032 9427 976 2476 
703 9642 4232 1890 704 6463 
9601 1921 5655 1119 3115 5920 1808 
645 3674 246 2023 4440 9607 4112 3215 
660 6345 323 1664 2331 7452 3794 7679 3102 
1383 3058 755 1677 8032 2408 2592 2138 2373 8718 
8117 4602 7324 7545 4014 6970 4342 7682 150 3856 8177 
1966 1782 3248 1745 4864 9443 4900 8115 4120 9015 7040 9258 
4572 6637 9558 5366 7156 1848 2524 4337 5049 7608 8639 8301 1939 
7714 6996 2968 4473 541 3388 5992 2092 2973 9367 2573 2658 9965 8168 
67 1546 3243 752 8497 5215 7319 9245 574 7634 2223 8296 3044 9445 120 
7064 1045 5210 7347 5870 8487 3701 4301 1899 441 9828 3076 7769 8008 4496 6796 
5256 2199 464 5164 4039 1014 8099 7932 1909 3051 4805 1698 8578 1771 5889 5711 9967 
6830 2603 9256 3629 2793 5219 6534 8838 944 5113 4981 6811 6958 48 9463 7477 5723 1111 
7907 9312 4756 8096 3564 7809 9326 2502 5346 6383 5658 3791 423 701 3417 5042 2669 3759 5017 
8754 6389 4368 7284 2150 7288 6145 459 4079 1631 7595 620 2350 171 6401 4222 1182 5561 2669 7641 
3335 696 6551 360 454 708 5378 7750 8156 3187 4263 8282 9494 9607 1989 435 1558 5920 909 6567 5174 
1771 5573 4603 6962 5957 9870 3482 6287 324 6551 5035 7100 5595 6189 3178 6047 354 4873 1168 3815 8771 1222 
8982 6194 3575 3673 5892 5035 8234 8414 7744 6956 6341 6824 4562 9416 6808 8836 1692 9636 609 5238 6918 1685 8565 
7610 6713 1077 9905 9328 7107 4166 8230 4864 8540 1762 4870 7483 9504 2516 9634 7336 761 1805 5454 2967 530 6166 6541 
9277 1113 1596 9327 4106 9159 6484 1666 3774 5001 6357 8586 5151 1306 8160 2201 8124 7684 6362 9309 7702 5800 1827 2679 9402 
9080 7085 1053 5077 2129 8422 8489 8852 7628 6024 5841 4504 2658 8298 5860 6226 2157 5477 8728 4520 4513 590 6642 7711 3209 3005 
4500 7462 8825 848 8698 3585 7756 3857 7587 9434 7531 7443 5232 4212 3761 2111 4765 2628 432 9750 8871 5534 3519 9777 2692 7383 7686 
3624 8816 7672 7245 5646 4888 3871 5462 2170 1897 2787 823 8107 5186 5782 4911 2313 835 816 4192 8726 7262 903 7191 187 5542 4234 9292 
5817 2292 5964 9704 836 5776 5457 9027 9782 9306 5636 1268 250 5976 3032 1188 4460 5327 8071 6400 229 5587 5243 3777 1265 4847 1853 1421 9092 
704 2262 685 5345 716 1758 7567 3740 5354 480 9161 5544 1022 3196 8803 1074 3236 5157 3026 2407 9018 7720 4543 9281 3233 13 8065 996 5680 4485 
9963 1991 4531 4900 8560 7771 6957 5041 9103 823 9644 5190 6393 3295 291 1344 8459 4311 6189 8997 6670 5018 7465 9360 1255 3737 714 891 6314 6900 3369 
3160 5093 8864 404 3212 4571 5136 2730 6864 8175 9081 991 8629 6874 1727 9398 4353 1791 7975 1676 79 6005 173 5249 9092 9272 1827 401 6713 7010 26 8267 
8974 4103 5046 5274 6983 4807 9583 1897 3563 2384 8047 476 2499 5930 8452 214 3611 7346 5579 7471 8807 8361 4272 5997 5233 6109 6024 4832 1692 5886 327 1273 3633 
1377 4645 2518 160 5935 3329 2396 3755 3272 6328 8905 9729 2328 3103 4238 7738 8995 5798 1396 2157 6902 8463 558 1575 515 5827 3949 234 6437 6012 126 5832 2979 6441 
7307 8791 3842 1132 657 7840 9032 640 289 5535 5045 2925 5151 5220 6760 4623 2934 7859 5524 7361 7679 3131 1427 3046 4833 4257 2937 5389 8209 128 3724 2300 4461 1466 4779 
5267 8533 9 9710 7333 7839 986 2533 875 3863 9532 147 22 7337 1095 6244 267 7172 4391 9425 9587 3942 3000 5959 1211 5846 8321 6766 8081 8815 2253 9001 2992 2718 2738 4910 
6435 2443 9071 4492 6216 6061 6768 3976 9095 2236 3682 9092 4889 5596 70 689 7730 1847 5340 394 7524 4099 3329 5672 7042 8078 6141 6914 6522 6675 3795 4000 8177 3662 3259 6130 7610 
2258 5763 6708 7737 6758 5762 4507 3566 4424 8365 3451 2915 465 4607 5963 9007 1072 5565 9005 5753 8196 6975 7712 5498 5059 5742 8816 2030 3209 8568 4937 8719 345 728 1278 2792 3133 9997 
8226 1983 721 6701 6953 9027 2801 5895 239 2827 701 1815 7406 2497 1211 7901 525 1956 638 7934 8869 8237 936 5126 9949 6296 633 6368 8425 6713 806 8251 8680 397 316 9989 2901 6176 5180 
5883 4165 2973 4063 6614 3168 8186 5624 4303 8055 7803 3721 1023 9048 1845 3325 4237 3518 782 3410 5515 2521 4720 3050 785 6882 7356 3478 1374 9420 981 1986 5142 67 7113 3167 6122 2324 9764 9257 
9240 2726 4783 4078 3959 9828 9244 4470 6945 5576 9405 8984 9255 9900 4457 6075 7944 8826 5918 3086 5487 7507 9357 2894 2955 2176 5932 7258 4504 9219 6115 4612 1390 5323 6949 5366 3494 9970 7190 9565 5099 
408 1771 233 9549 9691 8154 641 4346 372 2372 5306 4199 9991 1790 2614 4628 9646 4980 1610 2803 3596 6476 6735 5484 6132 5633 2054 6181 1731 4350 891 4916 5913 7961 7657 4368 7146 7280 6168 5573 4644 7463 
2764 4872 2984 1130 3119 1307 2067 9021 8833 320 175 1340 3573 5251 8588 6919 8844 2877 8567 5325 6300 3049 5378 9129 6921 5313 9471 9705 7350 7360 1923 107 219 1110 9836 2867 8386 2290 7486 8872 2663 8492 730 
5867 8841 8856 5413 1612 2596 5748 5338 7189 203 5146 1741 595 8910 7746 4155 9357 3261 7284 2035 3615 2738 6013 7593 7917 1633 9843 2925 754 4269 7264 8673 5793 7381 6835 7263 7709 6751 7766 1013 8521 7056 6920 4360 
7443 2273 3418 9801 8378 8974 8954 9246 4411 6370 7927 5950 7904 5051 6515 7396 8136 1045 3969 6132 5834 3021 2540 3863 5369 8259 4713 3878 938 7348 7709 8282 2613 8476 5590 9457 1787 9665 8699 9658 3258 1318 8696 8707 2945 
2046 4951 7421 6082 7912 4707 3529 598 8938 5077 7661 4384 6996 9684 9235 3127 6083 6544 6007 7501 9347 6667 6444 4635 7229 4760 1094 8971 7614 4417 7722 1933 1969 208 5048 8094 1119 8218 1666 7993 522 4744 9958 4152 7693 89 
9612 7380 3771 710 1762 5054 7126 8320 2685 1662 9388 8978 5499 4646 3294 8688 9370 5317 7359 4567 8370 5459 4536 2262 6300 5134 733 971 9561 6144 4359 7153 7467 8628 9912 6814 8260 5362 7016 4115 9541 9460 1306 981 3825 6374 5069 
8361 3493 390 3674 4850 4541 9096 8460 2493 5224 6751 7965 2760 3920 8877 7202 7919 394 5969 8981 4346 5975 3758 2230 4641 1135 1125 9698 4879 3430 4465 1502 1795 4859 9068 1531 2233 5295 3901 906 3839 7849 6098 6405 1623 2772 5385 2056 
9751 8824 6710 8920 1747 4906 1411 1538 5134 184 3420 9440 8450 7965 7169 8679 9609 7117 8177 1438 4561 4963 5590 1412 4378 7282 8360 8899 7026 4281 3187 2305 7333 6235 2890 2116 4971 8843 8424 9320 5605 6329 6432 2684 4828 9772 6893 8386 7931 
9250 2232 1035 1163 989 51 7337 1713 4906 6565 2308 4321 3688 6762 3303 2175 1854 321 8894 8548 2141 9426 8111 3471 6968 5728 468 6697 4772 8928 8778 4151 4531 8724 4829 164 6951 5181 2656 1852 7463 9987 5372 5192 4444 2515 9302 4612 5865 120

Volevo ottimizzare questo codice per correre più velocemente? Come posso farlo? non sono in grado di capire cosa va storto qui?

recursion

posta vinay parekar 12.04.2015 - 18:46

fonte

2 risposte

Leggi altre domande sui tag recursion

Progettazione di entità per un gioco di blackjack - dovrei fare di Card un'entità? Gestione della logica aziendale / Condizioni di convalida della convalida

score 1 · Answer 1

Questo può essere risolto elaborando una riga alla volta, senza retrocedere. Non si usa affatto DFS. Non ti derubò del piacere di venire a una soluzione da solo. Dirò semplicemente la tua attenzione alle possibili somme delle prime quattro righe:

9235 + 9096 +  973 + 3399
9235 + 9096 +  973 + 3350
9235 + 9096 + 3269 + 3350
9235 + 9096 + 3269 + 4788
9235 +  637 + 3269 + 3350
9235 +  637 + 3269 + 4788
9235 +  637 + 7039 + 4788
9235 +  637 + 7039 + 2476

Se pensi di elaborare questa linea per volta, puoi vedere che ci sono sia molti calcoli ripetuti qui, sia alcuni percorsi che puoi ovviamente eliminare. Ad esempio, un percorso che inizia con 9235 + 637 + 3269 sarà sempre più piccolo di un percorso che inizia con 9235 + 9096 + 3269 , quindi puoi sfoltirlo. Ogni nuova linea ti consente di sfoltire quasi la metà dei nuovi percorsi. Scopri cosa sono e come evitare di ripetere le somme e troverai che la risposta è abbastanza semplice.

score 0 · Answer 2

La predizione è fattibile solo se è possibile utilizzare qualsiasi euristica basata sulle proprietà dell'albero che si sta analizzando, se è generale e senza proprietà speciali per la struttura o il valore, si rischia di sfidare la risposta corretta. Questo ti lascia con ancora dover analizzare tutto l'albero.

Dato che quello che stai facendo non implica la modifica dell'albero, una possibile opzione è quella del multithreading (dato che vedo che stai codificando in Java) per migliorare l'esecuzione della velocità.