Jakiego algorytmu użyć, aby obliczyć najszybsze zamówienie na budowę budynków?

Question

W przypadku gry, w którą gram, chciałbym poznać najszybsze zamówienie na budowę kilku budynków. Gra, o której mowa, to OGame, jeśli ją znasz, to jest plus, ale oczywiście wyjaśnię podstawy gry:

• Gracz ma dostęp do wielu różnych zasobów.
• Gracz może budować budynki, maksymalnie jeden budynek naraz.
• Budynki mają różne poziomy, na przykład Budynek A poziom 1, Budynek A poziom 2 itp.
• Koszt zasobów na budowę budynków wzrasta na poziom.
• Budynki też mają dużo czasu na budowę, to także zwiększa się na poziomie.
• Niektóre budynki wytwarzają różne zasoby, co również zwiększa się w zależności od poziomu.
• Niektóre budynki zmieniają obliczenia, dzięki czemu budynki budowane są szybciej.

Wybierałem wyraźnie, aby nie wyświetlać równań, ponieważ nie są one proste i nie powinny być potrzebne do zasugerowania algorytmu.

wybrałem model ten z następujących czynności:

• StartUpgradeBuildingAction: Ta akcja rozpoczyna proces aktualizacji poprzez odjęcie kosztów od dostępnych zasobów.
• FinishUpgradeBuildingAkcja: Ta czynność kończy proces aktualizacji, przechodząc do przodu w czasie. To także wytwarza zasoby.
• WaitAction: Ta akcja przekazuje czas do X sekund, a tymczasem produkuje zasoby zgodnie z produkcją zasobów.

Należy zauważyć, że przestrzeń stan jest nieskończony i mogą być charakteryzowane przez fakt, że istnieje wiele ścieżek do ostatecznej konfiguracji (gdzie wszystkie wymagane budynki zostały zbudowane), każdy ewentualnie mający inny czas trwa i inną ilość zasobów, którą w końcu otrzymujesz. Teraz najbardziej interesuje mnie ścieżka (kolejność), która jest najszybsza, a jeśli istnieje wiele równych ścieżek, wówczas preferowana powinna być ścieżka, która kosztuje najmniejszą.

Próbowałem już następujące metody:

• wszerz wyszukiwania
• Depth-First Search
• Iterative Pogłębienie Depth-First Search
• Iterative Pogłębienie A *
• A * Wyszukaj

Niestety Wszystkie z tych algorytmów trwają zbyt długo lub zużywają zbyt dużo pamięci.

Jak googling nie dał mi jakieś dodatkowe przewody, pytam tu następujące pytania:

• Czy istnieje już istniejący model, który pasuje do mojego problemu? Wydaje mi się, że na przykład już wcześniej napotkaliśmy ten typ problemu.
• Czy istnieje algorytm, który daje najlepsze rozwiązanie? Jeśli tak, to jaki?
• Czy istnieje algorytm, który zapewnia rozwiązanie zbliżone do najlepszego rozwiązania? Jeśli tak, to jaki?

Każda pomoc jest doceniana.

Answer 1

Nie ma jednego algorytmu, który zapewnia najlepsze rozwiązanie problemu. Podejścia, które wypróbowałeś, są rozsądne. Jednak po wypróbowaniu wyszukiwania A * nie oznacza to dużo, ponieważ wyszukiwanie A * zależy od heurystyki, która ocenia pewną konfigurację (tj. Przypisuje wartość do kombinacji czasu, liczby i wyboru budynków, które są dostępne; zasoby itp.). Dzięki dobrej heurystyce wyszukiwanie A * może szybko doprowadzić do bardzo dobrego rozwiązania. Znalezienie tej heurystyki wymaga dobrej znajomości parametrów (koszty budynków, zalety modernizacji itp.).

Uważam jednak, że twój problem jest skonstruowany w taki sposób, że szereg decyzji dotyczących budowy może wyraźnie przewyższać inne serie decyzje po niewielkiej liczbie kroków. Powiedzmy, że budujesz budynki A, B i C w tej kolejności. Budujesz każdy, gdy tylko wymagane zasoby będą dostępne. Następnie spróbujesz kolejności C, A, B. Prawdopodobnie znajdziesz jedną alternatywę dominującą nad drugą, o ile masz te same budynki, ale w jednej alternatywie masz więcej zasobów niż w innych. Oczywiście jest to mniej prawdopodobne, jeśli masz wiele różnych zasobów. Możesz mieć więcej zasobów X, ale mniej Y, co utrudnia porównywanie sytuacji. Jeśli jest to możliwe, to dobrą rzeczą jest to, że nie potrzebujesz heurystyki, ale wyraźnie widzisz, którą ścieżkę podążyć, a którą odciąć.

W każdym razie, chciałbym zbadać, ile kroków potrzeba, aby znaleźć ścieżki, które można odrzucić w oparciu o taką uwagę. Jeśli uznasz, że są szybkie, warto jak najszybciej rozpocząć strategię od szerokości i przycinać gałęzie. Głębokie pierwsze wyszukiwanie niesie ze sobą ryzyko spędzania dużo czasu na odkrywaniu gorszych ścieżek.