Úvod do simulační optimalizace
Seznam

| Úvod a cíle |

Vygenerované prvky optimalizačním algoritmem představují prvky množiny v prohledávaném prostoru, ve kterém se snažíme nalézt nejlepší prvek. Tyto prvky jsou ohodnoceny např. pomocí účelové funkce. Na základě ohodnocení se pak vybírají prvky (prvek), které mohou být potenciálním řešením. Uspořádané prvky (např. na základě účelové funkce nebo fitness) představují seznam a proto jsou zde nastíněny některé matematické popisy metod práce se seznamy, které jsou převzaty z literatury - viz [2]. Některé z těchto metod jsou modifikovány pro potřeby jednotlivých optimalizačních algoritmů v rámci tohoto kurzu.

Seznamy (jedná se o uspořádanou množinu prvků např. na základě hodnot účelové funkce) jsou abstraktní datové typy, které mohou obsahovat uspořádanou konečnou posloupnost prvků stejného datového typu. Seznam může být považován za speciální abstraktní datový typ datového záznamu (v anglické literatuře je datový záznam označován obecněji jako Tuple - seřazená konečná posloupnost prvků, kde každý z nich je speciálního typu, kde na rozdíl od množin Tuple, může obsahovat stejný prvek dvakrát). Seznamy mohou být objekty jako např. tabulky atd., proto se s nimi pracuje na základě metod (procedury, funkce) uplatňované na daný objekt.

Přístup k jednotlivým prvkům seznamu je pomocí indexu v hranatých závorkách , kde první index má hodnotu 0 a poslední index má hodnotu n-1, kde n značí počet prvků v seznamu.

Poznámka: Text v odstavci uvedený za znakem popisuje metody (funkce, procedury).

Následující metody umožňují tvorbu seznamu, přidání prvku do seznamu, odstranění prvku ze seznamů, třídění seznamů, vyhledávání uvnitř seznamů atd.:

Length ( ) funkce která navrací délku seznamu L tj. počet prvků v seznamu, ( ).

CreateList ( ) funkce pro vytvoření nového seznamu L o délce n, naplněný prvkem x. Jestliže má být vytvořen seznam o délce 0, parametr x může být vynechán ( ).

InsertListItem ( ) funkce vytvoření nového seznamu M pomocí vložení jednoho prvku x do seznamu L s indexem i ( ). Tím se posunou všechny prvky seznamu umístěné za tímto indexem o jednu pozici doprava.

AddListItem ( ) funkce pro vložení jednoho prvku na konec seznamu.

AppendList ( ) funkce pro vytvoření nového seznamu M, který vznikne přidáním všech prvků ze seznamu do seznamu . Rekurzivně lze definovat:

DeleteListItem ( ) funkce pro vytvoření nového seznamu M pomocí odstranění prvku x na pozici i ( ) ze seznamu L ( ).

DeleteListRange ( ) funkce pro vytvoření nového seznamu M pomocí odstranění c prvků začínající indexem i ( ) ze seznamu L

( ).

CountItemOccurrences ( ) funkce, která vrací počet výskytů prvku x v seznamu L.

SubList ( ) funkce vrací nový seznam M vyjmutých c prvků ze seznamu L začínající indexem i.

Sort a - často je užitečné používat setříděný seznam, proto je zde definována funkce, která třídí seznam L podle pořadí buď vzestupně - ascending - nebo sestupně - descending - pomocí komparační funkce.

Pro vzestupné třídění lze definovat:

U sestupného třídění:

je rozdíl pouze v rovnici:

CF - komparační (porovnávací) funkce - ( ), která vrací zápornou hodnotu pokud dva prvky: , kladnou hodnotu když: a hodnotu 0, pokud: . Funkce je využita pro párové porovnání dvou prvků ze seznamu při třídění.

Search ( ) hledání prvku l v nesetříděném seznamu. Hledání prvku l v nesetříděném seznamu L znamená projít všechny prvky do té doby, dokud není prvek nalezen, nebo dokud se nenarazí na konec seznamu.

RemoveListItem ( ) nalezení prvního výskytu prvku x v seznamu L pomocí vhodného algoritmu a tento prvek bude vymazán (navrácení nového seznamu M).

V následujících příkladech si můžete vyzkoušet, zdali jste pochopily všechny vyjmenované metody pro práci se seznamy.