Nevezetes problémák

Mesterséges intelligencia alapok

2026

Problémák csoportosítása

• Megoldási idő szerint
• P (Polynominal)
• Viszonylag egyszerűen megoldható problémák
• P tipusú egy probléma, ha létezik olyan problémamegoldó algoritmus, melynek időszükséglete legfeljebb N polinomjával függ össze
• NP (Non-deterministic polynomial)
• „Nehéz” problémák
• Azok a problémák, melyek bármely feltételezett megoldása polinomiális idő alatt eldönthető, hogy helyes-e egy determinisztikus Turing gép segítségével
• Vagy azok a problémák, amelyek megoldhatóak polinomiális idő alatt nemdeterminisztikus Turing gép segítségével
• NP-teljes (NP complete)
• A legnehezebben megoldható problémák
• Nagy változószám esetén megoldhatatlan
• A megoldáshoz szükséges idő e^N (vagy n!) szerint változik
• NP-nehéz (NP hard)
• Olyan problémák, amelyre minden NP-beli probléma visszavezethető
• De nem kell NP-nek lennie (Valóban nem is eldönthetők)

​

P problémák

Áramkör érték probléma�(Circuit Value Problem)

• Logikai áramkör kimenetének kiszámításának problémája egy adott bemeneten
• Lineáris időben, topológiai rendezéssel megoldható
• Speciális esete: Bool képletkiértékelési probléma
• Az áramkör egy fa

3SUM

• Adott n valós számból álló halmaz
• Kérdés: tartalmaz-e három olyan elemet, amelyek összege nulla
• Általánosítása:
• k-SUM: tartalmaz-e k számú elemet, amelynek összege nulla
• Időigénye: O(n²)

Hozzárendelés probléma

• A probléma ügynököket és feladatokat tartalmaz
• Bármely ügynök hozzárendelhető bármilyen feladat végrehajtásához
• Ügynök-feladat összerendeléstől függő költségekkel jár
• A lehető legtöbb feladatot úgy kell elvégezni, hogy
• Minden feladathoz legfeljebb egy ügynököt rendelnek
• Minden ügynökhöz legfeljebb egy feladatot rendelnek
• Hozzárendelés összköltsége minimális legyen
• Ha az ügynökök és a feladatok száma megegyezik, akkor kiegyensúlyozott hozzárendelésnek nevezik, különben kiegyensúlyozatlan hozzárendelésnek
• Ha a hozzárendelés összköltsége az összes feladatra megegyezik az egyes ügynökök költségeinek összegével, akkor lineáris hozzárendelésnek nevezzük

​

Ütközés probléma

• Leggyakrabban az elnevezés a 2 az 1-hez verziót jelenti
• Adott egy páros n és egy f: {1,…,n} -> {1,…,n} függvény
• A függvény 1 az 1-hez (injektív) vagy 2 az 1-hez hozzárendeléssel rendelkezik
• Csak az f(i) értékeire tehetünk lekérdezést
• Kérdés: Hány lekérdezés szükséges, hogy�megállapítsuk, hogy f 1 az 1-hez �vagy 2 az 1-hez

Legkisebb élfedés probléma�(Minimum edge cover problem )

• Élfedés: az élek részhalmaza, gráfélek gyűjteménye úgy, hogy az élvégpontok uniója megfelel a gráf teljes csúcskészletének
• Csak elszigetelt pont nélküli gráfoknak van élfedése
• Legkisebb lefedés: A legkevesebb élből álló halmaz, amely élfedést valósít meg

Elem megkülönböztetési probléma

• Annak az eldöntésére szolgál, hogy egy lista összes elemei különböző-e
• A probléma megoldható a lista rendezésével, majd annak ellenőrzésével, hogy vannak-e egymást követő egyenlő elemek
• Akár lineáris várható időben is megoldható
• Általánosítása: Ismétlő elemek megtalálása

Üresség probléma

• Formális nyelvek témakörben
• Üres formális nyelv: Ha egyetlen valid mondata, eleme sincsen (Még az üres jelsorozat sem)
• Probléma: Eldönteni adott reprezentáció alapján, hogy üres-e a nyelv
• Reprezentáció lehet például a véges állapotú automata
• n állapotú automata esetén a probléma O(n²) idő alatt elvégezhető
• Egyes variánsai már nem ilyen könnyen megoldhatóak

Leghosszabb közös részsorozat probléma

• Célja: Megtalálni a leghosszabb részsorozatot, amely az összes szekvenciára jellemző egy sorozathalmazban
• Gyakran csak két szekvenciában
• Tetszőleges számú bemeneti sorozat esetén NP-nehéz
• Ha a szekvenciák száma konstans, a probléma megoldható polinomiális időn belül dinamikus programozással

​

NP-teljes problémák�

Bool-féle kielégítési probléma �(Boolean satisfiability problem (SAT))�

• Első ismert NP-teljes probléma (igazolva Stephen Cook által 1971-ben és Lenid Levin által 1973-ban)
• Kérdés:
• Van-e olyan interpretációja egy adott Boole- formulának, amely azt kielégíti
• Más szavakkal, annak az eldöntése, hogyha az adott formula változóit konzisztensen lecseréljük IGAZ vagy HAMIS értékekkel, akkor a képlet IGAZ értéket ad-e
• Ebben az esetben a formula kielégíthető
• Ha minden lehetséges behelyettesítésre HAMIS, akkor kielégíthetetlen

​

3-SAT probléma�(3-satisfiability problem)

• A SAT egy speciális esete
• A formula konjuktív normálformában van megadva, ahol minden tagmondat legfeljebb három literálra korlátozódik
• (x ∨ x ∨ y) ∧ (¬x ∨ ¬y ∨ ¬y) ∧ (¬x ∨ y ∨ y)
• Minden tagmondatban van legalább egy IGAZ literálja
• Ez alapján bizonyítják más problémák NP-nehézségét
• Speciális esetei:
• Konjuktív normálformában megadva, pontosan három literál egy tagmondatban
• Diszjunktív normálformában
• 1-in-3 SAT: Konjuktív normálforma, pontosan három literállal egy tagmondatban, de minden tagmondatban csak egy IGAZ literál lehet
• Lineáris SAT: Ha minden tagmondatnak csak egy másik tagmondattal van metszete, és a metszetükben csak egy literál lehet közös

​

Gráf Hamilton köre/útja

• Hamilton kör: Olyan kör egy gráfban, amely a gráf összes csúcsán pontosan egyszer halad át
• NP-teljes bizonyítása a csúcsfedés probléma� segítségével
• Hamilton út: Olyan út egy gráfban, amely a gráf �összes csúcsán pontosan egyszer halad át
• NP-teljes probléma:
• Páros gráf
• Irányítatlan síkba rajzolható gráfok maximum 3-as �fokszámmal
• Irányított síkba rajzolható gráfok maximum 2 bemeneti és kimeneti fokkal
• Hídmentes irányítatlan síkba rajzolható, 3-regulális páros gráf
• A négyzetrács gráf részgráfjai

​

Klikk eldöntési probléma�(Clique problem)

• Klikk: egy irányítatlan gráf csúcsainak olyan halmaza, melyek feszített részgráfja teljes
• A klikk bármely két csúcsa között van él, bármely két csúcsa szomszédos
• Kérdés:
• Bemenet: irányítatlan gráf, k paraméter (pozitív egész)
• A gráfban van-e k méretű klikk

​

​

Minimum lefedő csúcshalmaz eldöntési probléma�(Minimum vertex cover problem)

• Lefedő csúcshalmaz: A gráf csúcsainak egy olyan halmaza, amely a gráf minden élének legalább egy végpontját tartalmazza
• Adott gráf, k paraméter (pozitív egész)
• Kérdés:
• A gráfnak van-e legalább k méretű lefedő csúcshalmaza

​

Hátizsák probléma

• Adott- elemek halmaza. Minden elemnek van:
• Értéke
• Súlya
• Paramétere: Súlykorlát
• Cél:
• Meghatározni minden elem darabszámát, hogy az összsúlyuk ne haladja meg a súlykorlátot, de az összérték a lehető legnagyobb legyen
• A probléma először 1897-ben jelent meg

NP-nehéz

Utazóügynök probléma�(Travelling salesperson problem- TSP)

• Adott városok listái, és köztük lévő távolság
• Kérdés:
• Mi a legrövidebb út, amely az összes várost pontosan egyszer érinti, és visszatér a kezdő városba?
• Először 1930-ban fogalmazták meg
• Az optimalizáló megoldások számára viszonyítási alap
• Tervezésben, logisztikában, és mikrochip gyártásban jelentős gyakorlati felhasználása van
• Módosított változatai DNS szekvenálás és asztronómia témakörében is hasznosított
• Heurisztika és optimális utat eredményező algoritmus már ismert, milliós városoknál nagyon jól közelíthető

Minimum lefedő csúcshalmaz probléma

• Lefedő csúcshalmaz: A gráf csúcsainak egy olyan halmaza, amely a gráf minden élének legalább egy végpontját tartalmazza
• Kérdés:
• A legkisebb lefedő csúcshalmaz megkeresése az adott gráfban
• Visszaadja a k értéket

Teljes színezés

• A gráf csúcsaihoz és éleihez is szín van rendelve
• A szomszédos csúcsok, szomszédos élek, és az él és azok végpontjai sem lehetnek ugyanolyan színűek
• Cél a kromatikus szám meghatározása

K-minimum feszítőfa probléma

• 1993-ban jelent meg a probléma
• Bemenete:
• Irányítatlan gráf, súlyozott élekkel
• k paraméter

​

• Célja:
• Minimális költségű fa, amelynek pontosan k csúcsa, k-1 éle van, és egy nagyobb gráf részgráfját képezi

Max-3SAT problem

• Általánosított SAT probléma
• Bemenete:
• Konjuktív normálforma, maximum 3 literállal egy tagmondatban
• Célja:
• Olyan hozzárendelés keresése, amely a legtöbb tagmondatot kielégíti

Metrikus k-középpont

• Adott:
• N város adott távolság függvénnyel
• Cél:
• k db raktár építése a különböző városokban olyan módon, hogy minimalizálja a maximum távolságot a városoktól a raktárakig
• Gráfelméleti megfogalmazás: meg kell találni egy k csúcsból álló halmazt, amelynek bármely pontjának legnagyobb távolsága a legközelebbi csúcstól a k-halmazban minimális

Flow Shop ütemezési probléma

• Adott:
• n darab munka J₁, J₂, …, J_n különböző feldolgozási idővel
• m különböző feldolgozási teljesítményű gép
• Cél:
• A munkákat a gépekre kell ütemezni, miközben megpróbáljuk minimalizálni az átfutási időt (amikor az összes munkát befejeztük)
• Számos variánsa létezik

​

​

​

​

​

A termelésinformatika szakirány �foglalkozik ezzel

Háromdimenziós házasítás�(3-dimensional matching)

• Adott:
• X,Y és Z diszjunkt halmazok, mindegyik n méretű
• T részhalmaza a X x Y x Z- nek (T (x,y,z) hármasokból áll)
• M ⊆ T egy háromdimenziós házasítás ha:
• Bármely kettő különálló hármasra (x1,y1,z1) ∈ M, �és (x2,y2,z2) ∈ M, akkor x1 ≠ x2, y1 ≠ y2, z1 ≠ z2

Rekesz pakoló probléma

• Adott:
• Különböző méretű tételek
• Véges számú, meghatározott tárolóedény vagy konténer
• Cél:
• A tételeket a konténerbe kell csomagolni oly módon, hogy minimalizálja a felhasznált tárolóedények számát
• Alkalmazási területei:
• Konténerek felöltése
• Teherautók betöltése súlykorlátozással

​

​

Leghosszabb út probléma

• Adott:
• Gráf
• Cél:
• A leghosszabb egyszerű útvonal keresése az adott gráfban
• Egyszerű útvonal: Nincs ismétlődő csomópontja
• A hossz lehet
• Az élek száma
• Súlyozott gráf esetén az élek összsúlya

NP problémák

Utazóügynök döntési verzió

• Bemenete egy n város közötti távolságok mátrixa
• Kérdés: Van-e olyan útvonal, amely
• az összes várost meglátogatja
• Teljes távolsága kisebb, mint k
• A feltételezett megoldás lehet egyszerűen a városok listája
• Ekkor az ellenőrzés egyértelműen polinomiális időben végezhető el
• Összeadja a két város közötti útnak megfelelő mátrixértékeket

Részgráf izomorfizmus probléma

• Adott G és H gráfok
• Kérdés: G gráf tartalmaz-e olyan részgráfot, amely izomorf a H gráfhoz
• A maximum klikk probléma és a Hamilton kör tesztelésének általánosítása
• Alapvetően NP-teljes probléma
• A részgráf izomorfizmus bizonyos más esetei megoldhatóak polinomiális időben

Egész faktorizációs probléma döntési verzió

• Adott n és k egész szám
• Van-e olyan f tényező, amelyre igaz, hogy 1 < f < k és f osztja n-t?
• Jelenleg nincs olyan algoritmus, amely az összes egész számot polinomiális időben faktorizálja
• Kvantum számítógépre írt algoritmus meg tudja oldani polinomiális időben