2012-02-22, 22:50
#1
Hej,
jag har ett litet sökproblem som jag behöver hjälp med. Låt A vara en algoritm som gör en greedy-sökning på ett träd med djup n. Det finns en korrekt väg i träden. Låt en nod vara en urna som vi kan lägga bollar i, max kan det få plats b bollar i urnan. Vi har l sådana bollar som kan distribueras. Sannolikheten att mer än k bollar finns i en urna/nod är nära noll, så vi kan anta att max-bollar per nod är k men den kan naturligtvis vara lägre eftersom l << n. Vi kan anta att graden är 2^k.
Jag väljer vägen i trädet med hjälp av en ackumulerad poängsumma som ges av en värdefunktion f, enligt poäng += f. Jag väljer hela tiden den nod som har högst poäng.
Om noden ligger på den korrekta vägen så är f_korrekt = -k*A + (3*b/2-k)*B, om den inte gör det är f_fel = (b/2)*(X*B - (1-X)*A) - A, där X är en binomialfördelad stokastisk variabel i området [0,1].
Antag nu att vi utgår från rätt nod. Frågan är då, hur många felaktiga noder kommer att besökas innan vi väljer rätt väg?
Jag funderade om man kunde använda någon form av kösystem för att modellera A. Vi börjar med en kund i systemet. Det finns då en viss sannolikhet att nästa kund är den korrekta, nämligen sannolikheten P = Pr[f_korrekt > f_fel, för alla 2^k -1 andra utgående vägar]. Om vi väljer fel här, kommer vi med sannolikheten 1-P generera 2^k nya kunder (felaktiga vägar) enligt funktionen ovan. Det förväntade antalet nya kunder som skall betjänas före den korrekta beror då på antalet noder som har poäng bättre än f_korrekt. Varje sådan kund kan generera ytterligare nya kunder som är bättre än den korrekta, osv.
En annan idé som jag hade var att modellera komplexiteten av A som en markovkedja, men jag är lite osäker på hur jag ska fortsätta.
Något bra förslag?
jag har ett litet sökproblem som jag behöver hjälp med. Låt A vara en algoritm som gör en greedy-sökning på ett träd med djup n. Det finns en korrekt väg i träden. Låt en nod vara en urna som vi kan lägga bollar i, max kan det få plats b bollar i urnan. Vi har l sådana bollar som kan distribueras. Sannolikheten att mer än k bollar finns i en urna/nod är nära noll, så vi kan anta att max-bollar per nod är k men den kan naturligtvis vara lägre eftersom l << n. Vi kan anta att graden är 2^k.
Jag väljer vägen i trädet med hjälp av en ackumulerad poängsumma som ges av en värdefunktion f, enligt poäng += f. Jag väljer hela tiden den nod som har högst poäng.
Om noden ligger på den korrekta vägen så är f_korrekt = -k*A + (3*b/2-k)*B, om den inte gör det är f_fel = (b/2)*(X*B - (1-X)*A) - A, där X är en binomialfördelad stokastisk variabel i området [0,1].
Antag nu att vi utgår från rätt nod. Frågan är då, hur många felaktiga noder kommer att besökas innan vi väljer rätt väg?
Jag funderade om man kunde använda någon form av kösystem för att modellera A. Vi börjar med en kund i systemet. Det finns då en viss sannolikhet att nästa kund är den korrekta, nämligen sannolikheten P = Pr[f_korrekt > f_fel, för alla 2^k -1 andra utgående vägar]. Om vi väljer fel här, kommer vi med sannolikheten 1-P generera 2^k nya kunder (felaktiga vägar) enligt funktionen ovan. Det förväntade antalet nya kunder som skall betjänas före den korrekta beror då på antalet noder som har poäng bättre än f_korrekt. Varje sådan kund kan generera ytterligare nya kunder som är bättre än den korrekta, osv.
En annan idé som jag hade var att modellera komplexiteten av A som en markovkedja, men jag är lite osäker på hur jag ska fortsätta.
Något bra förslag?
