Коњићев пут — разлика између измена
Садржај обрисан Садржај додат
Нова страница: {{Hide in print|right|thumb|250px|Отворен коњићев пут на шаховској табли.}}{{Only in print|Image:K… |
мНема описа измене |
||
Ред 4:
'''Коњићев пут''' ({{jez-eng|Knight's tour}}) је низ потеза фигуре коња на шаховској табли, таквих да свако поље буде посећено тачно једном. Ако коњ свој пут заврши тачно на оном пољу са ког је кренуо (тако да може обиђе таблу истим пољима још једном) кажемо да је пут затворен, иначе кажемо да је отворен. Тачан број отворених коњићевих путева стандардне 8 × 8 шаховске табле још увек је непознат.
У теорији проналажење коњићевог пута је математички проблем, и често се задаје студентима информатике како би написали одговарајући програм који проналази коњићев пут. Различите варијанте овог проблема укључују и проналажење решења за табле нестандардних величина, као и решења за табле које нису правоугаоног облика.<ref>-{H. M. Deitel, P. J. Deitel. "Java How To Program Fifth Edition." ''Prentice Hall'', Upper Saddle River, New Jersey, pp. 326–328. 2003.}-</ref>
==Теорија==
[[Image:Knight's graph showing number of possible moves.svg|left|thumb|270px|Коњићев граф показује све могуће путеве. Бројеви на чворовима представљају број могућих потеза са тог поља.]]
У теорији проналажење коњићевог пута је пример много општијег проблема проналаска Хамилтоновог пута у теорији графова. Проблем проналажења затвореног коњићевог пута можемо постматрати као инстанцу проблема проналажења Хамилтоновог циклуса у графу. Приметимо, ипак, да за разлику од решења за Хамилтонов пут, решење за коњићев пут можемо добити у линеарном времену.<ref>{{Cite journal |first=A. |last=Conrad |first2=T. |last2=Hindrichs |first3=H. |last3=Morsy |lastauthoramp=yes |first4=I. |last4=Wegener |title=Solution of the Knight's Hamiltonian Path Problem on Chessboards |journal=Discrete Applied Mathematics |volume=50 |issue=2 |pages=125–134 |year=1994 |doi=10.1016/0166-218X(92)00170-Q }}</ref>
{{clear}}
==Историја==
Линија 19 ⟶ 15:
Најстарији писани траг овог проблема датира још из деветог века. Индијски песник Рудрата у својој збирци песама "Кавиаланкара" користио је низ шаблона коњићевог пута на половини шаховске табле у поетској фигури званој "турагападабанда" или "распоред у коњевим корацима". Строфа се може читати на исти начин с лева на десно и пратећи коњићев пут. Будући да је индијско писмо коришћено овом приликом слоговно, сваки слог може се посматрати као једно поље на шаховској табли.
से ना ली ली ली ना ना ना ली
Линија 36 ⟶ 31:
lī lī lī nā nā nā nā lī
На пример, прва линија се може читати с лева на десно или кренући од првог слога до трећег у другом реду(2.3), па затим до слога 1.5 и редом преко 2.7, 4.8, 3.6, 4.4, до 3.2.
Линија 76 ⟶ 70:
Проблем коњићевог пута користи се у имплементацији нервних мрежа. Мреже су направљене тако што је сваки дозвољени потез коњем представљен као нерв, а сваком нерву је иницијално насумично постављена вредност "активан" или "неактиван" ( 1 или 0 ), са 1 уколико је
нерв део крајњег решења. Сваки нерв има функцију стања ( описану испод). При покретању мреже, сваки нерв може променити своје стање и излаз на основу стања и излаза својих суседа ( који су удаљени тачно један потез од њега) и то пратећи следећа правила:
::<math>
U_{t+1} (N_{i,j}) = U_t(N_{i,j}) + 2 - \sum_{N \in G(N_{i,j})} V_t(N)
Линија 90 ⟶ 82:
\end{array} \right.
</math>
Где <math>t</math> представља интервале времена, <math>U(N_{i,j})</math> је стање нерва који повезује поље <math>i</math> до поља <math>j</math>, <math>V(N_{i,j})</math> је излаз нерва од <math>i</math> до <math>j</math>, и <math>G(N_{i,j})</math> је скуп суседа нерва.
Линија 123 ⟶ 114:
које почетно поље на шаховској табли користећи Ворнсдорфово правило може се пронаћи у књизи "Century/Acorn User Book of Computer Puzzles".
== Референце ==
{{reflist}}
* [[Abu-Bakr Muhammad ben Yahya as-Suli]]▼
== Види још ==
▲* -{[[Abu-Bakr Muhammad ben Yahya as-Suli]]}-
* [[Џорџ Колтановски]]
* [[Најдужи непрекрштени коњићев пут]]
* [[Проблем осам дама]]
==Спољашње везе==
Линија 140 ⟶ 134:
* [http://www.mayhematics.com/t/t.htm Knight's tour notes]
* [http://www.kongregate.com/games/Exportgold/a-knights-tour Knight's Tour Flash Game]
* [http://warnsdorff.com warnsdorff.com] - Page devoted to Warnsdorff's Rule
[[Категорија:Графовски алгоритми]]
[[Категорија:Шаховски проблеми]]
| |||
