navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:uloha6-2014 [2014/12/12 17:36] roziana vytvořeno |
courses:a4m33pal:uloha6-2014 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 6: | Řádek 6: | ||
| * Spustit třeba BFS v tom grafu z každého uzlu. | * Spustit třeba BFS v tom grafu z každého uzlu. | ||
| - | - Vztah mezi dvěma slovy existuje, pokud prováděním u jednoho slova nejvíc L operací (přidání, odebrání jednoho znaku a substituce jednoho znaku na druhý) dostanu druhé slovo. Tohle je přesně Levenshteinova vzdálenost (LD). K vytvoření grafu stačí tedy spočítat LD mezi každými 2 slovy (uzly). Je-li LD mezi slovy W1 a W2 <= L, pak existuje hrana mezi nimi. | + | - Vztah mezi dvěma slovy existuje, pokud prováděním u jednoho slova nejvíc L operací (přidání, odebrání jednoho znaku a substituce jednoho znaku na druhý) dostanu druhé slovo. Tohle je přesně Levenshteinova vzdálenost (LD). K vytvoření grafu stačí tedy spočítat LD mezi každými 2 slovy (uzly). Je-li LD mezi slovy W1 a W2 < = L, pak existuje hrana mezi nimi. |
| - Po vytvoření grafu pak stačí spustit BFS z každého uzlu. V každém kroku BFS budeme pamatovat vzdálenost. Zde vzdálenost je v podstatě počet větví stromu, který mi vytvoří BFS. Tedy na začátku to bude 0 u rootu a pak 1 v druhé větvi, pak 2 v třetí atd. Stačí potom pamatovat nejdelší dosud spočítanou vzdálenost - a to je řešení, které zobrazit po spuštěním BFS z každého uzlu. | - Po vytvoření grafu pak stačí spustit BFS z každého uzlu. V každém kroku BFS budeme pamatovat vzdálenost. Zde vzdálenost je v podstatě počet větví stromu, který mi vytvoří BFS. Tedy na začátku to bude 0 u rootu a pak 1 v druhé větvi, pak 2 v třetí atd. Stačí potom pamatovat nejdelší dosud spočítanou vzdálenost - a to je řešení, které zobrazit po spuštěním BFS z každého uzlu. | ||
