Bredden-först sökning av ekvationer

Beakta följande formella grammatik
F(_) --> F(_,_)
F(_,_) --> F(F(_,_),_) | F(_,F(_,_)) | x | konstant1 | konstant2 | sqrt(F(_,_)) | (_ + _) | (_ - _) | (_ / _) | (_ * _)

Vi gör en bredden-först sökning och testar ekvationer mot en vektor V av tupler (x,y). Ex: V = {(1,2), (4,9), ... }. Det maximala dJupet av sökningen sätter vi till N och den sematiska tolkningen av "djup" sätter vi till Q.

Låt R = { (F(x) - y)^2, ... } för alla tupler i V för varje ekvation i vår sökning. Sätt E = SUM(R) för varje test. Vi får en lista av ekvationer sorterade efter deras felkvadratsumma.

Om V är mätdata av exempelvis en fallande kropp mot jorden från inte så hög höjd, och en av konstanterna får vara 9.82 så hittar man trivialt några av dessa ekvationer https://en.wikipedia.org/wiki/Equations_for_a_falling_body#The_equations (jag har testat). Inget tjafs om det nu.

Vad heter den specifika metoden? Jag hittar bara ytterst lite litteratur om det.

Notera att vi INTE diskuterar andra metoder här än brute-force bredden-först sökning av ekvationer som stämmer överrens med den formella grammatiken ovan.

Varför tror du den har ett namn? Den verkar inte vara särskilt effektiv eller intressant.

Det är jag inte helt säker på, men jag behöver så mycket research som möjligt. Vill implementera metoden i kvandatorer och försöker hitta mer utöver det jag själv upptäckt. Andra metoder (approximationer, vissa typer av heurestik mm) blir ointressanta eftersom att jag inte vill missa några hörn i sökrymden.

Någon kanonisk form för algebraiska uttryck verkar inte ha upptäckts t.ex, men många har försökt.


Nej exakt, tidskomplexiteten gör att man inte kommer så brett i sökningen. På klassiska datorer fungerar det bara upp till en viss bredd/djup. Med heurestik kan man komma lite längre, men de flesta lösningar är lite mer probabilistiska med sina sökningar dvs de missar eventuella intressanta ekvationer.


Jodå, men inte hos alla. Kan man söka djupare så blir metoden högst intressant. Vänta tills (om) kvantdatorerna kommer så ska du få se på åka.

Tror du missförstod hur jag menade.

Att hitta ekvationer som uppfylls exakt av data är inte ett svårt problem. Problemet blir bara intressant om man har extra krav. Djupet i din sökning verkar inte vara en särskilt intressant egenskap så vad din algoritm spottar ut i mer generella fall förstår jag inte intresset av.

Nu förstår jag dig inte.

Jag testade att stoppa in mätvärden av en fallande boll och fick ut d=0.5*g*t*t exempelvis. Det var den formeln i min sökning som gav minst felsumma. Med samma metod återupptäckte vi också archimedes princip. Varför skulle detta inte vara intressant?

edit: nu tror jag att du förstår vad jag menar. Jo, vi vill inte hoppa över ekvationer när vi söker. Andra metoder (exempelvis genetisk programmering) hittar suboptimala ekvationer eller approximerar med arbiträra vikter.

Ja, det här metoden skalar inte väl på klassiska datorer och gör därmed inget utöver andra metoder. Är det det du menar?

Som sagt, att hitta formler som stämmer med data är inte svårt. Att en algoritm som går igenom alla uttryck hittar små kända uttryck är inte konstigt eller särskilt intressant.

Målet är givetvis att hitta större formler som är svåra att hitta. Högst intressant.

Nej de flesta formler som stämmer med given data är relativt ointressanta. Problemet blir bara intressant om vi har några extra krav på formlerna. Exempelvis om är algebraiska, har låg grad, få termer eller något sådant.

Det är ju just det vi får fram här då vi söker "utåt" med "bredden först". Det är ingen slump att just d=0.5*g*t*t dök upp som nummer 1 bland alla formler i mitt exempel.

Av det du skrivit hittills finns det ingenting som får mig att tro att det som din algoritm (i och för sig är det lite svårt att exakt förstå din beskrivning av algoritmen) kommer spotta ut kommer vara särskilt intressant i mer generella fall och för övrigt varför algoritmen på något vis skulle vara bättre än att exempelvis bara sätta upp allmänna algebraiska uttryck av någon grad och optimera parametrar.

Det beror på att du bara sysslat med gymansiefysik. När du jobbar med mer avancerade problem så är större samband intressanta där man inte vill approximera.

Nej det är inte det som det beror på, läs igen. Jag tror att din algoritm kan hitta saker, jag tror inte att den hittar särskilt intressanta saker och jag förstår inte varför den skulle vara bättre än de vanliga metoderna för att hitta ekvationer. Det kanske beror på att din beskrivning av algoritmen är ytterst bristfällig, men jag betvivlar det.