Korlátozott Teljesítési Problémák (CSPs)

A CSP alkalmazásai közé tartozik a csapatok párbajainak két alkalomra való ütemezése, figyelembe véve a korlátozásokat.

A CSP csomagolási problémáinak szempontjai közé tartozik a tér, a méret és az idő korlátozása.

A Golomb-rendező célja, hogy az éppen kijelölt helyeken lévő jelölések között minden jelölés különböző távolságokat tartson fenn.

<p>Fujita et al. (1993) bizonyította, hogy bizonyos méretű quasigroups nem léteznek.</p> Signup and view all the answers

<p>A problémák megoldásában léteznek nem-informált és informált keresési stratégiák.</p> Signup and view all the answers

<p>A <em>Forward Checking</em> célja, hogy előre ellenőrizze a jövőbeli változók lehetséges értékeit és eltávolítsa azokat, amelyek ütköznek a megadott korlátokkal.</p> Signup and view all the answers

<p>Az <em>Arc Consistency</em> biztosítja, hogy minden elágazásban a változók értékei közötti kapcsolat megfeleljen a megadott korlátoknak, így elkerülve az ellentmondásokat.</p> Signup and view all the answers

<p>Ha bármelyik jövőbeli változó értéke üres lesz, az azt jelenti, hogy az adott változónak nincs legális értéke, ami ellentmondáshoz vezetne.</p> Signup and view all the answers

<p>Az <em>Arc Consistency</em> algoritmus segít csökkenteni a keresési tér méretét azáltal, hogy eltávolítja azokat az értékeket, amelyek ütköznek a korlátokkal.</p> Signup and view all the answers

<p>A <em>Forward Checking</em> úgy működik, hogy eltávolítja azokat az értékeket, amelyek ütköznek a korlátokkal, így a megoldásokra nem hat ki, mivel ezek az értékek amúgy sem lehetnek részei a megoldásnak.</p> Signup and view all the answers

<p>Mert a rendszer korlátozottan tudja kezelni a változók közötti kapcsolatokat, és nem tud minden lehetséges ellentmondást észlelni.</p> Signup and view all the answers

<p>Az ívkonzisztencia egy speciális eset, ahol k=2, míg a k-konzisztencia általánosan k változóra vonatkozik.</p> Signup and view all the answers

<p>Az MRV heurisztika a legkorlátozottabb változo(ka)t telepíti először, ezáltal segít a halálos végek korai észlelésében.</p> Signup and view all the answers

<p>Az LCV olyan értékeket választ, amelyek a legkevesebb lehetséges értéket zárják ki a maradék változók számára.</p> Signup and view all the answers

<p>A változó sorrendje befolyásolja a keresés hatékonyságát és gyorsabb megoldást eredményezhet.</p> Signup and view all the answers

<p>A globális korlátozások, mint például az 'all-different', csökkenthetik a megoldási térfogatot és egyszerűsíthetik a problémát.</p> Signup and view all the answers

<p>Például a CHIP, ILOG Solver és Prolog CPLFD, amelyek könnyű és általános problémák megoldására készültek.</p> Signup and view all the answers

<p>A legjobb keretek használata jelentős mértékben felgyorsíthatja a keresést, különösen komplex problémák esetén.</p> Signup and view all the answers

<p>A függvény eltávolítja azokat az értékeket a DOMAIN[xj]-ből, amelyek nem felelnek meg a C(xi, xj) feltételnek.</p> Signup and view all the answers

<p>A dinamikus CSP-k olyan problémák megoldására szolgálnak, amelyek közben változnak, míg a hagyományos CSP-k statikusak.</p> Signup and view all the answers

<p>Az ívkonzisztencia azt jelenti, hogy minden egyes változó értéke számára léteznie kell egy másik változó értékének, amely kielégíti a megadott korlátozást.</p> Signup and view all the answers

<p>A szimmetria-észlelés segít új változók halmazát találni, ami gyorsabb megoldáshoz vezet.</p> Signup and view all the answers

<p>A C2 korlátozás alapján a 9, 10 és 11 értékek eltávolíthatók a DstartA-ból.</p> Signup and view all the answers

<p>A célja új korlátozások találása a hatékonyabb problémamegoldás érdekében.</p> Signup and view all the answers

<p>A QUEUE frissítése biztosítja, hogy az összes kapcsolatot ellenőrizzék a konzisztenciához, így elkerülve a megoldhatatlanságot.</p> Signup and view all the answers

<p>A hosszúságoknak különbözőnek kell lenniük, és a négyzetek területének összege kell, hogy egyenlő legyen az utolsó négyzet területével.</p> Signup and view all the answers

<p>A C3 korlátozás a startA + 3 ≤ startC feltételt írja elő.</p> Signup and view all the answers

<p>Fontos, mert a különbözőség segít elkerülni a redundanciát és optimalizálni a megoldás keresését.</p> Signup and view all the answers

<p>A CSP a hosszúságokat az $L1, L2, …, L25$ változók segítségével definiálja, amelyek az 1 és Top közötti értékekre korlátozva vannak.</p> Signup and view all the answers

<p>Az ívkonzisztencia hatékonyan eltávolít minden olyan értéket, amely nem szerepelhet egy lehetséges megoldásban.</p> Signup and view all the answers

<p>Az $L1<em>L1 + L2</em>L2 + … + L24<em>L24 = L25</em>L25$ egyenletet használják a négyzetek területének kiszámításához.</p> Signup and view all the answers

<p>Új elem akkor adható hozzá a QUEUE-hoz, ha a <code>REMOVE-INCONSISTENT-VALUES</code> eltávolítja az értékeket az egyik változóból.</p> Signup and view all the answers

<p>A hosszúságok összegei biztosítják a geometriai tulajdonságokat és a megfelelő megoldást a CSP-ben.</p> Signup and view all the answers

<p>A feladatok indítási időpontjai a precedencia kapcsolatok figyelembevételével és a korlátozások alapján kerülnek meghatározásra.</p> Signup and view all the answers

<p>A visszafelé történő munka biztosítja, hogy a legfelsőbb szintű korlátozások is figyelembe legyenek véve, így a korábbi feladatok befolyásolják a későbbiakat.</p> Signup and view all the answers

<p>A globális start és finish változók meghatározzák a feladatok végrehajtásának ütemezését és határidejét.</p> Signup and view all the answers

<p>A CSP elemei: változók halmaza, minden változó lehetséges értékeinek halmaza és a korlátok halmaza.</p> Signup and view all the answers

<p>A bináris korlátok grafikus és mátrixos reprezentációt tesznek lehetővé, amelyek megkönnyítik a CSP-k megértését.</p> Signup and view all the answers

<p>Az előrehaladást ellenőrző módszerek a korlátok betartását segítik biztosítani, csökkentve ezzel a megoldás keresésének idejét.</p> Signup and view all the answers

<p>A leggyakoribb keresési technikák a visszalépés, előrehaladást ellenőrző módszerek és a korlátozások terjesztése.</p> Signup and view all the answers

<p>Az egyes korlátok egy változóra vonatkoznak, míg a kettős korlátok két változó közötti kapcsolatot határoznak meg.</p> Signup and view all the answers

<p>Az intelligens visszalépés a lehetséges konfliktusok tárolására és a visszaugrásra épít az értékek korábbi rendelésének megfelelésére.</p> Signup and view all the answers

<p>A tűzoltási módszer célja a változók értékeinek megváltoztatása a lehetséges hibák minimalizálása érdekében.</p> Signup and view all the answers

<p>A legfontosabb feladatok közé tartozik a változók és a korlátok definiálása, valamint a keresési stratégia kiválasztása.</p> Signup and view all the answers

<p>A 4 vezérlő bábú problémája egy standard példa, melyben a változók a sorok, míg az értékek az oszlopok, és különböző korlátok vannak.</p> Signup and view all the answers

<p>A konzisztencia biztosítja, hogy a változók értékei megfeleljenek a korlátoknak, amely lehetővé teszi a megoldás érvényességét.</p> Signup and view all the answers