| Autor | Zpráva | ||
|---|---|---|---|
| KryVosa Profil * |
#1 · Zasláno: 29. 7. 2015, 19:53:18
Mám jednoduchou mapu:
[0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ], [0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ], [0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ], [0 ,0 ,0 ,0 ,-1,0 ,0 ,0 ,0 ], [0 ,0 ,0 ,2 ,a ,0 ,0 ,1 ,0 ], [0 ,0 ,0 ,0 ,0 ,1 ,1 ,0 ,0 ], [0 ,0 ,0 ,0 ,2 ,0 ,0 ,0 ,0 ], [0 ,0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ], [0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ] |
||
| Keeehi Profil |
#2 · Zasláno: 29. 7. 2015, 20:16:45
Nezapadá mě nic jiného, než bruteforce.
F = nová fronta
Přidej a do fronty
While (fronta F není prázdná)
P = vyjmi jedno pole z fronty
// u všech polí si pamatujeme kolik bylo nejvíc energie, když jsme na něm byli, na začátku mají všechny nulu
Projdi všechny sousedy S políčka P
Když mám dost energie, abych se na policko přesunul
Označím si políčko jako navštívené
Když by mi po přesunu na políčko zbylo více energie než co si pro něj pamatují
Zapamatuji si toto nové množství
Přidám políčko do fronty |
||
| KryVosa Profil * |
#3 · Zasláno: 29. 7. 2015, 20:21:05
Děkuji moc, tedy pokud jsem to pochopil správně :)
Jen drobná otázka: "BruteForce"? |
||
| Keeehi Profil |
bruteforce je zkoušení všech možných řešení. To tedy v tomto případě není ono ale to je detail. Spíše jsem měl asi napsat naivní řešení nebo simulace možných tahů.
Myslím že to co jsem popsal je něco na způsob BFS. Je tam jen lehká optimalizace. Určitě by se dalo i něco na způsob DFS. Jsou to ale spíš jen nástřely, žádnou hlubší analýzu jsem neprováděl. Ta rychlost je na začátku vždy 4, nebo je to obecné N a může být vyšší i nižší? |
||
| juriad Profil |
#5 · Zasláno: 29. 7. 2015, 20:35:14
Keeehi:
Ono optimální řešení spočívá v použití Dijkstrova algoritmu. KryVosa: Je ta mapa konečná? Jak se má postava chovat u kraje? |
||
| Keeehi Profil |
juriad:
Při použití prioritní fronty vlastně o Dijkstru půjde. Kraje si asi můžeš představit jako by celá ta matice byla po obvodu rozšířená o samé -1 A kdyby ta mapa byla nekonečná, vždy ji můžeš omezit na čtverec o hraně rychlost*2+1 se startovním bodem uprostřed. |
||
| KryVosa Profil * |
#7 · Zasláno: 29. 7. 2015, 20:51:14
Keeehi: Ano, rychlost se pak ve hře bude dát ovlivňovat npř. kouzly :)
Juriad: Mapa je konečná a předem definovaná, okraj se překročit nedá, překážky mohou být větší než jen "dvojkové"; Našel jsem si Dijkstrův algoritmus (Píšu to správně, že jo?) na netu, ale moc jsem to nepochopil.. Zkuste mi to prosím nějak načrtnout. |
||
| Keeehi Profil |
Dijkstra je algoritmus pro hledání nejkratších cest v grafu, to znamená, jak se co nejlevněji dostat z bodů a někam. Většinou se Dijkstra používá pro nalezení nejkratší cesty mezi dvěma body, ovšem při svém běhu zároveň spočítá nejkratší cesty do všech uzlů které navštíví.
Ona se ta tvoje úloha dá přeformulovat, aby to více odpovídalo hledání nejkratších cest. Každé políčko je uzel. Dva uzly mají mezi sebou hranu, pokud se tam dá jedním tahem přesunout (jsou to sousední políčka). No a na takovémto grafu hledáš cesty délky menší než N (4). S tímto omezením už to není typický Dijkstra ale upravená verze. Ještě jsem zapomněl napsat, že všechny hrany mají váhu 1 a do délky cesty se samozřejmě započítává i hodnota v cílovém uzlu. Na pochopení Dijkstra jsou výborné animace nebo vysvětlující videa na YouTube. |
||
| juriad Profil |
KryVosa:
Pak by bylo dobré okraj mapy vyplnit -1, aby se nemusely testovat podmínky podle polohy. A dobré by bylo změnit -1 na nějaké vysoké číslo, třeba 10000000, to pak znamená, že energie (budu ji používat místo rychlosti) potřebná na vstup do takového políčka je vyšší než energie, kterou hráč kdy může mít. Konstantu je nutné zvolit dostatečně velkou. Všechna čísla na mapě by měla být alespoň 1 (abys tam neměl ten nesmysl s extra jedničkou) a hodnota měla opravdu význam ceny za vstup. V mapě nebude vyznačená počáteční pozice, to bude další parametr funkce. Dijkstrův algoritmus v podstatě ukládá políčka do fronty, kterou průběžně zpracovává. Na začátky máš mapu prázdnou - všude jsou třeba -1. Protože 0 má význam, že se na dané pole hráč může dostat a zbyde mi 0 energie, musí být předvyplněná zápornými čísly. Proměnné: map // mapa světa s cenami za přechod na určitá políčka e // prázdná mapa - bude obsahovat dosažitelná políčka q // prázdná fronta start_p // počáteční pozice start_energy // počáteční energie Nová podoba map (9 značí vysoké číslo, použil jsem zde pro přehlednost; ty použíješ něco v řádů miliard): [[9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9], [9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9], [9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9], [9, 1, 1, 2, 1, 1, 1, 1, 1, 1, 9], [9, 1, 1, 1, 1, 9, 1, 1, 1, 1, 9], [9, 1, 1, 1, 3, 1, 1, 1, 2, 1, 9], [9, 1, 1, 1, 1, 1, 2, 2, 1, 1, 9], [9, 1, 1, 1, 1, 3, 1, 1, 1, 1, 9], [9, 1, 1, 1, 1, 1, 1, 2, 1, 1, 9], [9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9], [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]] 1) Do fronty si uložíš počáteční pozici p a v mapě uložíš na pozici p počáteční energii. q.add(start_p, start_energy); e.update(start_p, start_energy); while (!q.isEmpty()) var p = q.remove_largest(); var ss = map.neighbours(p);
for (var i = 0; i < ss.length; i++)
s = ss[i]; var energy = e.get(p) - map.get(s);
if (energy > e.get(s))e.update(s, energy) q.add(s, energy) Výstupem je mapa e. Zajímají tě pozice, které jsou >= 0. Číslo značí zbytkovou energii. Algoritmus funguje s libovolnou frontou, ale nejlépe s takovou, která vrací pozice s maximální energií. Tato fronta se implementuje různě, ale v tvém případě o výkon moc nejde, takže obyčejná binární halda v poli postačí. |
||
|
Časová prodleva: 4 dny
|
|||
| KryVosa Profil * |
#10 · Zasláno: 2. 8. 2015, 10:06:14
Děkuju moc, funguje bez problému. Ukazovat vám to naneštěstí nemůžu, protože to mám optimalizované zatím jen pro webkity. Zatím jsem nenašel chybu.
Jen pro informaci: Mapa doopravdy sestává z čísel značící "typ" políčka, neboli jeho obrázek, takže naštěstí nemusím předělávat desítky map, ale jen jedno pole :) |
||
|
Časová prodleva: 9 let
|
|||
0