Hamilton for Android APK

Lýsing

P versus NP vandamálið er stórt óleyst vandamál í tölvunarfræði. Fjallað er um hvort sérhvert vandamál sem hægt er að sannreyna fljótt með tölvu geti líka leyst fljótt með tölvu. Það er eitt af sjö þúsaldarverðlaunavandamálum sem Clay Mathematics Institute valdi til að bera 1.000.000 Bandaríkjadala verðlaun fyrir fyrstu réttu lausnina. Hamilton-hringrásarvandamálið er vel þekkt NP-heildarvandamál úr Graph Theory sviðinu. Að leysa slíkt vandamál, t.d. að finna margliða reiknirit sem leysir það við hvaða inntak sem er, myndi gera mannkynið nær en nokkru sinni fyrr til að leysa P á móti NP vandamálinu.

Í þessum leik er þér gefið Graf, það er sett af hnútum og brúnum, sem stundum inniheldur Hamilton-hring (frekari upplýsingar hér https://en.wikipedia.org/wiki/Hamiltonian_path_problem) og stundum ekki, og þú þarf að leysa það, annað hvort með því að afhjúpa Hamilton-hringrás eða með því að ákveða að það sé ekki til fyrir það graf.

stór ábending til að ákveða hvort graf sé hamiltónskt (inniheldur Hamilton hringrás) má finna hér https://en.wikipedia.org/wiki/Graph_toughness.

Komdu og leystu 1 milljón dollara vandamál og lærðu graffræði á meðan þú ert að því!