> Det er svært at afgøre, hvor svær en opgave er for mennesker. > Men man kan måske sige, at jo færre tal, der er givet på
> forhånd, jo sværere er opgaven.
Her er en ide:
Lad os nu kigge på en situation hvor en person løser sodukoopgaven
X[1]: Hun starter at tilføje et enkelt tal. Dette giver hende
sodukopgaven X[2]. Derefter tilføjer hun endnu et tal for at få
soduko-opgaven X[3]. Sådan kan hun fortsætte indtil der ikke er flere
tomme felter. Hun må selvfølgelig ikke tilføje et tal før hun er
helt sikker på at det er rigtigt.
Hver gang hun tilføjer et tal bruger hun en slags søgetræ-
algoritme. Vi kan lade tallet n[i] angive hvor dybt et søgetræ hun
bruger for at komme fra tilstand X[i] til tilstand X[i+1]. Med andre
ord angiver n[i] hvor mange træk hun er nødt til at tænke frem for
at tilføje et enkelt tal. Hele løsningsprocessen beskrevet ved et
array af søgetræsdybder: n[1],n[2],n[3],n[4]...
Vi kan give en bedre beskrivelse af løsningsprocessen hvis vi tegner
et histogram over søgetræsdybderne:.
N(n) = sum_i delta(n,n[i])
(Her opfylder Kroneckers deltafunktion delta(i,j)= 1 for i=j og
delta(i,j)= 0 for i!=j)
http://mathworld.wolfram.com/KroneckerDelta.html
Vi kan sammenligne to løsningsprocesser, A og B ved at sammenligne
deres dybdehistogrammer. Lad os sige at løsningsprocesen, A, er
beskrevet ved dybde-histogrammet NA(n) mens løsningsprocessen, B, er
beskrevet ved dybdehistogrammet NB(n). Jeg definerer A til at være
smartere end B hvis (og kun hvis) der eksisterer et naturligt tal m,
således at
NA(m) < NB(m) og
NA(n) = NB(n) for alle n>m
Desuden kalder jeg kalder løsningen A for optimal, hvis A er smartere
end alle andre løsningsprocesser (til den samme opgave). Jeg tror at
man kan give en god beskrivelse af hvor svær en sodukoopgave er ved at
finde den optimale løsningsproces og tegne det tilsvarende
dybdehistogram.
Nu har jeg tre spørgsmål til gruppen
1) Hvordan kan jeg konstruere en soduko-opgave, der har en optimal
løsning med søgedybderne n[1],n[2],n[3]...?
2) Hvordan kan jeg konstruere en soduko-opgave, der har en optimal
løsning med dybdehistogrammet N(n)?
3) Vil en "bredde først"-søgning altid resultere i en optimal
løsning? -Findes der et modeksempel?