polunpituudella

Polunpituudella tarkoitetaan mittaa, joka kuvaa kuljetun matkan pituuden jonkin reitin tai polun varrella. Käsite esiintyy sekä diskretissä grafiteoriassa että jatkuvissa käyrissä, ja sen tarkka määritelmä riippuu kontekstista. Yleisesti polunpituus mittaa kuljetun matkan pituutta reunan tai käyrän pituuden summana.

Graafiteoriassa polunpituus määritellään painotetussa graafissa G=(V,E) painofunktion w:E→R+. Polku P on jono verticeja ja reunoja, esimerkiksi P = v0, v1, ..., vk, jossa jokainen pari (v_{i-1}, v_i) on yhdistetty reunalla. Reunien pituudet l_i = w(v_{i-1}, v_i) summataan: L(P) = w(v0,v1) + w(v1,v2) + ... + w(v_{k-1}, v_k). Jos graafi on unweighted, jokaisella reunalla on paino 1, joten L(P) on reuna-iden lukumäärä. Lyhyin polku on polku, jonka pituus on pienin, ja useimmat lyhyimmän polun ongelmat ratkaistaan käyttäen BFS:iä unweighted-verkossa tai Dijkstraa/A*-algoritmia painotetuissa verkoissa.

Jatkuvissa yhteyksissä polunpituutta tarkastellaan käyrän kaaren pituutena. Olkoon r: [a,b] → R^n parametrisoitu käyrä, jolloin kaaren pituus on L = ∫_a^b |r'(t)| dt. Tämä määritelmä tunnetaan arc length -käsitteenä ja se johtaa perinteisiin tuloksiin käyrien geometriassa ja analyysissä. Käytännössä käyrän pituus voidaan approksimoida jakamalla käyrä pieniin segmenteihin ja summamalla niiden pituudet.

Ominaisuudet: L(P) on aina ≥ 0, ja L(P) = 0 tapahtuu vain, kun polku on degeneraatioltaan nolla (tyhjä polku tai vakio-käyrä). Monotoniikka ja kolmioepäyhtälöanalyysi ovat keskeisiä lyhyin- ja reititysongelmien yhteydessä.

Sovellukset kattavat reititys, logistiikka, verkkoanalyysi sekä robotiikka ja geometriakäytännöt. Terminä polunpituus kuvaa yleisesti mittaa, joka tilastoi tai optimoi kuljetun matkan pituuden eri konteksteissa.