Uproszczenie rekurencji

Witam

Mam drobny problem z uproszczeniem rekurencji w postaci

 
bool LimitedDFS(Hex* hex, float cost, float limit)
{
	
    if(cost > limit || hex == NULL)
		return false;
	
	if(cost < limit)
	{
		hex->enableFlags(eHF_MOVE_AVAILABLE);

		for(int i=0; i<6; i++)
		{
			LimitedDFS(hex->getNeighbour(i), cost + hex->calcTraverseCost(), limit);			
		}
	}
}

Metoda calcTraverseCost() wyznacza koszt ruchu (a raczej karę za przejście tego hexa) uwzględniając tylko 6 sąsiadów hexa ( koszt przejścia może być 1.0 - standardowo, 2.0 lub 3.0 jeśli np na heksie jest jakaś przeszkoda - 2.0 albo 3.0 w zależności od jej rodzaju )

Generalnie problem jest taki, że w przypadku gdy limit wynosi 10 ( czyli badamy ruch w odległości 10 heksów od źródła to przeszukiwanie tego to jest grubo kilkadziesiąt milionów przebiegów.
Agorytm jest potrzebny do znalezienia wszystkich możliwych hexów w zasięgu ruchu ( limit ). Mógłbym zastosować A* i badać wszystkie możliwe heksy ale to jest także mało racjonalne rozwiązanie ( dla ruchu 10 heksów będzie do przeszukania 400 heksów co także jest niedopuszczalne obliczeniowo). Jakieś wskazówki ktoś byłby uprzejmy podać ?

Nie jestem pewny do końca o co chodzi. Ale tak sobie myślę, tak czysto abstrakcyjnie, być może nie trafiłem w ogóle w Twój problem. Rozumiem, że chodzi o to, że chcesz wyliczyć tą karę za przejścia tak? A to nie można zrobić tak, że najpierw przechodzisz po hexach, zapamiętujesz ścieżkę i dopiero teraz sprawdzasz ścieżkę pod kątem kosztu przejścia tylko po tych hexach, po których się ruszyłeś?

Chyba, że chodzi o to, żeby nie dopuścić do chodzenia po tych hexach, w których kara jest duża lub inaczej: wybrać optymalną ścieżkę. Do głowy przychodzi mi zastosowanie teorii grafów (znaleźć najkrótszą drogę z wierzchołka A do B). Graf z wagami, na którym wykonujemy algorytm Dijkstry. Ale to może być bez sensu, bo ja akurat świeżo po grafach jestem, więc taka sobie mi przyszła na myśl dygresja :)

Nie do końca, kara za przejście przez konkretny hex ( czy wierzchołek grafu, bo nie ma tutaj różnicy) ogranicza tylko zasięg ruchu, ona ( ta kara ) jest znana wcześniej. Generalnie jest to problem ze znalezieniem wszystkich możliwych wierzchołków w grafie do których jest dojście z wierzchołka źródłowego przy czym zasięg ruchu jest obwarowany warunkiem, że nie może być większy niż konkretny limit ( czyli suma kar za przejścia przez wszystkie wierzchołki grafu które składają się na obecną ścieżkę nie może być większa niż ustalony wcześniej limit). Chodzi mi o to, żeby znaleźć jakiś dokładny algorytm ale w miarę tani obliczeniowo który wyznaczy te wierzchołki. Rekurencja którą przedstawiłem jest niestety zbyt kosztowna do tego zadania chociaż wynik jej działania jest w 100% prawidłowy.

Temat nieaktualny już, można skasować ;)