[es] - Sahovska tabla i konj

igac
Banjaluka

Član broj: 415
Poruke: 562
*.teleklik.net

+2 Profil

^{15.03.2004. u 21:22 - pre 244 meseci}

Odrediti najkraci put konja po sahovskoj tabli koji povezuje dva data polja table?
Ideje, komentari :)

^{"nice town, i'll take it..."}

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: Sahovska tabla i konj

^{15.03.2004. u 22:14 - pre 244 meseci}

Napravi graf. Polje na šahovskoj tabli je čvor. Dva čvora su povezana ako konj može da pređe sa jednog na drugo u jednom potezu. Zatim na tako definisan graf primeni neki od algoritama za nalaženje najkraćeg puta (Dijkstra, Bellman-Ford). Ne verujem da za šahovsku tablu postoji neko posebno bolje rešenje.

Više o tome ovde, između ostalog.

f

Odgovor na temu

igac
Banjaluka

Član broj: 415
Poruke: 562
*.teleklik.net

+2 Profil

Re: Sahovska tabla i konj

^{15.03.2004. u 22:37 - pre 244 meseci}

pa problem je sto konj skace na L, pa onda nece bas biti samo da idem prema odredistu a da on "tacno naskoci" na to polje... mislio sam da ako npr pocetno polje a1 a trebam stici u f7 krenem ovako... skocim "bezze" samo da ide prema f7, npr na b3, pa pogledam "razdaljinu" b3-f7, onda. skocim dalje, da se priblizim jos polju f7 - na c5, onda opet bacim pogled na "razdaljinu" do f7, pa posto opet "ima mjesta" skocim na e6 sada, da se sto vise priblizim cilju... e sada se slucaj "svodi" na "elementaran" (a da napravim listu tih "elementarnih") pa samo "odradim" d8, f7... al opet ima poslaposlaposla... pogledacu ovaj link, vidim da su tu koristili grafove... hvala :)

^{"nice town, i'll take it..."}

Odgovor na temu

mucky
Aleksandar Mastilović
Freelancer
Novi Sad - Srbija

Član broj: 237
Poruke: 412
*.12.eunet.yu

+1 Profil

Re: Sahovska tabla i konj

^{16.03.2004. u 20:07 - pre 244 meseci}

Moglo bi i backtracking-om... Nije najefikasnije, ali verujem da bi radilo

Odgovor na temu

masetrt
Marko Djurovic
Programer, Omni-Explorer
Beograd

Član broj: 3129
Poruke: 228
*.nat-pool.bgd.sbb.co.yu.

Sajt: www.vast.com

+2 Profil

Re: Sahovska tabla i konj

^{05.11.2004. u 15:52 - pre 236 meseci}

Poslusaj ideju da od sahovske table napravis graf i spoj odgovarajuce cvorove (one na L i G) pa primeni jedan od algoritama za trazenje puta (Dijkstra-u za ovaj slucaj preporucujem)

His majesty Grand Duke of Shumadija and Western Pomoravlje

Odgovor na temu

Damjan S. Vujnovic
London, UK

Član broj: 30444
Poruke: 81
*.ceetel.co.yu.

Jabber: damjan@elitesecurity.org
ICQ: 68189289
Sajt: www.javasvet.net

Profil

Re: Sahovska tabla i konj

^{05.11.2004. u 18:31 - pre 236 meseci}

@filmil (uz pozdrav):

Pa nisam bas siguran da ne postoji neko "posebno bolje resenje" za sahovsku tablu... Zamisli da imas bas veliku tablu (na primer 1000x1000; za malu tablu ce ionako sve osim backtrackinga biti brzo) i da gledas kako najkrace da stignes iz donjeg levog u gornji desni ugao (na primer). Ono sto meni pada na pamet je da prvo ides "greedy" - sto brze ka cilju ("pravolinijski", ta se pogresno izrazim), a onda kad dodjes "dovoljno blizu" pocnes pametnije da biras korake.

Sve je ovo posledica postojanja simetrije - ako malo (mnogo) odemo u krajnost i skakaca zamenimo pionom (dobro, dobro, ovde je stepen simetrije mnogo veci, ali i kod konja definitivno postoji), postaje ocigledno da moze brze od Dijkstre, 99% je sigurno da slicno moze i ovde.

Ono sto meni pada na pamet je da se "prekalkulisu" najkrace putanje na, npr tabli 10x10 i da se onda do okoline 10x10 ide greedy i da se gleda kako je najbolje uci u tu 10x10 oblast... Ovo u ovom obliku lici na heuristiku, ali zbog (opet) simetrije mi se cini da se moze napraviti i algoritam koji daje optimalno resenje...

Hef fan,
Damjan

P.S. Ono sa ant-om je proslo, 10x...

I love the smell of copyright violations in the morning. Smells like... freedom!

Odgovor na temu

filmil
Filip Miletić
Oce Technologies B.V., inženjer
hardvera
Arcen, NL

Član broj: 243
Poruke: 2114
*.adsl.zonnet.nl.

Jabber: filmil@jabber.org
ICQ: 36601391

+3 Profil

Re: Sahovska tabla i konj

^{05.11.2004. u 22:33 - pre 236 meseci}

Citat:

Ovo u ovom obliku lici na heuristiku, ali zbog (opet) simetrije mi se cini da se moze napraviti i algoritam koji daje optimalno resenje...

IMHO je u tome štos. Heuristikom onako kako si opisao vrlo brzo možeš da transportuješ konja :) blizu ciljnog polja, pa i da ga tamo parkiraš. Ali ne deluje mi očigledno kako od toga može lokalnim izmenama da se napravi najkraći put.

Citat:

P.S. Ono sa ant-om je proslo, 10x...

Jel na kraju ant ili javac?

Odgovor na temu