Sztuczna inteligencja. Czy ilość operacji ma negatywny wpływ na wydajność ?

Cześć !
Porównuje ostatnio algorytmy sztucznej inteligencji, szukające drogi do punktu w płaszczyźnie poziomej. // http://qiao.github.io/PathFinding.js/visual/ Jedne algorytmy są szybsze inne zaś wolniejsze czasem podają krótsze drogi czasem dłuższe. Co w przypadku kiedy algorytmy wskazują taką samą drogę do celu pomijając przeszkody mają ten sam czas dotarcia do celu, ale liczba operacji się różni. Czy liczba operacji ma wpływ np. na pamięć obciążenie procesora ?

Podobno algorytm wykorzystujący mniejszą mniejszą liczbę operacji nie jest lepszy ?

Jaki jest sens? Gdzie szukać zrozumienia?

Jakbyś grał w stare RTSy to wiedziałbyś jak maszyna zdycha przy kilkuset jednostkach naraz na ekranie.
Wtedy pewnie nie zadawałbyś takich pytań.

Jakich pytań ? Jak byś zgłębił link to zobaczył być że operacja jest wykonywana jedna po drugiej a nie kilka na raz.

slim44 napisał(a):

Jakich pytań ? Jak byś zgłębił link to zobaczył być że operacja jest wykonywana jedna po drugiej a nie kilka na raz.

Tym gorzej.

A mógłbyś swoje doświadczenie, poprzeć czymś uargumentować ? Te pytanie które, zostało zadane na zajęciach z SI i moja odpowiedź była bardzo podobna do Twojej, uzyskałem odpowiedź od prowadzącego że jestem na zbyt niskim poziomie abstrakcji jeśli tak myślę. I naszym zadaniem (studentów 5) roku jest znalezienie odpowiedzi.

chodzi dokładnie o algorytmy A* i Jump Point Search przy jednej mapie uzyskują podobne wyniki czas ten sam, droga też ale A* ma więcej operacji. A wiadomo że A* jest lepsze. Więc o co chodzi ? Czy liczba operacji nie jest istotna ?**

slim44 napisał(a):

a chodzi dokładnie o algorytmy A* i Jump Point Search przy jednej mapie uzyskują podobne wyniki czas ten sam, droga też ale A* ma więcej operacji. A wiadomo że A* jest lepsze. Więc o co chodzi ? Czy liczba operacji nie jest istotna ?

Jeśli przy podobnych czasach któryś algorytm oceniany jest jako gorszy to może oznaczać że:
a) jest mniej skalowalny (notacja wielkie O)
b) nie da się zrównoleglić
c) ma przypadki szczególne przy których jest niewydajny (scenariusze pesymistyczne)

Żeby dobrze porównać algorytmy powinieneś je zbadać dla kilku rozmiarów problemu (mały, normalny, gigantyczny), przy czym warto też wyjść poza sensowne rozmiary problemu żeby wyjść poza cache danych w CPU.

To ja zaczekam na lincz mojego rozumowania.
Dojście od punktu A do B z ograniczeniami (np ściana/linia prosta/cokolwiek) wymaga, aby algorytm podał taką ściężkę, że damy radę tam dojść (lub stwierdzić że nie można tam dojść). W zależności od użytego algorytmu może to być np 500 instrukcji (załóżmy że wskazana ścieżka będzie optymalna), a może to być np 50 instrukcji (ale droga będzie dłuższa/nieoptymalna). Dlatego nie zawsze algorytm który wykona mniej instrukcji będzie lepszy. W drugą stronę jest tak samo - algorytm, który wykona tysiące operacji nie oznacza, że będzie lepszy.

Celowałbym bardziej we współczynnik poprawności obranej ścieżki do ilości instrukcji.

Kolejnym wspomnianym nawet i przez Ciebie czynnikiem jest czas, kod zawierający 100 instrukcji może być wolniejszy od tego który ma 500 instrukcji.

Jestem w dużym błędzie @vpiotr ?

@axelbest: oczywiście masz rację.
Oprócz czasu wykonania i skalowalności ważna jest poprawność rozwiązania, czyli:
a) długość ścieżki
b) poprawność ścieżki
c) success rate (w grach, nawet AAA algorytmy często się gubią)

Abstrakcje abstrakcjami, złożoność złożonością, ale warto zrobić również test praktyczny. Czyli implementujesz algorytm na kilka sposobów, tworzysz jakąś testową mapę i mierzysz wydajność w każdym przypadku, robisz sobie taki benchmark. Teorie często przegrywają z praktyką, a na realną szybkość wykonywania programów ma wpływ wiele czynników.

Ufff... jak dobrze, że grałem w strategie :) Ostatnio słyszałem też o przypadku gracza, który wybudował w simsach taki labirynt - że postać aby dostać się do pracy musiała iść 8godzin, potem 8h pracowała i następnie znów 8h wracała przez labirynt (wykonanie iście diabelskie, ale jako tako pokazuje, działanie algorytmu wybierającego ścieżki). Nie pamiętam czy postać umierała z wycieńczenia :)

Kiedyś czytałem regularnie ten site, polecam:
https://www.gamasutra.com/view/feature/131505/toward_more_realistic_pathfinding.php