Back

ⓘ Problem najdužeg puta




                                     

ⓘ Problem najdužeg puta

U teoriji grafova i teoretskoj kompjuterskoj nauci, problem najdužeg puta je problem pronalaženja prostog puta najveće dužine u datom grafu. Put je prost ako se u njemu ne ponavlja nijedan čvor; dužina puta može se meriti ili brojem njegovih grana, ili sumom težina grana težinskog grafa. Nasuprot Problemu najkraćeg puta, koji može biti rešen u polinomijalnom vremenu kod grafova bez cicklusa negativnih težina, problem najdužeg puta je NP-težak problem, što znači da se ne može rešiti u polinomijalnom vremenu za proizvoljne grafove sem ako je P = NP. Rezultati jače težine pokazuju da je teško algoritmički aproksimirati. Medutim, postoji rešenje u linearnom vremenu za usmerene aciklične grafove, što ima značajnu ulogu u pronalasku kritičnog puta u problemima zakazivanja.

                                     

1. NP-težina

Np-težina netežinskog problema najdužeg puta se može pokazati korišćenjem redukcije problema Hamiltonovog puta: graf G ima Hamiltonov put ako i samo ako njegov najduži put ima dužinu n − 1, gde je n broj čvorova u G. Iz razloga što je Hamiltonov put NP-kompletan problem, ova redukcija pokazuje da je problem najdužeg puta takode NP-kompletan problem. U ovom problemu, ulaz je graf G i broj k ; željeni izlaz je da ukoliko G sadrži put od k ili više grana, i ne u suprotnom.

Ako bi se problem najdužeg puta mogao rešiti u polinomijalnom vremenu, mogao bi se koristiti da reši ovaj problem odluke, tako što bi se pronašao najduži put i onda poredila njegova dužina sa brojem k. Stoga, problem najdužeg puta je NP-težak. Nije NP-kompletan, zato što nije problem odluke.

U usmerenim kompletnim grafovima sa ne-negativnim težinama grana, težinski problem najdužeg puta je isti kao i problem trgovačkog putnika, zato što najduži put uvek uklučuje sve čvorove.

                                     

2. Aciklični grafovi i kritični putevi

Najduži put izmedu dva zadata čvora s i t u težinskom grafu G je ista stvar kao i najkraći put u grafu − G izvedenom iz G menjanjem svake težine u svoju negaciju. Stoga, ako se najkraći putevi mogu pronaći u − G, tada najduži putevi se takode mogu pronaći u G.

Za većinu grafova, ova transformacija nije korisna zato što stvara cikluse negativne dužine u − G. Ali ako G je usmereni aciklični graf, tada ne mogu biti stvoreni nikakvi negativni ciklusi, i najduži put u G se može pronaći u linearnom vremenu tako što primenimo algoritam linearnog vremena za najkraće puteve u − G, što je takode usmereni aciklični graf. Na primer, za svaki čvor v u datom grafu, dužina najdužeg puta, koji se završava sa v, može se dobiti u sledećim koracima:

  • Za svaki čvor v grafa, u topološkom uredenju, izračunati dužinu najdužeg puta koji se završava sa v gledajući naredne komšije i dodajući jedan na maksimalnu dužinu zabeleženu za te komšije. Ako v nema naredne komšije, postaviti dužinu najdužeg puta, koji se završsava sa v, na nulu. U oba slučaja, zabeležiti ovaj broj tako da naredni koraci algoritma mogu da mu pristupe.
  • Pronaći topološko uredenje datog grafa

Kada je ovo učinjeno, najduži put u celom grafu može se dobiti započinjanjem od čvora v sa najvećom zabeleženom vrednošću, a onda ponavljanje koraka u nazad na njegovog narednog komšiju sa najvećom zabeleženom vrednošću, i obrtanje niza čvorova koji su pronadeni ovim putem.

Metod kritičnog puta za zakazivanje skupa aktivnosti uključuje konstrukciju usmerenog acikličnog grafa tako da čvorovi predstavljaju prekretnice projekta a grane predstavljaju aktivnosti koje moraju biti učinjene nakon jedne prekretnice i pre druge; svaka grana ima težinu koja se meri procenom količine vremena koja je potrebna da se ispuni neka aktivnost. U ovakvom grafu, najduži put od prve prekretnice do poslednje je kritični put, koji opisuje ukupno vreme potrebno za izvršenje projekta.

Najduži putevi usmerenog acikličnog grafa se mogu takode upotrebiti u slojevitom grafičkom crtanju: svaki čvor v usmerenog acikličnog grafa G predstavlja sloj čiji broj je dužina najdužeg puta koji se završava sa v.

                                     

3. Aproksimacija

Bjorklund, Husfeldt i Khanna 2004 napisali su da je problem najdužeg puta u netežinskim neusmerenim grafovima "poznat po težini razumevanje njegove aproksimacije težine". Algoritam aproksimacije u najboljem polinomijalnom vremenu poznat za ovaj slučaj beleži vrlo slab odnos aproksimacije, n / exp ⁡ Ω log ⁡ n) {\displaystyle n/\exp\Omega {\sqrt {\log n}})}. Za sve ϵ > 0 {\displaystyle \epsilon > 0}, nije moguće aproksimirati najduži put do faktora 2 log ⁡ n 1 − ϵ {\displaystyle 2^{\log n^{1-\epsilon }}} sem ako NP nije sadržan u okviru kvazi-polinomijalnog determinističkog vremena; medutim, postoji veliki raskorak izmedu nemogućnosti aproksimacije rezultata i poznate aproksimacije algoritma za ovaj problem.

U slučaju netežinskog ali usmerenog grafa, poznati su snažni rezultati nemogućnosti aproksimacije. Za svaki ϵ > 0 {\displaystyle \epsilon > 0} problem ne može biti aproksimiran do faktora n 1 − ϵ {\displaystyle n^{1-\epsilon }} sem ako je P=NP, i sa snažnim pretpostavkama teoretske kompleksnosti ne može biti aproksimirano do faktora n / log 2 + ϵ ⁡ n {\displaystyle n/\log ^{2+\epsilon }n}.



                                     

4. Parametrizovana kompleksnost

Problem najdužeg puta je prilagodljiv fiksnom parametru kada se parametrizuje dužinom puta. Na primer, može biti rešen u vremenu linearnom veličini ulaznog grafa ali eksponencijalnom dužini puta, algoritmom koji prati sledeće korake:

  • Primeniti dinamičko programiranje na ovu dekompoziciju puta da se pronade najduži put u vremenu O d! 2 d n {\displaystyle Od!2^{d}n}, gde n {\displaystyle n} je broj čvorova grafa.
  • Izvršiti pretragu grafa u dubinu. Neka d {\displaystyle d} bude dubina dobijenog stabla pretrage u dubinu.
  • Koristiti niz koren-list puteva pretrage u dubinu, u redosledu u kom su predeni pretragom, da se napravi dekompozicija puta grafa, sa širinom puta d {\displaystyle d}.

Kako izlazni put ima dužinu veličine bar d {\displaystyle d}, vreme trajanja je takode ograničeno sa O ℓ! 2 ℓ n {\displaystyle O\ell!2^{\ell }n}, gde ℓ {\displaystyle \ell } je dužina najdužeg puta. Koristeći kodiranje bojama, zavisnost dužine puta može se smanjiti na jedinstvenu eksponencijalnu. Slične tehnike dinamičkog programiranja pokazuju da problem najdužeg puta je takode prilagodljiv fiksnom parametru kada se parametrizuje širinom drveta grafa.

Za grafove ograničene širinom klike, najduži put može biti rešen u polinomijalnom vremenu algoritmom dinamičkog programiranja. Medutim, polinomijalni eksponent zavisi od širine klike grafa, pa ovaj algoritam nije prilagodljiv fiksnom parametru. Problem najdužeg puta, parametrizovan širinom klike, je težak za klasu parametrizovane kompleksnosti W }, što pokazuje da algoritam prilagodljiv fiksnom parametru verovatno ne postoji.

                                     

5. Specijalni slučajevi grafova

Problem najdužeg puta može se rešiti u polinomijalnom vremenu na dopunama uporedivih grafova. Može se takode rešiti u polinomijalnom vremenu na bilo kojoj klasi grafova sa ograničenom širinom stabla ili ograničenom širinom klika, kao što su nasledni grafovi. Medutim, to je NP-teško i kada je ograničeno na rascepljene grafove, kružne grafove, ili pljosnate grafove.

                                     

6. Vidi još

  • Gallai–Hasse–Roy–Vitaver teorema, odnos izmedu najdužeg puta i bojenja grafa
  • Najduži nepresečeni put konja u šahu
  • Zmija u kutiji, najduži indukovani put u grafu hiperkocke
                                     
  • на 545 литара, а помоћни на 180 литара, тако да је могућност преласка најдужег растојања остала иста од 360 km иако му је маса повећана на 39, 15 тона
  • су чворови заједнички кључевима са истим префиксима. Трие олакшава проблем најдужег заједничког префикса. Број унутрашњих чворова од корена до листова
  • удеса ваздухоплова Као нестао сматра се онај ваздухоплов који у времену најдужег могућег трајања лета, рачунајући од последњег полетања, није стигао на
  • simptomatske autonomne disfunkcijom. Petogodišnja smrtnost kod bolesnika je tri puta viša nego kod pacijenata bez autonomnog poremećaja. Vodeći uzroci smrti kod
  • мора поново да упореди одређене знакове, када је већ познато да су део најдужег заједничког префикса за узорак и тренутни интервал претраге. Abouelhoda
  • не мора да поново упоређује одређене карактере, када се већ зна су део најдужег честог префикса обрасца и тренутног интервала претраживања. Abouelhoda

Users also searched:

...