MARS

Jak nejlépe propojit základny na Marsu?

Během kolonizace Marsu lidstvo postavilo několik základen. Nyní postup osidlování pokročil do fáze, kdy je třeba jednotlivé oddělené základny propojit pomocí tunelů tak, aby se dalo dostat z jakékoli základny do kterékoli jiné bez potřeby vycházet do volného prostoru. Tunely mohou vést jen z jedné základny do jiné (křižovatky tunelů mohou být jen v základnách). Zároveň je třeba mít síť tunelů co nejkratší, jednak kvůli náročnosti stavby samotné a jednak kvůli minimalizaci objemu tunelů (potřeba udržovat v tunelech dýchatelnou atmosféru).

Příklad možných tunelů a jejich délek je na následujícím obrázku:

Vaším úkolem bude vybrat z možných tunelů ty, které by se měly postavit, tedy ty, které zajistí propojení všech základen s minimálními náklady. Pro výše uvedený příklad by to byly tyto tunely:

V modulu mars.py, který budete odevzdávat, vytvořte funkci solve(), která z možných tunelů vybere ty, které se podle vás mají postavit. Funkce bude mít následující vstupy a výstupy:

Příklad uvedený na obrázcích výše by v Pythonu vypadal takto (pokud by funkce solve() byla implementována správně):

>>> available_tunnels = [
    ("Hermes Station", "Terra Station", 200),
    ("Nox Colony", "Gaia Station", 500),
    ("Terra Station", "Gaia Station", 400),
    ("Terra Station", "Nox Colony", 200)]
>>> solve(available_tunnels)
[0, 2, 3]

Správná implementace funkce solve() by tedy doporučila postavit tunely na indexech 0, 2 a 3, vynechala by tedy nejdelší tunel na indexu 1, který pro propojení všech stanic není potřeba.

Příklad (nesprávné) implementace funkce solve() může vypadat třeba takto:

def solve(available_tunnels):
    chosen_tunnels = []
    chosen_tunnels.append(0)
    chosen_tunnels.append(len(available_tunnels)-1)
    return chosen_tunnels

Tato implementace vždy volí jen první a poslední tunel, nezávisle na jejich délkách. Toto řešení skoro nikdy nebude přípustné, protože nebude propojovat všechny základny.

Kdybychom např. nahradili tělo funkce solve() jediným příkazem return list(range(len(available_tunnels))), funkce by vždy doporučila vybudovat všechny možné tunely (vrátila bych seznam indexů všech tunelů). Takové řešení je vždy přípustné (propojuje všechny základny), ale skoro jistě není optimální (délku tunelů - a tím i náklady - lze snížit).

Řešení bude testováno na několika náhodně vygenerovaných mapách. Bodové hodnocení bude zohledňovat

• zda je výstup algoritmu validní,
• zda jsou propojeny všechny základny,
• jak blízko optimu je nalezené řešení.