On Tue, 31 Jan 2012 04:09:51 +0100, bartekltg <b...@g...com>
wrote:

>W dniu 2012-01-30 10:43, f...@g...pl pisze:
>
>>
>> szczerze mowiac to malo zajmuje sie matematyka i np
>> nie bardzo podzielam co poniektorych tutaj zainteresowania
>> tymi tematami obecnie - nie chce za bardzo skakac po
>> tematach z mat phys, ew interesuje mnie kwestia symulacji
>
>Ale informatyka poważniejsza niż tradycyjnie wspominana
>"baza gumowców" to matematyka.
>
>> algorytmy to tak naprawde matematyka, bo akurat te ktore
>> znam - sortowania czy A* to mz wogole nie matematyka
>

fir siedzi u mnie w KF, ale ubawil mnie jego post na temat tego ze A*
to nei matematyka. Polecam mu wiec ksiazke Judea Perl, Heuristics:
Intelligent Search Strategies for Computer Problem Solving, stron 360,
poswiecona w calosci matematyce A*

a gdyby mu sie nie chcialo siegac do ksiazki, to moze siegnac do tego
artykulu

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.
1.1.89.3090

Generalized best-first search strategies and the optimality of A*

Abstract
This paper reports several properties of heuristic best-first search
strategies whose scoring functions f depend on all the information
available from each candidate path, not merely on the current cost g
and the estimated completion cost h. It is shown that several known
properties of A * retain their form (with the minmax offplaying the
role of the optimal cost), which helps establish general tests of
admissibility and general conditions for node expansion for these
strategies. On the basis of this framework the computational
optimality of A*, in the sense of never expanding a node that can be
skipped by some other algorithm having access to the same heuristic
information that A* uses, is examined. A hierarchy of four optimality
types is defined and three classes of algorithms and four domains of
problem instances are considered. Computational performances relative
to these algorithms and domains are appraised. For each class-domain
combination, we then identify the strongest type of optimality that
exists and the algorithm for achieving it. The main results of this
paper relate to the class of algorithms that, like A*, return optimal
solutions (i.e., admissible) when all cost estimates are optimistic
(i.e., h 5 h*). On this class, A * is shown to be not optimal and it
is also shown that no optimal algorithm exists, but if the performance
tests are confirmed to cases in which the estimates are also
consistent, then A * is indeed optimal. Additionally, A * is also
shown to be optimal over a subset of the latter class containing all
best-first algorithms that are guided by path-dependent evaluation
functions.

Z grubsza dotyczy zbieznosci algorytmu przy roznego rodzaju
oslabionych zalozeniach wzgledem heurystyk

Przyjemnego czytania!

A.L.