Új hozzászólás Aktív témák

• #40 P.H. senior tag Gabboo #37

  Új Válasz 2008-04-08 20:40:22 #40

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  P.H.

  senior tag

  válasz Gabboo #37 üzenetére

  Az elmélettől elvonatkoztatva érthetőbb lehet a dolog
  Nagyjából arról van szó, hogy addig nem lehet megoldásra jutni, ameddig az összes többi megfelelőbbneknek tűnő, de megoldást nem adó lehetőséget ki nem számoljuk vagy pedig ha van kiindulási eredmény (innen "igen vagy nem" a kérdés), be kell bizonyítani, hogy az összes többi megoldás közt nincs 'jobb' (polinomiális időigény helyett jellemzően legalább faktoriális vagy [n alatt a k] időigény).

  Példa lehet az utazó ügynök (TSP) algoritmus: adott gráfon (pl. legyen az Magyarország ~3200 települése) közül kiválasztva »tetszőlegesen« mondjuk húsz különböző pontot (~települést), mi annak a legrövidebb bejárási sorrendje? (Egyetlen teljes kör, legrövidebb lehetséges élhossz-összeggel). Itt 20! (2 432 902 008 176 640 000) megoldás lehetséges, általában irányítatlan gráf esetén legalább 2 (oda-vissza), irányított gráf (pl. vannak egyirányú utak) esetén minimum 1 jó megoldás van.
  Pl. az eredeti TSP-algoritmust alkalmazva a 20! lehetséges megoldásból a legrövidebb élhossz-összegtől haladva a megoldás felé az összes adódó eredményről meg kell állapítani először, hogy az egynél több kört tartalmaz-e; ha csak egyet, megvan a megoldás. Ha van kiindulási eredmény, akkor az összes nála rövidebbre meg kell nézni, hogy az hány kört tartalmaz.

  Így bármely bemenetre (pl. akárhány - az egyszerűség kedvéért több, mint x - pontos gráfon keresett x pontos körre) lehet mutatni olyan x db pontot, amelyeken ki kell számítani az összes lehetséges x! lehetséges élösszeget a megoldásig.

Új hozzászólás Aktív témák