Pirsgirêka rê û çawa dikare bi karanîna algorîtmayek nîşankirinê were çareser kirin rave bike.
Pirsgirêka rê pirsgirêkek bingehîn e di teoriya tevliheviya hesabkirinê de ku di grafekê de rêyek di navbera du xalan de peyda dike. Ji ber grafiyek G = (V, E) û du xalên s û t, armanc ew e ku were destnîşankirin ka rêyek ji s ber bi t di G de heye yan na.
Ji bo çareserkirina pirsgirêka rê, yek nêzîkatî karanîna algorîtmayek nîşankirinê ye. Algorîtmaya nîşankirinê teknîkek hêsan û bikêrhatî ye ku dikare were bikar anîn da ku diyar bike ka rêyek di navbera du xalên grafîkî de heye yan na.
Algorithm bi vî rengî dixebite:
1. Dest bi nîşankirina verteksa destpêkê s wekî serdan kirin.
2. Ji bo her verteksa v li tenişta s-yê, v wekî serdan nîşan bikin û li dorê zêde bikin.
3. Dema ku rêz ne vala ye, gavên jêrîn dubare bikin:
yek. Vertex u ji rêzê derxînin.
b. Ger u berika mebest t be, wê demê rêyek ji s ber bi t hatiye dîtin.
c. Wekî din, ji bo her verteksa v li tenişta u ya ku nehatibe serdan, v wekî serdankirî nîşan bikin û li dorê zêde bikin.
Algorîtmaya nîşankirinê stratejiya gerokê ya yekem-firehiya (BFS) bikar tîne da ku grafîkê bikole û vertîkên wekî serdan nîşan bide. Bi kirina vê yekê, ew piştrast dike ku her verteksa ku ji berika destpêkê bigihîje tê serdan kirin, rê dide algorîtmayê ku diyar bike ka rêyek di navbera berika destpêk û armancê de heye yan na.
Tevliheviya demê ya algorîtmaya nîşankirinê O(|V| + |E|) e, li wir |V| di grafîkê de hejmara ristên deq û |E| ye hejmara kevanan e. Ev e ji ber ku algorîtm carekê seredana her vertex û her keviyekê dike. Di warê teoriya tevliheviya hesabkirinê de, algorîtmaya nîşankirinê ji pola P-yê ye, ku pirsgirêkên ku dikarin di dema polînomî de werin çareser kirin temsîl dike.
Li vir mînakek heye ku sepana algorîtmaya nîşankirinê nîşan bide:
Grafika jêrîn bifikirin:
A --- B --- C | | D --- E --- F
Em bibêjin ku em dixwazin diyar bikin ka rêyek ji xala A-yê berbi berika F-yê heye an na. Em dikarin algorîtmaya nîşankirinê wekî jêrîn bikar bînin:
1. Bi nîşankirina vertex A wekî serdan dest pê bikin.
2. Vertex A li dorê zêde bikin.
3. Vertex A ji rêzê derxînin.
4. Vertex B wekî serdan nîşan bidin û wê li dorê zêde bikin.
5. Vertex B ji dorê derxînin.
6. Vertex C wekî serdan nîşan bikin û wê li dorê zêde bikin.
7. Vertex C ji dorê derxînin.
8. Vertex D wekî serdan nîşan bidin û wê li dorê zêde bikin.
9. Vertex D ji dorê derxînin.
10. Vertex E wekî serdan nîşan bikin û wê li dorê zêde bikin.
11. Vertex E ji dorê derxînin.
12. Vertex F wekî serdan nîşan bide.
13. Ji ber ku lêkera F lêkera mebestê ye, ji A ber bi F ve rêyek hatiye dîtin.
Di vê nimûneyê de, algorîtmaya nîşankirinê bi serfirazî destnîşan dike ku rêyek ji vertex A berbi vertex F heye.
Pirsgirêka rê di teoriya tevliheviya hesabkerî de peydakirina rêyek di navbera du xalên di grafekê de ye. Algorîtmaya nîşankirinê teknîkek hêsan û bikêrhatî ye ku dikare ji bo çareserkirina vê pirsgirêkê bi pêkanîna gerokek berfireh-yekemîn û nîşankirina vertîkên wekî serdankirî were bikar anîn. Algorîtma xwedan tevliheviya demê ya O(|V| + |E|) ye û ji çîna P ye.
Pirs û bersivên din ên vê dawiyê di derbarê Tevlîheviyê:
- Ma pola PSPACE ne bi pola EXPSPACE re wekhev e?
- Ma pola tevliheviya P binkomek pola PSPACE ye?
- Ma em dikarin îsbat bikin ku çîna Np û P yek in bi dîtina çareseriyek polînomî ya bikêr ji bo her pirsgirêkek bêkêmasî ya NP li ser TM-ya diyarker?
- Ma pola NP dikare bi çîna EXPTIME re wekhev be?
- Di PSPACE de pirsgirêk hene ku ji bo wan algorîtmaya NP-ya naskirî tune?
- Ma pirsgirêkek SAT dikare bibe pirsgirêkek tevahî NP?
- Ma dibe ku pirsgirêk di pola tevliheviya NP de be heke makîneyek ziravî ya ne diyarker hebe ku dê di dema pirnomî de wê çareser bike
- NP çîna zimanên ku xwedan verastkerên dema pirnomî ne
- Ma P û NP bi rastî heman çîna tevliheviyê ne?
- Ma her çarçoveyek zimanek azad e di pola tevliheviya P de?
Pir pirs û bersivan di Complexity de bibînin