Aké sú rozdiely medzi najširšou cestoua najdlhšia cesta? Presnejšie povedané, prečo je možné prvý z nich vyriešiť nájdením maximálneho preklenovacieho stromu, zatiaľ čo druhý nemôže. Pri vykresľovaní maximálneho preklenovacieho stromu viem, že je okamžite zrejmé, že nevyhnutne neobsahuje najdlhšiu cestu, ale nedokážem zabaliť svoju myseľ okolo rozdielov medzi dvoma otázkami, ktoré túto skutočnosť potvrdzujú.
Vďaka.
odpovede:
1 pre odpoveď č. 1Hlavný rozdiel medzi týmito dvomi problémami je v tom, že problém najširšej cesty vykazuje optimálnu spodnú štruktúru, zatiaľ čo problém najdlhšej cesty (podľa najlepších vedomostí niekoho iného) ho nemá.
Konkrétne zvážte najširšiu cestu z auzol u k uzlu v. Ak táto cesta prechádza cez sprostredkujúce uzly s, potom najširšia cesta od u do musí pozostávať z najširšej cesty od u do, po ktorej nasleduje najširšia cesta od s do v. , potom môžete nahradiť buď časť cesty z u do s alebo z do do ešte širšou cestou bez zhoršenia riešenia.
Toto však nefunguje pre problém najdlhšej cesty. Ak vyberiete najdlhšiu cestu (implicitne najdlhšiu jednoduchú cestu) z u na v a prechádza cez niektoré uzly, nie nevyhnutne musí mať najdlhšiu cestu od u do s, po ktorej nasleduje najdlhšia cesta od s do v. Tu je príklad:
2
u --- v
1 / 3
s
Najdlhšia cesta od u do s pozostáva z cesty u - v - s (dĺžka 5), zatiaľ čo najdlhšia cesta od u do v je u - s - v (dĺžka 4).
Táto optimálna vlastnosť spodnej vrstvy to robíje možné použiť chamtivé algoritmy a (efektívne) dynamické programovanie na efektívne vyriešenie problému s najširšou cestou, ale (podľa najlepších znalostí niekoho iného) nie je možné efektívne vyriešiť problém s najdlhšou cestou. Podobné argumenty môžete uviesť aj v prípade najkratších ciest. spôsob (ak najkratšia cesta od u do v prechádza s, máte zreťazenie najkratších ciest od u do sa od s do v) a na určenie najkratších ciest môžete použiť podobné chamtivé algoritmy alebo DP.
Dúfam, že to pomôže!