On 11 Lut, 18:02, bartekltg <b...@g...com> wrote:
> On 11 Lut, 16:22, Mariusz Marszałkowski <m...@g...com> wrote:
>
> > Dlaczego uwazasz ze to bzdura? Taki algorytm jest
> > tym samym co maszyna turinga. Stan to pozycja glowicy,
> > dane to tasma, pozostale tablice to funkjca przejsc.
>
> Nie widze wlasciwie zadnej mozliwosci praktycznego
> zastosowania takiego algorytmu.
No bez przesady. Zobacz np. drzewa i grafy decyzyjne
wraz z algorytmami do ich automatycznego budowania.
Każdy wezel grafu wyglada w przyblizeniu tak:
Node {
index;
max;
min;
index_true;
index_false;
value_true;
value_false;
stan_true;
stan_false;
response;
};

Mozna zbudowac taki graf w postaci tablicy:
Node graf[MAX_NODE];

I nastepnie zrealizowac kazdy problem decyzyjny w tak
prostej procedurze:

Response( data[SIZE_DATA+EXTENSION] , graf[MAX_NODE] ) {
stan = 0;
for( i = 0 ; i<MAX_LOOP ; i++ ) {
if( data[ graf[stan].index ] >= graf[stan].min AND
data[ graf[stan].index ] <= graf[stan].max ) {
data[ graf[stan].index_true ] = graf[stan].value_true;
stan = graf[stan].stan_true;
} else {
data[ graf[stan].index_false ] = graf[stan].value_false;
stan = graf[stan].stan_false;
}
return graf[stan].response;
}

> Jesli chesz uzywac tego jako narzedzia teoretycznego,
> jak maszyna turinga, to inna sprawa, ale tez bys
> musial pokazac jakies ciekawe wlasciwosci
> (bo jest oczko bardziej skomplikowana niz MT)
To żadna nowość, można tego używać np. jako
grafu decyzyjnego. Nie wiem dlaczego uwazasz ze to
jest skomplikowane, po prostu stany, funkcja przejsc
pomiedzy stanami, warunek stopu i koncowa odpowiedz.

Uwazam ze to jest maksymalnie uproszczone, poniewaz algorytm
budujacy taki graf widzi po prostu tablice liczb i moze
nimi dowolnie manipulowac. Kod wykonania tego grafu
tez jest zabojczo prosty, niespelna 10 linii, a mozna chodzic
po dowolnym grafie.

> > Nie bylo mowy ze w tablice nie wolno wbic pomocniczych
> > rozwiazan, albo dowolnych innych pomocniczych danych.
>
> To w koncu moge tym algorytmem cokolwiek policzyc, czy
> musze znac wynik i wstawic go do tabelki:)
Wystarczy do rubryki "response" wsadzic dwie liczby: zero i jeden,
aby policzyc tym algorytmem dowolne zadanie. Czesciowe
wyniki mozna wstawiac w celu przyspieszenia.

Np. mozesz tym algorytmem policzyc problem komiwojazera.
Na poczatek danych wrzucasz opis grafu ktory ma komiwojazer
przejsc. Po opisie grafu mozna wpisac dwa wierzcholki grafu.
Algorytm zwroci jedynke jesli owe dwa wierzcholki sa z soba
bezposrednio polaczone na najkrotszej drodze laczacej i zero
gdy nie sa. W ten sposob trzeba algorytm wywolac dla kazdej
pary wierzcholkow, aby ustalic najkrotsza droge laczaca wszystkie.

Podobnie z innymi problemami optymalizacyjnymi. Mozna za
danymi umiescic probne rozwiazanie, algorytm zwroci jedynke jesli
rozwiazanie probne jest za male i zero jesli jest za duze. Trzeba
taki algorytm wywolywac iteracyjne (wielomianowa ilosc razy) aby
przyblizyc sie do dokladnego rozwiazania dowolnego problemu.

> Bo na razei to wyglada jak jakies wyszukiwanie
> w przestrzeni rozwiazan. Mamy stan, mamy jakies funkcje
> od stanu, jesli nam nie pasuja (u Ciebie sa za male lub za duze)
> odpowiednio modyfikujemy stan. Na koncu wypisujemy
> odpowiedz (stan lub jakas funkcje stanu).
Modyfikujemy tez dane, nie tylko stan, mamy pamiec,

> Tylko po co w to angazowac tabelki:)
Po to tabelki zeby bylo czytelniej. Dlaczego operowac na
ciagu nienazwanych bitow? Tutaj mamy ladnie wydzielone
tabele zakresow, nowych wartosci, nowych stanow, itd.

> > No wlasnie dlatego to mnie tak bardzo ciekawi, ze znane sa tylko takie
> > kosztowne sposoby. Interesuje mnie jaki jest najlepszy algorytm
> > budowania takich tablic (czyli tak naprawde algorytm budowania
> > innego algorytmu), o ograniczonych rozmiarach ktore dla dla
> > wszystkich danych uczacych wypluja wlasciwe rozwiazanie.
>
> Jesli dobrze wylapuje idee, chcesz znalesc tak tabelkowy algorytm
> dla danego problemu i pozniej te probmely w ten sposob rozwiazywac.
> W ogolnosci bedziesz mial z tym problem.
No jest z tym ogromny problem. Mnie nie tylko interesuje taki
tabelkowy
algorytm, ale raczej algorytm do budowania takich tabelkowych
algorytmow
na podstawie danych doswiadczalnych. Do tego chcialbym zeby zbudowane
algorytmy byly optymalne w sensie rozmiaru, szybkosci, dokladnosci.

> Pomysl, jak 'tabelkowo' znalesc najkrotsza droge w grafie (+z wagami).
> Czasem sie da. Znajdz tym algorytmem chocby wysokosc drzewa
> (to sie da dosc bezposrtednio, tylko po co).
No jak trzeba znalezc najkrotsza droge w grafie, to lepiej kola nie
wymyslac. Ale wielu innych algorytmow nie znamy.

> > Sa ciekawsze przypadki. Np. mamy gre kolko i krzyzyk. Algorytm
> > dostaje pary uczace w postaci opisu sytuacji w grze i najlepszego
> > ruchu. Czyli
> > tablica z danymi to bedzie:
> > int plansza[9+rozszerzenie]
> > tablica z odpowiedziami to bedzie numer pola z optymalnym ruchem
> > int response[9] = {1,2,3...9}
> > I algorytm genetyczny musialby dobrac parametry w pozostalych
> > tablicach
> > tak, aby w najmniejszej ilosci krokow zawsze podac optymalny ruch.
>
> Stabelaryzowales gre. Super, ale to juz bylo. A tabelke lepiej
> wypelnic zwyklym przeszukiwaniem drzewa gry.
A jak gra jest tak duza jak np. GO na planszy 19x19? Wtedy
potrzeba heurystyk ktore w miare mozliwosci szybko dzialaja i
dobrze uogolniaja.

> Algorytmy genetyczne, sieci neuronowe i inne wynalazki
> nie sa uniwersalna metoda rozwiazywanie wszytkiego.
> Raczej ostatnia deska ratunku dla pewnej klasy zadan,
> zeby znalesc rozwiazanie nieco lepsze niz losowe.
> Ale jakis czas kazdy sie nimi zachwyca:-)
Moze to kwestia mocy obliczeniowej? Teoretycznie na
super-komputerze mozna stablicowac rozwiazania jakiegos
ogromnego problemu NP-trudnego, nastepnie zasymulowac
wszystkie algorytmy na tych danych i wybrac tylko te ktore
zakonczyly sie przed zadanym czasem i daly poprawne
odpowiedzi na wszystkich danych. Moze w przyszlosci
wlasnie takie symulacje pomoga znalezc kontrprzykad
na to ze NP != P. Wlasciwie to juz dzis sie tak robi, ale
dzis dysponumemy moca obliczeniowa do sprawdzenia
zaledwie jakis wybranych parametrow w programie.

> pozdrawiam
rowniez pozdrawiam