Shag'al harakati muammolari - Pebble motion problems

The tosh bilan harakatlanish muammolari, yoki grafalardagi toshbo'ron harakati, bilan bog'liq muammolar to'plami grafik nazariyasi a-dagi tepadan tepaga bir nechta ob'ektlarning ("toshlar") harakati bilan shug'ullanish grafik istalgan vaqtda tepalikni egallashi mumkin bo'lgan toshlar sonini cheklash bilan. Shag'al harakatlanish muammolari ko'p domen kabi domenlarda paydo bo'ladi.robot harakatni rejalashtirish (unda toshlar robotlar) va tarmoqni yo'naltirish (unda toshlar mavjud paketlar ma'lumotlar). Shag'al harakati muammosining eng taniqli namunasi mashhurdir 15 jumboq bu erda tartibsiz guruh, o'n beshta plitani bir vaqtning o'zida bitta plitkani siljitish orqali 4x4 katakchada qayta tuzish kerak.

Nazariy formulalar

Yalang'och harakat muammosining umumiy shakli - Grafadagi tosh harakati^[1] quyidagicha tuzilgan:

Ruxsat bering ${ displaystyle G = (V, E)}$ bilan grafik bo'ling ${ displaystyle n}$ tepaliklar. Ruxsat bering ${ displaystyle P = {1, ldots, k }}$ bilan toshlar to'plami bo'ling ${ displaystyle k$ . Shag'allarning joylashishi xaritalashdir ${ displaystyle S: P rightarrow V}$ shu kabi ${ displaystyle S (i) neq S (j)}$ uchun ${ displaystyle i neq j}$ . Harakat ${ displaystyle m = (p, u, v)}$ toshni ko'chirishdan iborat ${ displaystyle p}$ tepadan ${ displaystyle u}$ tutashmagan tepalikka ${ displaystyle v}$ . Ikkita kelishuvni hisobga olgan holda, Graflar bo'yicha Pebble Motion muammosi hal qilinadi ${ displaystyle S_ {0}}$ va ${ displaystyle S _ {+}}$ , o'zgartiradigan harakatlar ketma-ketligi bormi ${ displaystyle S_ {0}}$ ichiga ${ displaystyle S _ {+}}$ .

O'zgarishlar

Muammoning umumiy o'zgarishi grafika tuzilishini quyidagicha cheklaydi:

Variantlarning yana bir to'plami ba'zi holatlarni ko'rib chiqadi^[5] yoki barchasi^[3] shag'allar yorliqsiz va bir-birining o'rnini bosadi.

Muammoning boshqa versiyalari nafaqat erishish mumkinligini isbotlash uchun, balki transformatsiyani amalga oshiradigan (potentsial optimal) harakatlar ketma-ketligini (ya'ni reja) topishga intiladi.

Murakkablik

Grafalar muammosi bo'yicha toshli harakatdagi eng qisqa yo'lni topish (belgilangan toshlar bilan) ma'lum Qattiq-qattiq^[6] va APX-qattiq.^[3] Yuqorida aytib o'tilgan xarajatlar o'lchovidan foydalanilganda (qo'shni tepaliklarga harakatlarning umumiy sonini minimallashtirish) yorliqsiz muammoni polinom vaqtida echish mumkin, ammo Qattiq-qattiq boshqa tabiiy xarajatlar ko'rsatkichlari uchun.^[3]

Adabiyotlar

^ Kornhauzer, Doniyor; Miller, Gari; Spirakis, Pol (1984), "Grafalar, permutatsiya guruhlari diametri va qo'llanmalaridagi toshlar harakatini muvofiqlashtirish", Kompyuter fanlari asoslari bo'yicha 25-yillik simpozium materiallari (FOCS 1984), IEEE Computer Society Press, 241–250 betlar, CiteSeerX 10.1.1.17.3556, doi:10.1109 / sfcs.1984.715921, ISBN 978-0-8186-0591-8
^ Auletta, V .; Monti, A .; Parente M.; Persiano, P. (1999), "Daraxtlarda toshlar harakatini amalga oshirishning chiziqli algoritmi", Algoritmika, 23 (3): 223–245, doi:10.1007 / PL00009259, JANOB 1664708
^ ^a ^b ^v ^d Clinesk, Gruya; Dumitresku, Adrian; Pach, Xanos (2008), "Grafalar va kataklardagi qayta konfiguratsiyalar", Diskret matematika bo'yicha SIAM jurnali, 22 (1): 124–138, CiteSeerX 10.1.1.75.1525, doi:10.1137/060652063, JANOB 2383232
^ Surynek, Pavel (2009), "Ikki tomonlama grafiklarda bir nechta robotlar uchun yo'llarni rejalashtirishning yangi yondashuvi", IEEE robototexnika va avtomatika bo'yicha xalqaro konferentsiya materiallari (ICRA 2009), IEEE, 3613–3619 betlar, doi:10.1109 / robot.2009.5152326, ISBN 978-1-4244-2788-8
^ Papadimitriou, Xristos H.; Raghavan, Prabhakar; Sudan, Madxu; Tamaki, Hisao (1994), "Grafada harakatni rejalashtirish", Kompyuter fanlari asoslari bo'yicha 35-yillik simpozium materiallari (FOCS 1994), IEEE Computer Society Press, 511-520 betlar, doi:10.1109 / sfcs.1994.365740, ISBN 978-0-8186-6580-6
^ Ratner, Doniyor; Warmuth, Manfred (1990), "The ${ displaystyle (n ^ {2} -1)}$ - jumboq va boshqa joyga ko'chish muammolari ", Ramziy hisoblash jurnali, 10 (2): 111–137, doi:10.1016 / S0747-7171 (08) 80001-6, JANOB 1080669

[Kornhauser-1] Kornhauzer, Doniyor; Miller, Gari; Spirakis, Pol (1984), "Grafalar, permutatsiya guruhlari diametri va qo'llanmalaridagi toshlar harakatini muvofiqlashtirish", Kompyuter fanlari asoslari bo'yicha 25-yillik simpozium materiallari (FOCS 1984), IEEE Computer Society Press, 241–250 betlar, CiteSeerX 10.1.1.17.3556, doi:10.1109 / sfcs.1984.715921, ISBN 978-0-8186-0591-8

[Auletta-2] Auletta, V .; Monti, A .; Parente M.; Persiano, P. (1999), "Daraxtlarda toshlar harakatini amalga oshirishning chiziqli algoritmi", Algoritmika, 23 (3): 223–245, doi:10.1007 / PL00009259, JANOB 1664708

[Calinescu-3] v ^d Clinesk, Gruya; Dumitresku, Adrian; Pach, Xanos (2008), "Grafalar va kataklardagi qayta konfiguratsiyalar", Diskret matematika bo'yicha SIAM jurnali, 22 (1): 124–138, CiteSeerX 10.1.1.75.1525, doi:10.1137/060652063, JANOB 2383232

[Surynek-4] Surynek, Pavel (2009), "Ikki tomonlama grafiklarda bir nechta robotlar uchun yo'llarni rejalashtirishning yangi yondashuvi", IEEE robototexnika va avtomatika bo'yicha xalqaro konferentsiya materiallari (ICRA 2009), IEEE, 3613–3619 betlar, doi:10.1109 / robot.2009.5152326, ISBN 978-1-4244-2788-8

[Papadimitriou-5] Papadimitriou, Xristos H.; Raghavan, Prabhakar; Sudan, Madxu; Tamaki, Hisao (1994), "Grafada harakatni rejalashtirish", Kompyuter fanlari asoslari bo'yicha 35-yillik simpozium materiallari (FOCS 1994), IEEE Computer Society Press, 511-520 betlar, doi:10.1109 / sfcs.1994.365740, ISBN 978-0-8186-6580-6

[Ratner-6] Ratner, Doniyor; Warmuth, Manfred (1990), "The ${ displaystyle (n ^ {2} -1)}$ - jumboq va boshqa joyga ko'chish muammolari ", Ramziy hisoblash jurnali, 10 (2): 111–137, doi:10.1016 / S0747-7171 (08) 80001-6, JANOB 1080669

[1]

[2]

[3]

[4]

[5]

[6]