Witam

Jakbyście zaprojektowali algorytm do rozwiązywania gry sokoban (japoński
magazynier). Kiedyś ściągną jakiś solver, ale na dużych zadaniach nie
znajdował ani dopuszczalnego rozwiązania ani optymalnego.

Pozdrawiam

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

On 15 Lip, 23:17, "Mariusz Marszałkowski"
<b...@g...pl> wrote:
> Witam
>
> Jakbyście zaprojektowali algorytm do rozwiązywania gry sokoban (japoński
> magazynier). Kiedyś ściągną jakiś solver, ale na dużych zadaniach nie
> znajdował ani dopuszczalnego rozwiązania ani optymalnego.

A pare minut wczesniej:



From: "Mariusz Marszałkowski" <b...@g...pl>
Date: 15 Lip, 23:06
Subject: Szukam kogo&#65533; do napisania gierki we flashu
To: pl.comp.programming

>> Nie jest to praca na zaliczenie potrzebuję kogoś kto umie szybko i sprawnie
>> napisać tego typu proste gierki lub inne programy we flash. W perspektywie
>> dłuższej współpracy.

>Prześlij projekt programu i wzór umowy na gg 5582899


Przypadek;>

Wracajac do pytanie, sokoban jest NP-trudny, wiec dobrze bysmy
sie zastanowili, co tak naprawde chcemy.

Porada darmowa, rachunku na gg nie wysle:)

pozdrawiam
bartekltg

do góry

bartekltg <b...@g...com> napisał(a):

> Wracajac do pytanie, sokoban jest NP-trudny, wiec dobrze bysmy
> sie zastanowili, co tak naprawde chcemy.

Co chcemy? Spędzić kilka miłych chwil przy pogawędce o sokobanie.

Moje przemyślenia:

1) Najpierw siłowe przeszukiwanie grafu w szerz - złożoność to brench faktor
do potęgi depth.
2) Później drobne usprawnienie - odrzucamy pola-pułapki z których nie
da się dotrzeć do celu.
3) Kolejny krok, to spamiętywanie węzłów przeszukanych w przeszłości -
dzięki temu algorytm nie będzie chodził w kółko. Złożoność obliczeniowa
spadnie do (n nad k), ale złożoność pamięciowa wzrośnie do n nad k.
4) Gdy pamięci zabraknie, dobra heurystyka do wyboru które węzły
trzymać zapamiętane a które nadpisać nowymi.
5) Dobra heurystyka które węzły odrzucić bez przeszukiwania
6) Gdy z powodu rozmiaru nie ma szans na rozwiązanie optymalne albo
bliskie optymalnemu, to dwa algorytmy:
a) pierwszy generuje dowolne rozwiązanie
b) drugi im pracuje dłużej, tym ma większe szanse na poprawienie
rozwiązania

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry