Hamilton for Android

ဖော်ပြချက်

P နှင့် NP ပြဿနာသည် ကွန်ပျူတာသိပ္ပံတွင် မဖြေရှင်းနိုင်သော အဓိကပြဿနာဖြစ်သည်။ ကွန်ပြူတာမှ လျင်မြန်စွာ စစ်ဆေးအတည်ပြုနိုင်သည့် ပြဿနာတိုင်းကိုလည်း ကွန်ပြူတာမှ လျင်မြန်စွာ ဖြေရှင်းနိုင်မလား။ ဒါဟာ Clay Mathematics Institute က ရွေးချယ်တဲ့ ထောင်စုနှစ်ဆု ပြဿနာ ခုနစ်ခုထဲက တစ်ခုဖြစ်ပြီး ပထမဆုံး မှန်ကန်တဲ့ အဖြေအတွက် US$ 1,000,000 ဆုကို ပေးအပ်သွားမှာဖြစ်ပါတယ်။ Hamiltonian cycle problem သည် Graph Theory နယ်ပယ်မှ လူသိများသော NP-ပြီးပြည့်စုံသော ပြဿနာဖြစ်သည်။ ထိုသို့သောပြဿနာကိုဖြေရှင်းခြင်း ဥပမာ- ပေးထားသည့်ထည့်သွင်းမှုတစ်ခုခုတွင်ဖြေရှင်းနိုင်သော polynomial algorithm တစ်ခုကိုရှာဖွေခြင်းသည် P နှင့် NP ပြဿနာကိုဖြေရှင်းရန် လူသားမျိုးနွယ်ကို ယခင်ကထက်ပိုမိုနီးကပ်စေမည်ဖြစ်သည်။

ဤဂိမ်းတွင် သင့်အား Graph တစ်ခုပေးထားပြီး၊ ၎င်းသည် တစ်ခါတစ်ရံတွင် Hamiltonian စက်ဝန်းပါရှိသော node များနှင့် edges အစုံဖြစ်သည် (ဤနေရာတွင် https://en.wikipedia.org/wiki/Hamiltonian_path_problem တွင်ပိုမိုလေ့လာပါ) နှင့် တစ်ခါတစ်ရံတွင် သင်မပါဝင်ပါ။ Hamiltonian လည်ပတ်မှုကို ဖော်ထုတ်ခြင်းဖြင့် သို့မဟုတ် ထိုဂရပ်အတွက် ၎င်းသည် မရှိဟု ဆုံးဖြတ်ခြင်းဖြင့် ဖြေရှင်းရန် လိုအပ်သည်။

ဂရပ်တစ်ခုသည် ဟာမီလ်တိုနီယံ (Hamilton cycle ပါ၀င်သည်) ကို ဆုံးဖြတ်ရန်အတွက် ကြီးမားသော အကြံပြုချက်ကို ဤနေရာတွင် https://en.wikipedia.org/wiki/Graph_toughness တွင် တွေ့နိုင်ပါသည်။

လာ၍ $1 million ပြဿနာကို ဖြေရှင်းပြီး Graph Theory ကို လေ့လာပါ။