Софтуерно Инженерство
Loading...
+ Нов въпрос
Angeld55 avatar Angeld55 20 Точки

Задача "Knight's tour!"

Здравейте, 

не знам кои от вас знаят за тази задача,понеже е доста популярна!Ако някой не я знае, задачата е следната "напишете програма която по зададени координати на поле в шахматна дъска с размери NxN (N също е параметър на програмата) намира (чрез рекурсия) дали има път през който може да мине един шахматен кон, за да обиколи цялата дъска. Конят няма право да стъпва повторно на никое поле."

Въпросът е ,че би трябвало,да съм решил задачата,но не ми ми  дава отговор (става като безкраен цикъл и не иска да излезе от рекурсията),когато въведа дъската да е по-голяма от 7X7.При по малките размери ми дава правилен отговор!

Това е кодът ми https://github.com/Angeld55/exercise/blob/master/KnightsTour.cs

Ако някой има идея как да го оптимизирам,ще съм много благодарен !

1
Technology Fundamentals 19/01/2016 18:27:11
RoYaL avatar RoYaL SoftUni Team Trainer 6883 Точки

Мисля, че не е безкраен цикъла, просто изчисляваш ходове, които вече си ги изчислил. Преди рекурсивните колове казваш, че си посетил, като приключиш - размаркираш. Супер, обаче има шанс да попаднеш на същия sequence втори път, от другаде.

Т.е. това маркиране като посетени важи само за текущия сикуенс, но не и за друг. Ако друг сикуенс хитне част от този - ще се наложи да го изчислиш целия.

Освен пазенето на bool visited[x,y], според мен трябва и да пазиш в някакъв масив ходовете от тоя пойнт, до където може да се стигне и евентуално има ли изход. За да може като стъпнеш на полето 4,5 например и преди си изчислиш че от него до края има 600 хода, които водят до нищо. Запиши си го това и когато втори път хитнеш 4,5 да знаеш че няма смисъл например, или ако има смисъл да прибавиш ходовете, които си записал и да продължиш от там от където може.

Според мен задачката трябва да може да се реши линейно, докато твоя код го пуснах с едно принтене в началото на функцията където инкрементирам една глобална променлива, точно преди да почна да пиша този пост и в момента е на 730 000 извиквания на функцията и има мегдан да продължава доста.

2
Angeld55 avatar Angeld55 20 Точки

Ванка,благодаря ти много за реакцията :) ! Ще се опитам да го измисля,въпреки че не е сигурно дали ще стане ,понеже като се стига до квартаче X,Y се стига от друго място, съответно и има различни изходи от тази точка и различен брои вариянти от къде да мине !Но ще го измисля, благодаря ти :)!

0
RoYaL avatar RoYaL SoftUni Team Trainer 6883 Точки

Когато си на [x,y] и има N на брой възможности - изчисли ги. Докато ги изчисляваш, ти си маркирал полето като визитед, т.е. няма да стъпиш обратно на [x,y] и няма да зациклиш, което е ОК. Като ги изчислиш всичките възможности - запиши че си ги изчислил.

Ако да речем от [x,y] можеш да отидеш на [n,m] и на [a,b], а от [n,m] можеш да отидеш на [u,v] и [w,z], а пък от [a,b] на [i,j] и толкоз, запиши тези възможности.

Защото после като хитнеш [x,y] от някъде другаде, трябва да го знаеш това. Нещо повече. Ако хитнеш от някъде другаде [n,m] трябва да знаеш, че може да отиде до [u,v] и [w,z] без да ги изчисляваш отново.

Опитах се да нарисувам примерна ситуация:

4
moholovka avatar moholovka 168 Точки

Не ти трябва рекурсия ти имаш краен брой стъпки N*N-1 демек всичко може да стане с един прост цикъл. Хвърлих едно око на кода, но не можах да схвана логиката добре, ако искаш обясни с два три реда :) 

Това е моето решение (не че много се чете) :)

https://github.com/IvanMladenov/Algorithms/blob/master/GreedyAlgorithms/KnightsTour/Program.cs

1
20/01/2016 00:23:57