PPR.2 semestralka (krizovka)

asked 2014-10-11 22:43:21 +0100

palicand gravatar image

updated 2014-10-12 11:44:16 +0100

Miro Hrončok gravatar image

Zdravim... najde sa tu niekto, kto ma zadanie krizovka a bol ochotny sa podelit o tipy? Algoritmus mam snad spravne, ale je neskutocne pomaly, nedobehne ani pre maticu 6x6 (pokial nie je vyslovene skonstruovana tak, aby sa rychlo zaplnila) Nejak tusim, ze mam zistovat, ked uz nema zmysel pokracovat v skusani slov v nejakej vetvi DFS, ale neviem, ako to zistit :-D

Vdaka! ;-)

edit retag flag offensive close delete

Comments

Zadání pro PPR.2 bývají schválně volena taková, aby sekvenční výpočet trval dlouho a to nás motivovalo k použití paralelnímu programování. A to i pro maličké úlohy - my jsme kdysi dělali přeskakování jezdcem z jednoho konce šachovnice na druhý a co si pamatuju, byly problémy i s šachovnicí 4x4.

Ořezávání řešení je každopádně nezbytné. Po velmi zběžném zhlédnutí zadání bych třeba pouvažoval o oříznutí takto: M = dosud dosažené maximum bodů. X = bodové ohodnocení aktuálního stavu. N = počet volných políček v aktuálním stavu. Z = nejvyšší možné bodové ohodnocení jednoho znaku. Pak výpočet přeruším, pokud (X+N*Z) < M. Samozřejmě se to dá všelijak zoptimalizovat.

Josef Kokeš ( 2014-10-12 07:34:16 +0100 )edit

Dik za inspiraciu :-)

palicand ( 2014-10-12 16:03:23 +0100 )edit