Tudnátok adni nekem gondolkodó programozási feladatokat?

,,Az 1, 2, 3, ..., n számoknak hány olyan sorrendje van melyben a szomszédos elemek relatív prímek?”

Nézzünk inkább n általános számot, ne 1..n számokat.

Ez NP teljes feladat, sőt, már az is, hogy létezik-e ilyen permutáció. Könnyű visszavezetni a Hamilton-út problémára.

Azt nem tudom, hogy az 1..n speciális eset okoz-e különbséget, speciális lesz-e a graf a számelméleti tulajdonságok miatt, de ez már nem algoritmus/programozási feladat, hanem számelméleti.

"Nézzünk inkább n általános számot, ne 1..n számokat."

Az n számon mit nézel önmagában? Relatív prím nem egy darab szám hanem egy számpár lehet. Egy szám az prím lehet, azt hogy prím e nem NP nehéz feladat, nem csak osztópróbákkal dönthető el. Két számról hogy relatív prím e, nem csak a prímtényezős felbontással dönthető el.

Amúgy igen NP teljes feladat lehet az eredeti felvetett sorrendes probléma.

Legyen "csak" az a feladat hogy 1..n számokhoz mindhez meghatározni hogy melyekkel relatív prímek 1..n számok közül. Több féle módon is, melyik módszer a gyorsabb versenyeztetni egymással. Én kétfajtaképpen is implementáltam, a második gyorsabb (optimalizáltam).

#11:

A Hamilton-út problémát kéne visszavezetni erre a problémára az NPC-beliség igazolásához.

Pl egy ötlet: van egy G gráfunk, amiben Hamilton utat akarunk keresni. A G gráf komplementerének az éleire rakunk 1-1 különböző prímet, majd a csúcsaiba beírjuk az élek szorzatát. Ebben a gráfban két csúcs pontosan akkor relatív prím, ha megy közöttük él. Egy felsorolás így egy Hamilton-útnak felel meg.

Azt nem tudom, hogy lehet-e találni pol időben prímeket, és hogy mekkorák lesznek. Valaki?

@15:

Elírtam a visszavezetést, ugyan ez a konstrukció jutott eszembe nekem is, bár szerintem egy komplementer képzés kimaradt. 16. válaszoló pedig azt is megmutatta, hogy lehet primeket találni hozzá.

A probléma az -és ez talán válasz @12 számára is, aki félreértett-, hogy bizonyos gráfokra tudunk P időben Hamilton utat keresni. Vagyis ha a tetszőleges n számra vett feladatot, amiről most láttuk be, hogy NP teljes, szűkítjük az 1..n típusú feladatokra, az eredményezhet olyan grafcsaládot, amire P-ben van a feladat. Bár nem hiszem, hogy ez lenne a helyzet, de nem tudok eleget számelméletből, hogy biztosan tudjam milyen az 1..n számok között a relatív prímség gyakorisága, struktúrája.

@15:28

Azaz ötlet valahogy sehogy nem akar stimmelni ahogy gondolkodom rajta. Mi a helyzet a prímszámokkal? úgy értem hogy ahol konkrétan a 2,3,5 ... számokat kéne berakni? Az 1 a dzsoli dzsóker, ez bármivel relatív prím. Ezzel mi a helyzet? Mi a helyzet például a 8-al? Ez 2*2*2. Vagy a prímszámok négyzetével, prímszámok n-ik hatványával? Vagy az olyan összetett számokkal ahol a prímtényezős felbontásban több különböző hatványon különböző prímek szerepelnek?

@15:33

Megcsináltam a szita ötletére csak máshogy már 3-kor csak nem volt időm ide írni már. Méghozzá egy szitát csináltam csak máshogy. Nem is gondoltam arra hogy ez egy gráfként felfogható valami, hanem egy számítógépes adatszerkezetként gondoltam rá. A gráfos matekos szemlélet szerint elmondva a következőt csináltam : Csináltam egy 1,2,... n csúcsú teljes gráfot melyből kiszitáltam azon éleket mely számok nem relatív prímek egymással. A kiszitálás úgy történt, hogy 1..n-ig minden számnak megadtam, hogy mely számok a prímosztói. Vagyis 1..n-ig minden számhoz hozzárendeltem egy halmazt (mely halmaz az adott szám prímosztóit tartalmazza, és ezt memóriába tároltam). Ezt osztások nélkül inverz szitával csináltam meg. Úgy hogy kezdetben minden számhoz üres halmaz tartozik. Majd véve a legkisebb prímszámot a 2-őt melynek az összes többszöröséhez n-ig bővíteni a halmazaikat 2-vel. Vagyis 1..n-ig minden páros számhoz hozzárendeltem a {2} halmazt. Majd vettem a következő prímet a 3-at és ennek minden többszözöréhez a hozzá tartozó halmazukat bővítettem 3-al, vagyis minden 3-ik halmazt bővítettem 3-al és így tovább ameddig kell értelem szerűen. Először prímkeresési függvényt használtam rá, de ahogy olvastam tanárúr válaszát, akkor mondom magamba miért ne, legyen már a prímkeresés is szitával. Ekkor meg a prímkeresést Eratoszthenész szitájára cseréltem le, ez még gyorsított rajta. Visszatérve a teljes gráfra a teljes gráfon meg az előzőleg kiszámolt prímosztó halmazok szerint hajtottam végre szitálást úgy hogy vettem minden számot és 1..n-ig és ezekhez rendelt halmazokat bejárva azon halmaz elemek többszöröséhez tartozó éleit értelem szerűen kitöröltem a gráfból, így maradt egy olyan gráf ahol a szomszédos élek egymással relatív prímek.

Majd az így kapott gráfra programoztam egy backtrack keresést, ahol természetesen figyelni kell hogy hol jártam már az adott bejárásba és oda ne lépjek 2x egy bejárás során.

A kódot nem, de néhány futtatás kimenetét közzéteszem :

3-ra a bejárások : [link]

4-re a bejárások : [link]

5-re a bejárások : [link]

6-ra a bejárások : [link]

7-re a bejárások : [link]

Mj.: Az hogy magát a prímkeresést szitával csináltam, az nem gyorsított annyit, mert a backtrack ami a szűk keresztmetszet, pedig ez még mindig jobb mintha végigpörgetném az összes permutációt.

"Mj.: Az hogy magát a prímkeresést szitával csináltam, az nem gyorsított annyit, mert a backtrack ami a szűk keresztmetszet, pedig ez még mindig jobb mintha végigpörgetném az összes permutációt."

Pontosítok: Komplett mindennel együtt a teljes gráf előállítása elhanyagolható a megfelelő összes gráf bejárások megtalálásának futási idejéhez képest.

Meg még egy megjegyzés : "Ez NP teljes feladat, sőt, már az is, hogy létezik-e ilyen permutáció."

Ez nem igaz a létezésre vonatkozóan. Konkrétan bizonyítást nem tudok írni, de azt mondom hogy mindig létezik. Triviális megoldás mindig a számok csökkenő vagy növekvő sorrendje. (1,2 ... n számokra vonatkozóan)