The math dina kahirupan sapopoe: sistem navigasi satelit
Navigator satelit tangtosna mangrupikeun alat anu umum, sareng sering dianggap yén operasina ngan saukur nampi inpormasi ti satelit anu "nunjukkeun jalan". Nyatana, kamampuanna pikeun netepkeun rute pikeun ngahontal tujuan naon waé mangrupikeun gabungan tina téknik anu béda-béda, anu paduli kana kamampuan pikeun ngaidentipikasi akurat dimana urang aya iraha waé, kasadiaan peta jalan anu akurat sareng anu diperbarui sareng di luhur sadayana, kamampuan ngitung rute anu pangsaéna pikeun ngahontal tujuan urang. Dina tulisan ieu kami bakal museurkeun perhatian urang kana titik terakhir ieu, ngajelaskeun yén dina dasar itungan ieu aya téori matématika anu pas pisan, "téori grafikAnu ngamungkinkeun urang ngartos kumaha mungkin pikeun ngaidentipikasi jalur anu paling pondok antara dua titik. Dina praktékna, urang ningal kumaha gambaran ilmiah abstrak janten pondasi objék anu praktis, nyata sareng di luhur sadayana anu mangpaat pisan.
Kahiji, hayu urang mimitian ti handap: naon anu dimaksud grafik?
Nyatana, éta henteu sanés ngan sakumpulan unsur anu saling nyambung: unggal unsur disebat "simpul", sareng sambungana disebat "busur". Conto grafik nyaéta anu ngagaduhan unsur-unsur rangkéan kota anu saling nyambung ngalangkungan jaringan jalan tol: dina hal ieu, simpulna nyaéta kota sareng lengkungan mangrupikeun ruas jalan raya antara kota-kota éta sorangan. Urang tiasa ngabayangkeun grafik salaku séri bola warna atanapi bunderan (simpul) dihubungkeun babarengan ku garis (busur). Arc tiasa orientasi atanapi teu diarahkeun: busur berorientasi nyaéta anu ngamungkinkeun jalanna ngan ukur ti titik mimiti ka titik kadatangan (sareng henteu sabalikna); lengkungan anu teu diarahkeun nyaéta anu ngamungkinkeun jalan dina dua arah. Dina conto navigator kami, jalan tiasa dianggap busur anu berorientasi upami éta saarah, bari éta tiasa dianggap busur anu teu diarahkeun upami éta dua arah.
Grafik cenah ditimbang upami nilaina, anu disebut beurat, pakait sareng tiap busur. Nilai ieu umumna tiasa positip atanapi négatip. Ngarujuk kana conto kota sareng jalan raya sateuacana, urang tiasa kéngingkeun grafik kabobotan ku ngasosiasikeun unggal bagéan jalan tol kalayan panjangna dina kilométer. Dina grafik, sacara téoritis tiasa angkat ti simpul A kana simpul B dina sababaraha cara anu béda, ngagunakeun busur anu béda, sapertos anu nyatana tiasa angkat ti hiji kota ka kota anu sanés nganggo jalan anu béda. Urang teras bakal nyebat "jalur paling pondok" salaku "cara paling pondok" pikeun nyambungkeun simpul A kana simpul B.
Pikeun navigator satelit urang, mendakan jalan antara titik awal sareng titik akhir ibarat mendakan jalur paling pondok dina grafik. Dina tiori matématika grafik, masalah ngitung jalur paling pondok parantos dikaji sareng dianalisis tina unggal sudut pandang, sareng aya seueur algoritma anu dihasilkeun. Salah sahiji anu paling sering dianggo, contona, nyaéta Algoritma Dijkstra, tapi aya seueur anu sanés. Kituna mangrupikeun pilihan pabrikan pikeun milih algoritma anu dianggap paling pantes. Dina pilihan ieu pastina kedah diperhatoskeun yén tiori anu ngalangkungan milarian jalur anu paling pondok antara dua titik tiasa rumit pisan, utamina nalika ngalakukeun itungan dina peta jalan anu rumit pisan. Salaku conto, algoritma A * parantos dikembangkeun anu milari jalur anu pang pondokna nganggo "estimasi statistik" pikeun unggal simpul; nyarios dina "kecap sesah", perkiraan ieu ngagambarkeun evaluasi priori ngeunaan kaunggulan ngaliwat hiji titik dina titik anu sanés dina jalan ka tujuan akhir. Bisi wae, asup kana detil algoritma janten rada rumit sareng meryogikeun kanyaho khusus; kami ngarepkeun kumaha waé pikeun nyayogikeun visi dasar tina masalah sareng panginten tiasa ngarangsang minat kana téori matématika kalayan seueur implikasi praktis dina kahirupan sapopoe.
John Calcerano